Backtracking
Alle bisher vorgestellten Verfahren funktionieren um so besser, je mehr Zahlen vorgegeben sind.
Tatsächlich lässt sich jedes Sudoku damit lösen, solange man bei der mehrstufigen Logik weit genug denkt.
Wenn man ein Computerprogramm schreiben will, dass Sudoku löst (wie z.B. YaSSS (Yet another (Simple|Stupid) Sudoku Solver), so ist es sehr aufwändig und Fehleranfällig eine mehrstufige Logik zu programmieren.
Für Computer bietet sich ein anderes Vorgehen an, das so genannte Backtracking. Das ist nur eine hochtrabende Bezeichnung für Ausprobieren und Fehler erkennen.
Im einzelnen funktioniert das so: wenn man nicht weiter weiß, sucht man sich eine Stelle, an der es nur wenige Möglichkeiten gibt, und rät. Dabei merkt man sich aber, dass man geraten hat. Dann versucht man, das Sudoku mit der geratenen Zahl zu lösen. Solange man kann, probiert man es ohne raten, wenn man nicht weiter kommt, rät man eben wieder.
Irgendwann kommt man dann zu dem Punkt, an dem man erkennt, dass man entweder eine richtige Lösung findet, oder dass das Rätsel nicht lösbar ist, man also falsch geraten hat.
Hat man richtig geraten, ist man am Ziel und glücklich.
Hat man falsch geraten, nimmt man alles zurück, was man seit dem letzten Mal raten getan hat, und rät anders. Damit man sicher zum Erfolg kommt, muss man natürlich alle Möglichkeiten durchprobieren, d.h. man muss sich merken (oder eher aufschreiben), wann man was geraten hat.
Um ein Sudoku auf diese Art von Hand zu lösen bräuchte man viel Zeit. Vor allem aber ist es frustrierend, da man sich ganz am Anfang schon irren kann, und alles, was man danach gemacht hat, scheinbar sinnlos war.
Aber auf dem Computer geht dieses Verfahren recht schnell. Für den Computer ist es sehr einfach, ein Sudoku, das sich bereits im Arbeitsspeicher befindet, zu kopieren, und dann mit der Kopie weiter zu probieren.
Ein halbwegs aktuelle Computer kann mit den richtigen Programmen mehrere richtig schwere Sudoku pro Sekunde lösen, einfache gehen noch sehr viel schneller.
Mehr über das Lösen von Sudokus mit Backtracking, erstellen von Sudokus und Codebeispiele gibt es auf der Projektseite von YasSS, meinem Sudoku-Löser