Constraint Programming und Sudokus: 20ms

Sudoku ist in meinen Augen ein eher langweiliges Puzzle, ich steh mehr auf Solitaire. Aber Sudoku eignet sich sehr gut als Beispielproblem für Constraint Programming. Die Regeln sind einfach: Ziffern von 1 bis 9 werden in eine 9x9-Matrix eingefügt, sodass

• in jeder Zeile keine Ziffer doppelt vorkommt
• in jeder Spalte keine Ziffer doppelt vorkommt
• in jeder kleinen 3x3-Submatrix keine Ziffer doppelt vorkommt.

Üblicherweise sind je nach Schwierigkeitsgrad unterschiedlich viele Zahlen vorgegeben, sodass der Lösungsraum beschränkt wird. Bei schwereren Sudokus ist der Lösungsraum so stark beschränkt, dass nur eine Lösung möglich ist.

Bild: CC-BY Tim Psych

Zum Lösen von Sudokus gibt es verschiedene Ansätze, z.B. Backtracking oder auch brute-force Algorithmen. Als Beispiel sei folgender Algorithmus genannt:

 solve(puzzle[][]) {
    if all cells are known:
      return success immediately
    for each unknown cell (x, y):
        for each possible digit 1..9:
            puzzle[x][y] = digit
            if(valid(puzzle)) solve(puzzle)
            puzzle[x][y] = unknown
 }

Dieser rekursive Algorithmus versucht einfach für alle 81 Felder, eine Zahl zu finden, die keine Constraints verletzen. Dabei kostet der Aufruf

 if(valid(puzzle))

nochmal erheblich Rechenzeit, da sowohl Spaltenconstraint als auch Zeilen- und Submatrixconstraint geprüft werden müssen.

Was ist Constraint Programming?

Im Gegensatz zum imperativen Algorithmus oben (“tue A, dann B, dann …”) gehört Constraint Programming (CP) zu den deklarativen Ansätzen, d.h. es werden nur die Anforderungen an eine valide Lösung spezifiziert. Der Lösungsweg wird dann dynamisch durch die Programmierumgebung bestimmt.

Formal kann man ein Constraint Satisfaction Problem (CSP) wie folgt definieren: Gegeben sei eine Menge von n Entscheidungsvariablen x_i. Der zulässige Wertebereich D_i der Entscheidungsvariablen wird die Domäne der Entscheidungsvariable genannt und kann beliebige Symbole (Integer, Reals, oder auch Mengen) enthalten.

Ein Constraint c(x₁, x₂, …, x_n) ist eine Relation, die den Lösungsraum einschränkt. Wenn (x₁, x₂, …, x_n) in S liegt und S eine Untermenge von D₁ x … x D_n ist, dann ist der Constraint erfüllt. Üblicherweise wird ein Constraint als Funktion f beschrieben, so dass f(x₁, x₂, …, x_n) = 1 genau dann wenn das Constraint erfüllt ist. Ein Constraint Satisfaction Problem (CSP) kann man nun wie folgt definieren:

Gegeben sind n Domänen D₁ x … x D_n und m Constraints f₁, …, f_m. Eine Lösung (x₁, x₂, …, x_n) erfüllt

• f(x₁, x₂, …, x_n) = 1 für 1 ≤ k ≤ m
• x_j ist Element von D_j für 1 ≤ j ≤ n

Um aus einem CSP ein Optimierungsproblem zu formulieren kann man natürlich noch eine Zielfunktion hinzufügen, z.B.

• Minimize/Maximize g(x₁, x₂, …, x_n)

Man sieht: Die Anforderungen an eine Lösung sind sehr flexibel und können quasi alles abbilden. Das Schöne an Constraint Programming: Es ist eine eigenständige Disziplin und hat viele Bibliotheken hervorgebracht. Effektiv kann man also sein Problem beschreiben und die Bibliothek den Rest machen lassen. Insbesondere für sich ändernde Problemstellungen ist diese Methode praktisch. Eine weitergehende Einführung in Constraint Programming ist in Lustig/Puget, “Program Does Not Equal Program” zu finden.

Sudoku als CSP

Zurück zum Sudoku: Die eingangs beschriebenen Restriktionen für eine korrekte Lösung lassen sich direkt in Constraints für einen CSP-Solver übersetzen. Dabei unterstützen viele Solver den Benutzer mit vorgefertigten, mächtigen Constraints. Ein Beispiel dafür ist das alldifferent-Constraint, mit dem man schnell beschreiben kann, dass alle Elemente in einer Menge unterschiedliche Werte haben sollen. Das Constraint ist quasi für Sudoku gemacht.

