In einer Diskussion in der Wikipedia zum Artikel Sudoku behauptete einst ein Mitautor, ein Sudoku wäre nicht in überschaubarer Zeit mit der Backtracking-Methode zu lösen. Als Zweifel daran geäußert wurden, bestand er darauf, „dass sich 30 Informatikstudenten im Hauptstudium plus ein Dozent sich nicht alle derart gewaltig irren.“ Daraufhin habe ich das Ganze einfach programmiert.
Backtracking ist das stumpfe Durchprobieren von Möglichkeiten, solange sie noch zu einer Lösung führen können. Für Sudoku bedeutet das, dass man das erste freie Feld mit einer 1 füllt, und dann schaut, ob sich Widersprüche ergeben. Wenn nein, füllt man das nächste freie Feld mit einer 1. Sobald ein Widerspruch auftritt (zum Beispiel zwei Einsen in einer Zeile…) probiert man die 2. Wenn man für ein Feld alle Ziffern ausprobiert hat und alle zu Widersprüchen führen, löscht man es wieder, geht ein Feld zurück und zählt dessen Ziffer eins hoch, probiert also zum Beispiel dort die 2.
Das Ergebnis war, dass ein Sudoku aus der Zeitung per Backtracking auch mit damaligen Rechnern (2005) schon in einer Sekunde gelöst werden konnte. Ich habe dann noch per Google den Uni-Assistenten ausfindig gemacht, der behauptet hatte, dass das unmöglich wäre. Er war überrascht, hat die Anregung aber dankbar aufgenommen.
Und hier der Code…
using namespace std;
int start[9][9] =
{
{ 2, 4, 0, 0, 9, 0, 0, 0, 0 },
{ 5, 1, 0, 0, 0, 3, 4, 0, 9 },
{ 0, 0, 0, 0, 6, 4, 2, 8, 1 },
{ 0, 0, 0, 3, 0, 8, 1, 0, 0 },
{ 1, 0, 7, 0, 0, 0, 0, 5, 3 },
{ 0, 3, 5, 6, 0, 0, 0, 0, 4 },
{ 0, 5, 1, 7, 0, 0, 0, 0, 2 },
{ 0, 0, 3, 0, 2, 0, 0, 0, 0 },
{ 0, 2, 4, 0, 1, 9, 3, 0, 0 }
};
bool isfine(int feld[9][9], int x, int y)
{
// doppelte Zahl in Zeile oder Spalte?
for (int yi = 0; yi < 9; yi++)
if (yi != y && feld[x][yi] == feld[x][y])
return false;
for (int xi = 0; xi < 9; xi++)
if (xi != x && feld[xi][y] == feld[x][y])
return false;
// Neuner-Kästchen-Test
int x1 = (x / 3) * 3;
int y1 = (y / 3) * 3;
for (int xk = x1; xk < x1 + 3; xk++)
for (int yk = y1; yk < y1 + 3; yk++)
if ((xk!=x || yk!=y) && feld[xk][yk]==feld[x][y])
return false;
return true;
}
bool nextone(int feld[9][9], int x, int y)
{
if (y == 9) { y = 0; x++; };
if (x == 9) return true;
if (feld[x][y] > 0)
{
if (!isfine(feld, x, y)) return false;
return nextone(feld, x, y + 1);
}
else for (feld[x][y] = 1; feld[x][y] <= 9; feld[x][y]++)
{
if (!isfine(feld, x, y)) continue;
if (nextone(feld, x, y + 1)) return true;
}
feld[x][y] = 0;
return false;
}
int main(int argc, char **argv)
{
if (nextone(start, 0, 0))
{
for (int x = 0; x < 9; x++)
{
for (int y = 0; y < 9; y++)
cout << start[x][y];
cout << endl;
}
}
else
cout << „Dieses Rätsel ist nicht lösbar!“ << endl;
return 0;
}
Formatiert mit Quickhighlighter.
Ich habe das Programm in C umgeschrieben, alle int gegen uint8_t getauscht und mein Beispiel auf einem Arduino Uno
laufen lassen:
uint8_t start[9][9] = {
{ 0, 6, 0, 0, 0, 0, 0, 0, 0 },
{ 5, 0, 0, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 2, 0, 0, 0, 4, 0, 5 },
{ 0, 3, 0, 0, 0, 0, 0, 0, 9 },
{ 0, 4, 9, 0, 1, 8, 2, 0, 0 },
{ 0, 0, 0, 6, 0, 0, 8, 0, 0 },
{ 2, 0, 0, 0, 7, 9, 0, 0, 0 },
{ 0, 0, 1, 0, 2, 0, 5, 0, 0 },
{ 0, 5, 6, 0, 0, 0, 0, 0, 4 }
};
Ausgabe mit TimeStamp:
01:38:06.083 -> Programm Start
01:42:17.734 -> 4,6,7,8,3,5,9,1,2,
01:42:17.734 -> 5,9,3,2,4,1,6,8,7,
01:42:17.773 -> 8,1,2,9,6,7,4,3,5,
01:42:17.773 -> 6,3,8,7,5,2,1,4,9,
01:42:17.812 -> 7,4,9,3,1,8,2,5,6,
01:42:17.845 -> 1,2,5,6,9,4,8,7,3,
01:42:17.845 -> 2,8,4,5,7,9,3,6,1,
01:42:17.884 -> 3,7,1,4,2,6,5,9,8,
01:42:17.884 -> 9,5,6,1,8,3,7,2,4,
Das Sudoku hat genau 2 Lösungen.
In Zeile 2 Spalte 8 und 9 sowie in Zeile 4 Spalte 8 und 9 gelöst sind die Ziffern 7 und 9 austauschbar. Lösungsdauer: 0,586 s.
Genau das ist der Sinn eines guten Algorithmus, auch nicht lösbare Sudokus als solche zu erkennen. Mit dem Kandidatenstreichverfahren ist das sehr schnell ermittelbar, wenn Felder ohne Kandidaten entstehen. Backtracking hingegen scheitert hier. Das mag für simple Sudokus reichen, nicht aber, wenn man eigene Sudokus mit weiteren Bedingungen erweitert und bei dennen man sehen möchte, ob es lösbar ist bzw. bleibt, denn auch keine Lösung ist eine Lösung im Sinne von, so geht es nicht. Z.B. sind zwei ineinander geschachtelte Sudokus (eines um 45 Grad gedreht) nicht lösbar, das ist mit Brain 1.0 sehr schnell bewiesen (5 gemeinsam abhängige Zahlen, bei nur 4 Freiheitsgraden), Backtracking hingegen würde x-Jahre rechnen und rechnen und könnte keine Aussage treffen, ob das Problem lösbar ist oder nicht, denn es könnte ja rein theoretisch eine Lösung gegeben und nicht jeder erkennt es auch so.
Ich bin ueber wikipedia auf deine Seite gestossen. Vor einiger Zeit hatte ich eine recht aehnliche Loesung programmiert. Es gibt aber durchaus Sudokus, fuer welche solch ein Ansatz zu lange dauert: http://norvig.com/sudoku.html
Z.B.:
. . . |. . 5 |. 8 .
. . . |6 . 1 |. 4 3
. . . |. . . |. . .
——+——+——
. 1 . |5 . . |. . .
. . . |1 . 6 |. . .
3 . . |. . . |. . 5
——+——+——
5 3 . |. . . |. 6 1
. . . |. . . |. . 4
. . . |. . . |. . .
Ich hab das Puzzle probiert – und nach ein paar Minuten ergebnislos abgebrochen. Dann hab ich es mal um 90 Grad gedreht, in der Vermutung, dass es dann per Backtracking leicht zu lösen ist:
{ 0, 3, 0, 0, 0, 5, 1, 4, 0 },
{ 8, 4, 0, 0, 0, 0, 6, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 5, 1, 0, 0, 6, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 6, 0, 5, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 3, 0, 0 },
{ 0, 0, 0, 0, 0, 3, 5, 0, 0 }
Wenn ich beim Drehen nicht falsch gemacht hab, ist das aber gar nicht zu lösen. Das passt zu dem, was über dem Puzzle auf der Webseite steht („impossible puzzle“), und ein Kommentar dort bestätigt das auch.
Ich hab mir dann mal das „hardest (for my program)“ genommen, und als das nach 0,13 Sekunden fertig war, es auf den Kopf gestellt, sodass die ersten beiden Zeilen komplett leer waren. Das war nach 0,15 Sekunden gelöst.
Also… du hast mich tatsächlich verunsichert. Vielleicht bin ich da über’s Ziel hinausgeschossen, das Ergebnis von ein paar Sudokus auf alle auszudehnen. Ich hab das lösbare Sudoku, an dem der Algorithmus scheitert, aber noch nicht gesehen. Ich müsste den Test wohl automatisieren, wie der Autor des verlinkten Werks es getan hat…
Aber wieso hast du abgebrochen? Dein Proggy hätte doch „Dieses Rätsel ist nicht lösbar“ ausspuken müssen, oder lese ich das falsch?
Nachdem ich gesehen hatte, dass es nicht in einer Minute gelöst ist, wollte ich erstmal kucken, ob es überhaupt lösbar ist. Deshalb hab ich’s gedreht und geh davon aus, dass man beim Original dieselbe Nicht-Lösung erhalten würde. Dass das lange dauert, ist aber nicht so interessant, die vergebliche Suche ist eigentlich immer die langwierigste. Ich kann’s ja nochmal einen Tag durchlaufen lassen, aber Jahrmillionen hab ich leider nicht zur Verfügung… ;)