Frage zu Sudoku

[cz3kit]

Nabend,
ich habe gerade ein Problem. Ich programmiere einen Sudoku Generator. Der soll einfach nur ein ausgefülltes Feld erstellen, ohne dabei die Regeln zu brechen. Dazu verwende ich ein 2 Dimensionles Array.

Ich bin gerade an der Stelle um so eine Box zu überprüfen, also das die Zahlen von 1 bis 9 nur einmal in so einer 3x3 Box vorkommen dürfen.

Jetzt ist die Frage wie kann ich das bei einer 2D Array am besten machen? Ich könnte ja if und else Abfragen machen mit den Koordinaten, aber das finde ich nicht gerade schön und ist eher so eine einfache Lösung. Wüsste jemand wie man vielleicht sowas berechnen kann, z.B. um an die Koordinaten von dem Fels oben Links solch einer Box zu kommen??

MfG

cz3kit

 

[Mujahiddin]

du könntest ja in einem 3x3 Großfeld, wovon jedes Feld in 3x3 Feldern unterteilt ist, erstellen...
Jedes Feld in so einem 3x3 Feld hat dann einen Index...
also Feld 1x1 ist ArrayList[0][0], 1x2 [0][1] ... 3x3 = [0][8]
Ich verstehe nur nicht, was das Problem an einer if abfrage sein soll...
du kannst doch jede zahl auf alle anderen bisher existenten zahlen prüfen, und wenn die übereinstimmt, wird eine neue zahl generiert und die mit einer anderen identischen zahl verworfen...
das wäre ne einfache lösung, ne andere fällt mir grad nich ein.
Ich hoffe, du kannst was damit anfangen.
Machs gut

 

[Marco13]

Ich verstehe nur nicht, was das Problem an einer if abfrage sein soll...

Das Problem ist vielleicht, dass man hier schon gelegentlich mal sieht, dass Leute if-Abfragen zu sowas schreiben (einige, deren Namen ich nicht erwähnen möchte, haben sich für solche Sachen sogar schon "Codegeneratoren" geschrieben)...

In einer Schleife kann man (getrennt, oder nebenbei) überprüfen, ob in diesen 9 Feldern NUR Zahlen zwischen 1 und 9 stehen. WENN das so ist, dann müssen auch ALLE Zahlen zwischen 1 und 9 vorkommen. Wenn eine fehlt, ist eine andere doppelt - und umgekehrt. Um das zu überprüfen könnte man sich 1000 Lösungen überlegen, von einer HashSet bis zu bitweisen Operatoren, alle unterschiedlich effizient...

class SudokuTest
{
    public static void main(String args[])
    {
        int a[][] = new int[9][9];


        a[0][0] = 1;
        a[0][1] = 2;
        a[0][2] = 3;
        a[1][0] = 4;
        a[1][1] = 5;
        a[1][2] = 6;
        a[2][0] = 7;
        a[2][1] = 8;
        a[2][2] = 9;

        System.out.println(isValid(a,0,0));
        System.out.println(isValid(a,1,1));
        System.out.println(isValid(a,2,2));
    }

    private static boolean isValid(int a[][], int x, int y)
    {
        int bits = 0;
        for (int i=0; i<3; i++)
        {
            for (int j=0; j<3; j++)
            {
                bits |= (1<<a[x*3+i][y*3+j]);
            }
        }
        return bits == 0x3FE;
    }
}

EDIT: Hey da kommt wirklich kein if drin vor?!

 

[Landei]

ungetestet:

Set<Integer> set = new HashSet<Integer>(); 
for(int offset = 0; offset < 9; offset++) {
   set.clear();
   for(int box = 0; box < 9; box++) {
       int x = box % 3 + 3 * (offset % 3);
       int y = box / 3 + 3 * (offset / 3);
       int value = sudoku[x][y];
       if(value > 0) {
           if(set.contains(value)) {
               System.out.println("Multiple value " + value + " at " + x + ":" + y);
           }
           set.add(value);
       }  
   }
}

 

[cz3kit]

Ich hab als erstes überlegt, dass ich vielleicht eine HashTable anlege und dort die Koordinaten aus der linken oberen Ecke einer Box hinterlege, also so in etwa:

Box 0,0 0,1 0,2
1,0 1,1 1,2
2,0 2,1 2,2

{0: (0,0), 1: (0,3), usw.}