Mein Code für einen einfachen CSP-basierten Sudokusolver ist auf Github (gonium/sudoku) zu finden. Ich benutze die C++-Solverbibliothek gecode, d.h. diese muss installiert sein, bevor der Code übersetzt werden kann. Ein einfaches

 $ make

sollte das Binary build/src/sudokusolve erzeugen. Ein Aufruf sieht so aus:

 $ ./build/src/sudokusolve
 Setup - Using this sudoku:
  9 0 0 1 0 4 0 0 2
  0 8 0 0 6 0 0 7 0
  0 0 0 0 0 0 0 0 0
  4 0 0 0 0 0 0 0 1
  0 7 0 0 0 0 0 3 0
  3 0 0 0 0 0 0 0 7
  0 0 0 0 0 0 0 0 0
  0 3 0 0 7 0 0 8 0
  1 0 0 2 0 9 0 0 4
 Setup - row constraints
 Setup - column constraints
 Setup - square constraints
   9 5 7 1 8 4 3 6 2 
   2 8 1 9 6 3 4 7 5 
   6 4 3 7 2 5 1 9 8 
   4 9 6 3 5 7 8 2 1 
   8 7 5 4 1 2 9 3 6 
   3 1 2 8 9 6 5 4 7 
   7 2 9 5 4 8 6 1 3 
   5 3 4 6 7 1 2 8 9 
   1 6 8 2 3 9 7 5 4 

Das hier verwendete Sudoku ist fest einkompiliert (hey, das hier ist nur ein Proof of Concept!). Es handelt sich dabei um die Instanz “Star Burst Leo”, von der bekannt ist, dass sie nur eine Lösung besitzt. Die Laufzeit für den Solver beträgt auf meinem Notebook ca. 20ms - nicht schlecht für eine fast automatische Methode. Der Solveraufruf in src/sudokusolve.cpp sieht so aus:

 SudokuSolver* s = new SudokuSolver(star_burst_leo);
 Gecode::DFS<SudokuSolver> e(s);
 delete s;
 while (SudokuSolver* result = e.next()) {
   result->print(std::cout);
   delete result;
 }

Nice and clean. Die while-Schleife gibt einfach alle gefundenen Lösungen aus — diese Instanz hat jedoch nur eine. Der Solver verbirgt sich hinter Gecode::DFS. Dies ist ein generischer Solver, der eine Depth-First-Search benutzt. In der Klasse SudokuSolver wird das CSP formuliert. Aus lib/sudokusolver.cpp:

 std::cout << "Setup - Using this sudoku:" 
 for (int i=0; i<9; i++){
   for (int j=0; j<9; j++) {
     int v = sudokuproblem[i*9 + j];
     std::cout << " " << v;
     if (v != 0)
       rel(*this, m(j,i), IRT_EQ, v );
   }
   std::cout << std::endl;
 }
 std::cout << "Setup - row constraints" 
 for(int i=0; i<9; i++)
   distinct(*this, m.row(i));
 std::cout << "Setup - column constraints" 
 for(int i=0; i<9; i++)
   distinct(*this, m.col(i));
 std::cout << "Setup - square constraints"
 for(int i=0; i<9; i+=3)
   for(int j=0; j<9; j+=3)
     distinct(*this, m.slice(i, i+3, j, j+3));

Im ersten Teil wird das Sudoku ausgelesen und als einzelne Constraints in den Solver übernommen:

 rel(*this, m(j,i), IRT_EQ, v );

Sprich: An der Stelle (i,j) des Sudokus muss der Wert v (aus der Problemstellung) stehen. Ähnlich funktioniert auch das Setup der anderen Constraints, wobei hier der Constraint distinct benutzt wird. Das — sehr lesbare — Handbuch zu gecode liefert hier mehr Informationen.

Fazit

Constraint Programming ist IMHO eine sehr interessante und mächtige Technik. Wenn es um Fahrplanplanung oder Raumzuweisungen geht, kann Constraint Programming genau das richtige sein. In meinem kleinen Sudoku-Experiment funktioniert CP sowohl einfach als auch schnell.

Das bedeutet allerdings nicht, das CP für alle Probleme geeignet ist. Hier muss man im Einzelfall entscheiden. Dazu kommt, dass eventuell andere Algorithmen bessere Performance liefern. Wie immer: It depends. Einen Blick ist CP in jedem Fall wert.

Weiterführende Ressourcen

• Lustig/Puget, “Program Does Not Equal Program”
• Minion ist eine einfache Programmierumgebung für CP.
• Gecode Homepage. Das Handbuch ist empfehlenswert.

Ähnliche Artikel