¶ Einleitung
Sudoku ist ein Logikrätsel auf einem -Gitter mit insgesamt Feldern, das in neun kleinere -Blöcke unterteilt ist. Ziel ist es, das Gitter mit den Ziffern bis so zu füllen, dass in jeder Zeile, jeder Spalte und jedem Block jede Zahl genau einmal vorkommt. Als Ausgangspunkt ist ein Gitter vorgegeben, in dem bereits mehrere Ziffern eingetragen sind, um sicherzustellen, dass das Rätsel genau eine Lösung hat.[1]
Trotz der einfachen Regeln ist die zugrunde liegende Struktur komplex. Für das klassische -Sudoku existieren über
() verschiedene vollständig ausgefüllte gültige Gitter. Die Größe dieses Zustandsraums macht Sudoku zu einem interessanten und herausfordernden Constraint-Satisfaction-Problem (CSP).[1:1] Ein naiver Backtracking-Algorithmus, der alle möglichen Belegungen ausprobiert, wäre wegen des exponentiell wachsenden Suchraums rechnerisch sehr teuer. Stattdessen kommen intelligentere Verfahren zum Einsatz, etwa Backtracking-Suche in Kombination mit Constraint-Propagation (z.B. Forward Checking) sowie Heuristiken wie Minimum Remaining Values (MRV) und Least Constraining Value (LCV).[2]
¶ Sudoku als Constraint-Satisfaction-Problem (CSP)
Formal lässt sich ein Sudoku als Constraint-Satisfaction-Problem (CSP) modellieren. Sei die Menge der Zeilen- und Spaltenindizes. Für jede Position wird eine Variable definiert, die den Wert in der entsprechenden Zelle beschreibt. Die Domäne jeder Variablen ist zunächst . Für vorgegebene Felder wird die Domäne auf den jeweiligen Startwert eingeschränkt.[2:1]
Die Sudoku-Regeln werden durch Constraints ausgedrückt:
- Zeilen-Constraints: In jeder Zeile müssen die Variablen paarweise verschiedene Werte annehmen.
- Spalten-Constraints: In jeder Spalte müssen die Variablen paarweise verschiedene Werte annehmen.
- Block-Constraints: In jedem -Block mit (entspricht den Blöcken oben links, oben Mitte, …) müssen alle Variablen in ebenfalls paarweise verschieden sein.
Dieses CSP-Modell bildet die Grundlage für die in den folgenden Abschnitten betrachteten Lösungsverfahren, bei denen Backtracking durch Constraint-Propagation und geeignete Heuristiken deutlich effizienter wird.[2:2]
¶ Backtracking-Algorithmus
¶ Grundprinzip
Der Backtracking-Algorithmus ist der einfachste Ansatz, um ein Sudoku zu lösen. Der Algorithmus besucht alle freien Zellen in einer bestimmten Reihenfolge und füllt diese systematisch mit einer Zahl von bis und prüft diese nach jedem Eintrag auf ihre Gültigkeit. Falls eine Zelle keine Kandidaten zur Verfügung hat, springt der Algorithmus eine Zelle zurück (backtracked) und ändert die Zahl der vorherigen Zelle.[3]
Auf diese Weise wird der Suchraum als Tiefensuche systematisch durchlaufen, bis entweder alle Zellen gültig gefüllt sind (Lösung gefunden) oder alle Möglichkeiten verworfen wurden (keine Lösung für die gegebene Instanz). Da alle möglichen Belegungen der freien Felder betrachtet werden, ist der Algorithmus vollständig. Existiert eine Lösung, wird sie vom Backtracking-Verfahren garantiert gefunden (unter Umständen nach sehr langer Laufzeit). Im schlechtesten Fall wächst die Laufzeit von Tiefensuche und damit auch von Backtracking exponentiell mit der Größe des Suchraums. Backtracking eignet sich daher vor allem für Probleme, bei denen der Suchbaum vergleichsweise klein bleibt. Es gibt jedoch Möglichkeiten, die Laufzeit eines Backtracking-Algorithmus zu verringern, etwa durch den Einsatz geeigneter Heuristiken.[4]
¶ Implementierung
Der folgende Pseudocode illustriert die reine rekursive Backtracking-Logik für Sudoku.
Eingabe: Ein -Gitter mit einigen vorgegebenen Werten (Ziffern ) und Nullen an den Stellen, die noch leer sind.
Ausgabe: Entweder ein vollständig gelöstes Gitter , in dem alle Zellen gültig belegt sind, oder das Ergebnis "keine Lösung", falls das gegebene Rätsel nicht vervollständigt werden kann. Dabei sind und die Zeilen- bzw. Spaltenindizes (von bis ), sodass die Zelle in Zeile und Spalte bezeichnet.
function SOLVE(G)
for r ← 0 to 8 do
for c ← 0 to 8 do
if G[r][c] = 0 then
for num ← 1 to 9 do
if ISVALID(G, r, c, num) then
G[r][c] ← num
if SOLVE(G) then
return True
end if
G[r][c] ← 0 // Backtrack
end if
end for
return False // keine Zahl passt in diese Zelle
end if
end for
end for
return True // kein leeres Feld mehr → gelöst
end function
Pseudocode übernommen aus [3:1].
Bhattarai et al. geben für das Backtracking-Verfahren im Mittel (nach ihrer Analyse) eine Zeitkomplexität von
an.[3:2]
¶ Optimierungen des Backtracking-Verfahrens
¶ Forward Checking
Forward Checking ist eine Erweiterung des Backtracking-Verfahrens. Für jede noch nicht belegte Zelle wird eine Menge von zulässigen Kandidatenwerten verwaltet, die mit den bisher eingetragenen Zahlen verträglich sind. Trägt der Algorithmus eine Zahl in eine Zelle ein, werden in allen Zellen derselben Zeile, Spalte und desselben -Blocks diese Zahl sofort aus der jeweiligen Kandidatenliste entfernt. Damit werden Werte, die sicher zu einem Konflikt führen würden, gar nicht erst ausprobiert.[1:2]
Dieses Vorgehen hat zwei wichtige Effekte. Zum einen werden nur noch Werte getestet, die nicht direkt im Widerspruch zu bereits gesetzten Zahlen stehen. Zum anderen können Widersprüche früh erkannt werden. Wenn die Kandidatenliste einer Zelle leer wird, ist klar, dass der aktuelle Suchpfad keine Lösung mehr liefern kann – der Algorithmus bricht diesen Pfad sofort ab und backtracked, statt noch mehrere Ebenen tiefer zu suchen.[1:3]
In Abb. 3 ist ein kleines -Sudoku-ähnliches Beispielpuzzle dargestellt. Die Suche wählt das grau markierte Feld als nächste Variable und testet dort den Wert .
Beim Forward Checking wird nach dieser Zuweisung nicht unmittelbar weitergesucht, sondern zunächst die Auswirkung auf die Nachbarzellen überprüft. In allen Feldern derselben Zeile, Spalte und Block wird die sofort aus den Kandidatenmengen entfernt. Anschließend kontrolliert der Algorithmus, ob jede dieser Nachbarzellen noch mindestens einen möglichen Wert besitzt.
Keine dieser Nachbarzellen hat die mehr als Kandidaten, aber alle Zellen verfügen weiterhin über mindestens einen zulässigen Wert. Forward Checking erkennt hier zunächst keinen Konflikt. Erst wenn im nächsten Schritt unter die eine eingetragen wird, greift Forward Checking erneut ein. Die wird aus der Kandidatenliste der übrigen Zellen in derselben Spalte entfernt, insbesondere aus der linken unteren Zelle. Da diese Zelle danach keine zulässigen Kandidaten mehr hat, wird ein Konflikt erkannt und der aktuelle Suchpfad verworfen.
¶ Minimum Remaining Value (MRV)
Die Minimum-Remaining-Values-Heuristik (MRV) ist eine Strategie zur Wahl der nächsten Zelle, die im Backtracking belegt werden soll. Anstatt einfach die erste freie Zelle zu nehmen, wählt der Algorithmus immer diejenige Zelle, die aktuell am wenigsten zulässige Kandidaten besitzt – also die "am stärksten eingeschränkte" Variable. In einem Sudoku mit expliziten Kandidatenlisten bedeutet dies, dass unter allen noch leeren Feldern genau das Feld ausgewählt wird, dessen Kandidatenmenge die kleinste Größe besitzt.[1:4]
In Abb. 4 haben in einem -Beispielpuzzle zwei grau markierte Felder jeweils nur zwei mögliche Werte, alle anderen leeren Felder jedoch drei.
Die MRV-Heuristik wählt dann eines der Felder mit nur zwei Kandidaten. Dadurch verzweigt der Suchbaum nur in zwei statt drei Richtungen – der Suchraum schrumpft ungefähr um den Faktor .[1:5]
¶ Least Constraining Value (LCV)
Die Least-Constraining-Value-Heuristik (LCV) beeinflusst in welcher Reihenfolge die möglichen Werte für eine bereits ausgewählte Zelle ausprobiert werden. Die Idee ist, unter allen zulässigen Kandidaten zunächst den Wert zu wählen, der die übrigen noch ungefüllten Zellen am wenigsten einschränkt. Für eine freie Zelle werden alle aktuell erlaubten Zahlen betrachtet und und für jeden Kandidaten wird abgeschätzt, wie viele Möglichkeiten in den Nachbarzellen (gleiche Zeile, Spalte, Block) dadurch wegfallen würden. Bevorzugt wird dann der Wert, der in der Summe die wenigsten Kandidaten bei den Nachbarzellen eliminiert.[2:3]
In Abb. 5 ist die grau markierte Zelle in der ersten Zeile und zweiten Spalte hervorgehoben.
Für ein -Sudoku mit den Zahlen bleiben nach Anwendung der Zeilen-, Spalten- und Blockregeln für nur noch die Werte und als Kandidaten übrig:
Für die noch leeren Nachbarzellen (gleiche Zeile, Spalte oder Block) erhalten wir zunächst die folgenden Kandidatenmengen. Dabei bezeichnet die Kandidatenmenge der Zelle in Zeile und Spalte :
Zur Illustration der LCV-Heuristik werden die Auswirkungen der beiden möglichen Werte für miteinander verglichen:
- Falls , wird der Wert aus allen Domänen der Nachbarzellen entfernt:
Insgesamt werden dabei fünf Kandidatenwerte gestrichen.
- Falls , wird der Wert entfernt:
Hier werden insgesamt nur vier Kandidatenwerte gestrichen.
Da die Wahl die Nachbarzellen weniger stark einschränkt, bevorzugt die LCV-Heuristik in diesem Beispiel den Wert für die grau markierte Zelle .
¶ Heuristikbasierter Solver (MRV + LCV)
Bhattarai et al. beschreiben einen heuristikbasierten Sudoku-Solver, der die Suche durch zwei Heuristiken steuert. Minimum Remaining Values (MRV) zur Wahl der nächsten Zelle und Least Constraining Value (LCV) zur Reihenfolge, in der die Kandidatenwerte ausprobiert werden. Grundlage ist eine Datenstruktur possibilities, die für jede noch leere Zelle die aktuell zulässigen Kandidaten speichert. Diese Kandidatenmengen werden initialisiert, indem aus Zeile, Spalte und Block bereits bekannte Zahlen entfernt werden.[3:3]
¶ Zeitkomplexität und heuristische Kostenfunktion
Die Zeitkomplexität des heuristikbasierten Ansatzes zur Lösung eines Sudoku-Rätsels liegt nahezu in polynomieller Zeit.[3:4]
Zur Bewertung eines partiell ausgefüllten Sudoku-Zustands definieren die Autoren eine heuristische Kostenfunktion der Form
die die geschätzten Gesamtkosten angibt. Dabei quantifiziert den bereits erreichten Belegungsgrad (Anzahl der bereits festgelegten Zellen), während die verbleibende Suchkomplexität über die noch möglichen Kandidatenwerte der offenen Zellen abschätzt.[3:5]
In ihrem Ansatz werden diese Terme wie folgt spezifiziert:
wobei die Anzahl der aktuell noch leeren Zellen ist.
Für den heuristischen Anteil verwenden sie
wobei die Menge der zulässigen Kandidatenwerte der Zelle bezeichnet.
Damit ergibt sich insgesamt
¶ Ergebnisse
Zur Bewertung der beiden Lösungsansätze – Backtracking und dem heuristikbasierten Solver (MRV + LCV) – wurden beide Algorithmen auf insgesamt 500 Sudoku-Rätseln getestet, verteilt auf fünf Schwierigkeitsstufen (Beginner, Easy, Medium, Hard und Expert). Für jede Stufe wurde die durchschnittliche Lösungszeit in Millisekunden erfasst und im folgenden Diagramm zusammengefasst.[3:6]
Die Auswertung zeigt, dass mit zunehmender Schwierigkeit der Leistungsunterschied zwischen beiden Methoden größer wird. Besonders deutlich wird dies beim Vergleich der Verhältnisse der durchschnittlichen Laufzeiten. Dabei wird rekursives Backtracking von der heuristischen Methode in allen getesteten Kategorien übertroffen. Der heuristikbasierte Ansatz ist bei schwierigeren Sudokus zunehmend im Vorteil. Gleichzeitig bleibt die heuristische Methode über alle Schwierigkeitsstufen hinweg konsistent effizient.[3:7]
¶ Referenzen
¶ Abbildungen
- Abb. 1: Wikimedia Commons – "Sudoku_problem_1.svg"
- Abb. 2: Wikimedia Commons – "Sudoku_solved_by_bactracking.gif"
- Abb. 3: Schermerhorn (2015), S. 5
- Abb. 4: Schermerhorn (2015), S. 6
- Abb. 5: Eigene Darstellung (erstellt mit ChatGPT)
- Abb. 6: Bhattarai et al. (2025), S. 11
¶ Literatur
Schermerhorn, M. (2015). A Sudoku Solver. pdf ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
Nair, R. R., Kishore, S., Joseph, S., Divyashree, N. R., & Sharma, N. (2025, June). Constraint Propagation Techniques for Efficient Sudoku Solvers. In 2025 International Conference on Emerging Technologies in Computing and Communication (ETCC) (pp. 1-5). IEEE. url | pdf ↩︎ ↩︎ ↩︎ ↩︎
Bhattarai, A., Uprety, D., Pathak, P., Shrestha, S. N., Narkarmi, S., & Sigdel, S. (2025). A Study Of Sudoku Solving Algorithms: Backtracking and Heuristic. arXiv preprint arXiv:2507.09708. url | pdf ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
Seite „Backtracking“. In: Wikipedia – Die freie Enzyklopädie. Bearbeitungsstand: 16. Februar 2025, 05:59 UTC. url ↩︎