Sowas war meine Idee so mitten in der Nacht, was haltet ihr davon??

Aber die Idee von Landei finde ich auhc sehr interessant.

 

[Marco13]

Wie schon gesagt, gibt es dafür beliebig viele mögliche Lösungen... Ich versuche tendenziell eher effiziente und kompakte Lösungen zu finden (jaaa, manchmal auch "schön" oder "bequem", je nach dem, worum es geht ) aber eben i.a. nur das zu berechnen oder zu speichern, was man wirklich braucht.

Eine Map "Zahl -> Gitterposition" würde natürlich funktionieren, genau wie eine "Set<Zahl>". Rein ""informationstheoretisch"" braucht man aber dieses Mapping nicht, und man braucht auch nicht so was komplexes wie ein HashSet, wenn es prinzipbedingt genau um die Zahlen von 1 bis 9 geht. Ein Array wäre vielleicht noch eine Alternative zu den "bitmustern", aber ... das war eher Spielerei.

 

[cz3kit]

Hmm naja okej danke, ich werde mir die Lösung mal genau anschauen und gucken was am besten passt. Ich danke euch für die gute Hilfe.

 

[function]

Was mir da so einfällt in sachen sudoko generator, ich würde ihn nicht "box"-weise erstellen, sondern zeilen oder spaltenweise und zwar so in die richtung:
1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 1
3 4 5 6 7 8 9 1 2 ....

damit hat man schonmal ein valides standard sudoku um damit man nun eine große vielfalt bekommt kann man nun einiges durch einander mischen, regeln fürs mischen sind dabei:
belieg tauschbar sind:
die zeilen 1-3; 4-6; 7-9;
die spalten 1-3; 4-6; 7-9;
und die jeweiligen "box" spalten u. zeilen.

eine weitere variation kann man erzeugen, in dem man nicht bei der standard belegung bei 1 startet sondern bei einer anderen zahl...

dadurch erspart man sich jegliche validitäts prüfung, weil durch dieses tauschen nur mögliche sudokus erzeugt werden können.

 

[eRaaaa]

ich würde ihn nicht "box"-weise erstellen, sondern zeilen oder spaltenweise und zwar so in die richtung:
1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 1
3 4 5 6 7 8 9 1 2 ....

damit hat man schonmal ein valides standard sudoku

Ähm, bist du dir da sicher? Also ich bin kein Sudoku-Spieler, aber wenn das jetzt eine 3x3 Feld ist, wäre ja in dem erstem Feld schon

1 2 3
2 3 4
3 4 5

Was ja nicht so valide ist oder? ;D (2 x 2, 3 x 3, 2 x 4)
Muss nicht eher Blockweise verschoben werden? Also immer im 3er Block:

1 2 3 4 5 6 7 8 9
7 8 9 1 2 3 4 5 6
4 5 6 7 8 9 1 2 3

Nu wäre es valide!
Und anschließend könnte man dann die Matrixoperationen anwenden!

 

[Marco13]

Wie würden denn da die unteren zwei 3er-Reihen aussehen? ???:L

EDIT: Die müßten dann wohl um 1 oder 2 nach links rotiert sein (also, die komplette 3er-Reihe)... oder? Hm.

 

[cz3kit]

Was mir da so einfällt in sachen sudoko generator, ich würde ihn nicht "box"-weise erstellen, sondern zeilen oder spaltenweise

ja das mach ich, also ich habe ein array wo die zahlen enthalten sind. Diese wird dann einmal gemischt und ich kann die erste reihe einfach befüllen, horizontal. Danach kommen aber die weiteren Reihen und ich muss ja irgendwie wissen in welcher Box ich mich gerade befinde, damit ich die Zahlen aus dieser Box raussuchen kann und als erledigt markieren kann.

eine weitere variation kann man erzeugen, in dem man nicht bei der standard belegung bei 1 startet sondern bei einer anderen zahl...

Ich versteh nicht so recht wie du das meinst.

 

[eRaaaa]

Wie würden denn da die unteren zwei 3er-Reihen aussehen? ???:L

Mhm, ich würde sagen: Jetzt kommt das verschieben?

1 2 3 4 5 6 7 8 9
7 8 9 1 2 3 4 5 6
4 5 6 7 8 9 1 2 3

9 1 2 3 4 5 6 7 8
6 7 8 9 1 2 3 4 5
3 4 5 6 7 8 9 1 2

8 9 1 2 3 4 5 6 7
5 6 7 8 9 1 2 3 4
2 3 4 5 6 7 8 9 1

Okay und jetzt die Matrixoperationen ;D

 

[function]

oh sry die zahlen müßen natürlich immer um 3 plätze verschoben werden. und dann in der nächsten boxreihe im eine stelle... also:
1 2 3 4 5 6 7 8 9
7 8 9 1 2 3 4 5 6
4 5 6 7 8 9 1 2 3

9 1 2 3 4 5 6 7 8
6 7 8 9 1 2 3 4 5
3 4 5 6 7 8 9 1 2

8 9 1 2 3 4 5 6 7
5 6 7 8 9 1 2 3 4
2 3 4 5 6 7 8 9 1

war grad etwas arg schnell gepostet...

 

[Marco13]

Eigentlich ist sowas ja ganz spanndend ... zu schauen, unter welchen Matrixoperationen gültige Sudokus im algebraischen Sinne vollständig und abgeschlossen sind :reflect: (ZEIT müßte man haben....)

 

[cz3kit]

Ich habe mir gerade Gedanken gemacht wie man am besten so eine Box berechnet und ich bin dabei auf folgende Lösung gestoßen. Jedes Feld hat eine Koordinate, wenn ich die y-Koordinate (Zeile) durch 3 teile und dann die x-Koordinate (Spalte) ebenfalls durch 3 teile, dass aber dann durch 10 teile, bekomm ich die Koordinate solch einer Box heraus. Ein Beispiel:

Die erste Box hat die Koordinate 0,0. Alle Koordinaten der Zellen in der Box sind unter 3, das bedeutet mit der Rechnung würde ich zu dieser Box kommen.

Nehmen wir die nächste Box 0,1. Ich befinde mich z.B. in der Zelle 2,4. Ich teile 2 durch 3, als int und bekomme 0 heraus. Jetzt teile ich 4 durch 3 und bekomme 1 heraus. Jetzt müsste ich die 1 durch 10 teilen, dazu müsste es zu einem double gecastet werden. Das Ergebnis 0,1 wird dan zu dem ersten Ergebnis 0 dazugerechnet, wodurch ich auf 0,1 komme.

 

[Landei]

Ziemlich kompakt:
(ungetestet)

Set<Integer> set = new HashSet<Integer>();
for(int x = 0; x < 9; x++) {
  for(int y = 0; y < 9; y++) {
      if(sudoky[x][y] != 0) {
        int entry = x/3 + 3*(y/3) + 9*sudoky[x][y];
        if(set.contains(entry)) {
           System.out.println("Duplicates"); 
        }
        set.add(entry);
      }
  }
}

[edit] Noch kompakter:

Set<Integer> set = new HashSet<Integer>();
for(int d = 0; d < 81; d++) {
  if(sudoky[d/9][d%9] != 0) {
    int entry = (d/9)/3 + 3*((d%9)/3) + 9*sudoky[d/9][d%9];
    if(set.contains(entry)) {
        System.out.println("Duplicates"); 
    }
    set.add(entry);
  }
}

 

[cz3kit]

int entry = x/3 + 3*(y/3) + 9*sudoky[x][y];

Ich kann diese Rechnung nicht wirklich nachvollziehen.

 

[Landei]

Das sollte eigentlich für jede Block-Zahl-Kombination einen eindeutigen Wert erzeugen, und zwar aus den Block-Koordinaten x/3 und y/3 (daraus wir mit x/3 + 3*(y/3) eine Zahl von 0..8 berechnet) plus der zu überprüfenden Zahl (natürlich mit 9 multipliziert, damit es keine Überschneidungen gibt). Kann man natürlich auch schöner machen (man hätte z.B. auch Strings nach dem Schema "" + x/3 + ":" + y/3 + ":" + sudoku[x][y] bilden können, Hauptsache es ist eindeutig). Wayne interessiert's, wenn's läuft...

 

[cz3kit]

Ahso, okej.

 

[Marco13]

[edit] Noch kompakter:

..
    if(set.contains(entry)) {
        System.out.println("Duplicates"); 
    }
    set.add(entry);
...

NOCH kompakter:

    if(!set.add(entry)) {
        System.out.println("Duplicates"); 
    }

 

[Landei]

Ahh, cool, daran hatte ich gar nicht gedacht!