Soduko Blocküberprüfung

[DerAhnungsloseDude]

Hey yo ich hätte eine Frage zu einer Aufgabe:
Ich habe leider keine Idee wie ich die Blockweise überprüfung in meinen Programm einfügen soll.
Die Aufgabe lautet:
Eine allgemeinere Version des Sudokus ist ein n×n-Sudoku. Es ist eine n×n-Matrix von Zahlen zwischen 1 und n (einschließlich), wobei n eine Quadratzahl sein muss. Analog ist ein n × n-Sudoku gültig, wenn in jeder Zeile, in jeder Spalte und in jedem Block jede Zahl genau einmal vorkommt. Ein Block hat hierbei die Größe √ n × √ n, von denen das Sudoku n viele enthält, die ebenfalls jeweils nicht überlappen. Schreiben Sie eine allgemeinere Version des vorherigen Programms, das zunächst eine Quadratzahl n einliest. Anschließend liest Ihr Programm die n 2 Einträge eines n × n-Sudokus zeilenweise ein. Danach gibt Ihr Programm yes aus, wenn das eingelesene Sudoku gültig ist. Andernfalls gibt es no aus.
Mein Programm sieht bisher so aus:
import java.util.Scanner;
public class Aufgabe2 {

public static void main (String [] args){

Scanner scan = new Scanner (System.in);
int n = scan.nextInt(); //einlesen der Zahl n
if(isSquare(n)){


int [][] matrix = new int[n][n]; //ein Array der Laenge nxn wird erstellt

for(int i = 0; i<matrix.length; i++){ //befuellen des Arrays mit selbst eingelesenen Int werten
for( int j = 0; j<matrix.length; j++){

matrix[j] = scan.nextInt();
}
}

for(int i=0; i<n; i++){
for(int j = 0; j<n; j++){
for(int k = 0; k<n; k++){
if(k != i && matrix[j] == matrix [k][j] ||k!=j &&matrix[j]==matrix[k]){
System.out.println("no");
return;
} //prueft ob in den Zeilen oder Spalten die selbe Zahl enthalten ist
//falls ja wird ein no ausgegeben
}
}
System.out.println("yes"); //falls nein wird ein yes ausgegeben
return;
}

}
else {
System.out.println("no");
}
}
public static boolean isSquare(int n) {
int root = (int) Math.sqrt(n);
return root * root == n;
}
}

 

[mihe7]

Schau Dir mal ein 9x9-Sudoku an:

 |0|1|2|3|4|5|6|7|8|
0|*    |*    |*    |
1| 0,0 | 0,1 | 0,2 |
2|__0__|__1__|__2__|
3|*    |*    |*    |
4| 1,0 | 1,1 | 1,2 |
5|__3__|__4__|__5__|
6|*    |*    |*    |
7| 2,0 | 2,1 | 2,2 |
8|__6__|__7__|__8__|

Die Zahlen außen entsprechen den Indizes Deiner Matrix. Den eingezeichneten Blöcken habe ich Koordinaten gegeben, außerdem findest Du in der letzten Zeile eines jeden Blockes eine Blocknummer, die die Blöcke von links oben nach rechts unten von 0 bis 8 durchnummeriert. Ferner ist in jedem Block das erste Feld (links oben) mit einem Stern markiert.

Die Position des ersten Feldes eines Blocks ist wichtig, denn von dort aus kannst Du k Zeilen und k Spalten, und somit alle Elemente eines Bocks, durchsuchen.

Jetzt gibt es zwei Möglichkeiten:
a) wenn Du Dir die Koordinaten anschaust, stellst Du fest, dass der Zeilen-Index Deiner Matrix dem k-Fachen der ersten Koordinate des Blocks entspricht: (2,0) = 2*3 = 6. Analog gilt dies für den Spalten-Index und der zweiten Koordinate eines Blocks. So befindet sich das erste Feld des Blocks (2,1) an Position (6, 3) in der Matrix. Du kannst also mit zwei Schleifen über die Blöcke iterieren:

for (int yBlock = 0; yBlock < k; yBlock++) {
    for (int xBlock = 0; xBlock < k; xBlock++) {
        int yFeld = yBlock * k;
        int xFeld = xBlock * k;
        // behandle k-Zeilen und k-Spalten  ab (yFeld, xFeld)
     }
}

b) die zweite Möglichkeit ist wesentlich eleganter. Wenn Du die linken Blöcke (Blocknummern 0, 3, 6) anschaust, siehst Du, dass deren Nummern sich jeweils um k erhöhen. Würde man also die Blocknummer ohne Rest durch k teilen, würde man die y-Koordinate des Blocks erhalten. Der Rest dieser Division entspricht der x-Koordinate. Man kann also einfach die n Blöcke durchzählen:

for (int i = 0; i < n; i++) {
    int yBlock = i / k;
    int xBlock = i % k;
    int yFeld = yBlock * k;
    int xFeld = xBlock * k;
    // ...