Gestelltes Problem
Das Sudoku war also prinzipiell gelöst. Es zeigte sich jedoch, dass für manche Rätsel recht viele Kombinationen ausprobiert werden mussten. Bei einem Rätsel waren es 45253, was für die heutige Hardware ein Witz ist, aber in Zusammenhang mit der Ausgabe jeder Position auf dem Monitor dann doch zu Laufzeiten von über 10 Minuten führte. Da kann man dann natürlich tricksen und nur jede fünfte oder zehnte Position ausgeben. Es zeigte sich jedoch dass bei einer vertikal gespiegelten Version des obigen Rätsels statt 45253 Versuchen nur noch 199 nötig waren. Die Methode, die jeweils erste freie Zelle von links oben durchzuiterieren war offensichtlich suboptimal.

Algorithmus
Der Grundalgorithmus blieb gleich, freie Zelle suchen und für jede mögliche Ziffer Rekursion mit der nächsten freien Zelle. Geändert wurde lediglich das Auffinden dieser Zelle. Unter allen noch freien Zellen wird die genommen, deren Kasten, Zeile und Spalte am meisten gefüllt sind. Bei der Optimierung von rekursiven Programmen habe ich immer eine gewisse Scheu, zusätzliche Anweisungen einzufügen, aber letzten Endes hängt die Gesamtlaufzeit nur von einer möglichst niedrigen Anzahl Rekursionen ab. Mein Referenzrätsel wird jetzt jedenfalls mit 315 Versuchen gelöst.

Screenshot: