Schwerstes Sudoku der Welt?
Ich habe mit Java einen Algorithmus programmiert, der Sudokus lösen kann. Die reine Berechnungszeit beträgt allerdings nur, selbst bei extrem schweren Sudokus (zumindest wenn man nach der Bezeichnung aus Zeitungen oder dem Internet geht), maximal 50ms. Das ist zwar sehr schön, allerdings würde ich meinen Computer gerne mehr fordern.
Deshalb meine Frage: Gibt es Sudokus, die sehr sehr wenige Zahlen(10? 15?) vorgegeben haben, es trotzdem aber nur eine einzige Lösung gibt und das Rätsel somit als Sudoku gilt?
3 Antworten
Gibt es Sudokus, die sehr sehr wenige Zahlen(10? 15?)
Es gibt einige mit 17 Zahlen, solche kannst du dir hier generieren. Sudoku mit weniger Zahlen gibt es kein einziges (Sudokuvarianten mit Sonderregeln wie z.B Knight-Sudoku ausgenommen), weshalb vermutet wird das 17 die Mindestanzahl für ein lösbares Sudoku ist. Aber auch die Anordnung der Zahlen ist entscheidend.
Ein für Menschen tendenziell sehr schweres Sudoku ist bspw Tatooine Sunset. Die Schwierigkeit ergibt sich aber hauptsächlich daraus einen Lösungsweg zu finden, ein Problem das dein Algorithmus nicht haben sollte.
Für deinen Algorithmus interessant könnte Hanabi von shye sein. Den geplanten Lösungsweg finden Solver normalerweise nicht, da dieser eine recht neue Lösungstechnik benötigt.
@DanKirpan Mein Algorithmus arbeitet grob wie folgt:
-Für jedes nicht gelöste Feld wird eine Liste mit möglichen Zahlen aufgestellt
-Es wird geschaut, bei welchen Feldern es nur eine Möglichkeit gibt, diese wird dann eingesetzt
-Dann werden die möglichen Zahlen pro Feld wieder neu berechnet
-Sollte es irgendwann kein Feld mit nur einer Möglichkeit geben, kommt Rekursion ins Spiel: Es werden beim ersten leeren Feld alle Möglichkeiten durchprobiert, wenn eine passende gefunden wurde, wird diese dann entgültig eingesetzt und die anderen werden verworfen.
Von daher ist es eigentlich nur eine Frage der Zeit, bis der Computer die Lösung berechnet hat. Ich hatte halt noch die Hoffnung, dass es Sudokus gibt, bei denen der Computer länger als 1/20 s braucht, aber das scheint wohl nicht der Fall zu sein
Die schwersten die ich kenne sind in der französischen Tageszeitung "Le Monde"
Versuchs mal mit dem. (wäre cool wenn ich die Lösung dann auch sehen könnte)
812 753 649
943 682 175
154 237 896
369 845 721
287 169 534
521 974 368
438 526 917
796 318 452
Berechnungszeit: 77ms.
Eigentlich dauert nur das eingeben, wenn man auf den Button "Lösen" kommt, dann erscheint das Ergebnis (auch bei diesem Sudoku) sofort.