Um mal von der Polemik zur Sachlichkeit zurückzukehren:
Dragonate hat insofern recht, dass er tatsächlich sicherstellt, dass in jedem 3*3-Block wirklich nur die Zahlen von 1-9 vorkommen; in dem Punkt war ich tatsächlich im Irrtum. Dass seine Methode trotzdem extrem ineffizient ist, ist eine Tatsache.
Sudokus mit 18 vorgegebenen Zahlen sind eindeutig lösbar; das wären durchschnittlich 2 Zahlen pro Block. Gehen wir einmal von einem Sudoku mit 4 vorgegebenen Zahlen pro Block aus, was schon als ziemlich einfaches Sudoku einzustufen ist. Die Anzahl der Möglichkeiten, jeweils in einem Block die übrigen 5 Zahlen zu platzieren, ist 5! = 120. Die Anzahl der Möglichkeiten für 9 Blöcke sind dann
5!^9 = 120^9, also ca. 5*(10^18).
Und davon ist nur eine richtig.
Und viele davon werden mehrfach getestet.
Zufallsbasierte Lösungsverfahren werden in der Informatik tatsächlich angewandt; meistens wird dabei eine zufällige Startverteilung ausgewürfelt und dann versucht, durch Umgruppieren eine gültige Lösung zu finden. Wenn nach einer festgelegten Anzahl von Umgruppierungen keine Lösung gefunden wurde, wird eine neue Startverteilung ausgewürfelt. Wenn das Spielfeld groß genug ist, wird dadurch schneller eine Lösung gefunden als durch Backtracking. Bekanntestes Beispiel hierfür ist das N-Damen-Problem. Für ein Spielfeld mit 18*18 Feldern ist ein solcher intelligent implementierter Algorithmus tatsächlich schneller.
Für das Standard-Sudoku ist es allerdings schwierig bis unmöglich, gute Kriterien für die Umgruppierung zu finden, so dass ein Backtracking im allgemeinen die einzig effiziente Methode ist, eine Lösung zu finden.
Die derzeit effizienteste Methode, ein Backtracking zu implementieren, ist der Algorithmus X, auch 'Dancing Links' oder kurz DLX genannt, der von
Donald Knuth entwickelt wurde. Genaueres dazu findest du z.B. über die
Sudopedia.
