Sudoku per Backtracking Lösen


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…

#include <iostream>
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.

  1. Bisher keine Kommentare.
(wird nicht veröffentlicht)

  1. Bisher keine Trackbacks.