Problem mit Sudoku ähnlichem Programm

[Grishnak]

Ich bin der Meinung, dass durch rein zufälliges Füllen es relativ leicht passiert, dass für eine bestimmte Zelle keine Möglichkeit besteht, diese zu füllen; d.h. es kommen bereits alle Zahlen von 1 bis 9 in der Zeile, Spalte bzw. Unterquadrat vor. Aus diesem Grund bleibt dein Programm wahrscheinlich auch hängen!

Weiterhing bin ich der Meinung, dass ein solches Unterfangen ohne Back-Trac(k)ing überhaupt nicht möglich. Sobald dein (Zufalls-)Algorithmus an eine Stelle kommt, für die keine Zahl mehr möglich ist, muss er einen Schritt zurück (auf die vorherige Zelle) gehen und dort eine andere Zahl eintragen. Sollte es für diese Zelle keine andere mögliche Zahl gehen, muss wiederum ein Schritt zurückgegangen werden usw. Ein solches Vorgehen dürfte aber sehr rechenintensiv und langwierig sein.

Sollte der Algorithmus ein widerspruchsfreies Sudoku gefunden haben, wie geht es dann weiter? Schließlich sind ja alle 9x9 Felder nun gefüllt? Wie willst du von diesem aus zu einem 9x9-Gitter kommen, in dem nur einige Zahlen drinstehen, mittels denen man das Sudoku eindeutig lösen kann (es darf schließlich nur genau eine Lösung existieren!)?

Ich habe mir selbst einen Sudoku-Löser und darauf aufbauend einen Sudoku-Generator geschrieben. Wenn es dich interessiert, kann ich dir gerne genauer erklären, wie ich vorgegangen bin!