Algorithmus der eindeutig lösbare Sudokus erstellt
-
Hallo zusammen,
ich möchte gerne Sudokus generieren die eindeutig lösbar sind.
Ich habe schon einen Algorithmus geschrieben, der das Feld nach den Regeln mit Zahlen füllt (mittels Backtracking). Dieses Feld soll nacher die einzige (!) Lösung des Rätsels sein.
Wenn ich nun einfach zufällig Felder lösche tritt das Problem auf, dass mehrdeutige Rätsel erstellen. Das heißt man kann auch auf eine andere Lösungen als die AUsgangslösung kommen ohne gegen die Sudoku regeln zu verstoßen.
Ich muss also beim löschen der Felder ständig überprüfen ob das Sudoku auch noch eindeutig lösbar ist.
Leider hab ich zurzeit gar keine Idee wie man das machen könnte.
Kann mir bei diesem Problem jemand weiterhelfen? Kennt jemand einen Algorithmus der dieses Problem löst?
Vielen Dank für Eure Hilfe!
Gruß
Micha
-
das ist doch mal eine mathematische herausvorderung;)
naja im backtracking prinzip erstellst du erst mal felder, welche nach den regeln von sudoku lösbar wären .
nun willst du irgendwelche felder löschen und versuchen ob es nur eine kombination gibt die das sudok lösen... das sudoku hat regular 81 felder.. nun stell dir ein 81 bit große feld vor welche du von 0 auf max hochzählst.. nach diesen muster löscht du die felder, und bei jeder iteration gehst du im backtracking prinzip die möglichen lösungswege durch, gibt nur einen, dann merkst dir das "bitmuster" der 81 felder und machst weiter;)
-
Bruteforce
-
@BorisDieKlinge: Das hab ich jetzt leider nicht wirklich verstanden.
@Brainfuck: Wie genau stelltst du dir den Bruteforce-Algorithmus vor?
Danke für eure Hilfe!
Gruß
Micha
-
Durchprobieren.
-
@Brainfuck, ja wenn man viel Zeit hat und die Hardware eines PCs noch ziemlich modern ist, ja, dann geb ich dir recht. ;P
-
Dein Löser mit Backtracking dürfte sich doch recht gut so modifizieren lassen, dass er prüft ob es genau eine Lösung gibt, oder? Das dürfte auch nicht so viel langsamer sein als eine einzige Lösung zu suchen.
Wenn Du das hast kannst ja mit einem vollständig gefüllten Sudoku beginnen und zufällig zahlen rauslöschen und jedesmal deinen löser fragen ob's noch eindeutig ist.