Sodukos lassen sich durch Anwendung des Backtrackings lösen. Dabei werden die Lücken systematisch mit den Ziffern 1 bis 9 gefüllt. Passt die Ziffer hinein, wird mit dem nächsten Feld fortgefahren. Kann keine Ziffer hinzugefügt werden, geht man zum vorherigen Feld zurück und versucht dort die nächste Ziffer. Insgesamt benötigt man mit Backtracking 1038 Schritte, um dieses Sudoku zu lösen. Das Video illustriert dabei, welche Felder getestet werden.
Quellcode
Den Quellcode werde ich hier nicht veröffentlichen, da dieses Problem eine gute Programmierübung ist. Hier jedoch einige Hinweise:
Rekursion
Backtracking ist rekursiv. Damit muss auch hier gearbeitet werden. Man kann sicher auch mit Schleifen arbeiten, aber das ist äußerst komplex.
Deep-Copies notwendig
Bei Referenzen von Feldern in Python muss man vorsichtig sein. Zeile 2 des folgenden Codes erstellt keine Kopie von a, vielmehr referenziert b nur auf a. D.h., eine Veränderung in b führt auch zu Änderungen in a.
a = [1,2,3] b = a b[0]=1000 print(a) # Ausgabe: [1000,2,3]
Daher ist es nötig, immer wieder so genannte Deep-Copies anzufertigen, d.h., durch Auslesung der einzelnen Elemente die Kopie immer wieder neu aufzubauen. Es gibt dafür fertige Routinen in Python, aber eigentlich ist das auch schnell selbst geschrieben.
Zwei Rückgabewerte
In meiner Lösung geben die Funktionen immer zwei Werte zurück: Ein Feld und einen Wert der anzeigt, ob der das zurückgegebene Feld die Lösung ist. So können die Lösungen dann ausgelesen werden:
feld, success = versucheLoesung(...)