Was ist die Mindestanzahl von Hinweisen, die ein Sudoku haben kann?
Zuletzt aktualisiert
Ein gültiges Sudoku – eines mit genau einer Lösung – erfordert mindestens 17 vorgegebene Ziffern. Dies ist ein bewiesenes mathematisches Ergebnis. Jedes Rätsel mit 16 oder weniger Hinweisen hat entweder mehrere Lösungen oder gar keine.
Der Beweis von 2012
Im Jahr 2012 veröffentlichten Gary McGuire, Bastian Tugemann und Gilles Civario vom University College Dublin einen Beweis, dass kein gültiges 16-Hinweise-Sudoku existiert. Ihre Arbeit war hauptsächlich rechnerisch: Sie durchsuchten den gesamten Raum möglicher 16-Hinweise-Gitter und bestätigten, dass keines eine eindeutige Lösung ergab. Die Suche erforderte etwa 7 Millionen Kernstunden Rechenzeit.
Zuvor war weitgehend angenommen worden, dass 17 das Minimum sei, und Tausende von 17-Hinweise-Rätseln waren experimentell gefunden worden. McGuires Team lieferte den ersten rigorosen Beweis, dass 16 unmöglich ist.
Wie 17-Clue-Puzzles aussehen
17-Hinweis-Rätsel sind extrem spärlich – 17 gegebene Ziffern in 81 Zellen, 64 bleiben leer. Sie gehören zu den schwersten zu lösenden Rätseln und erfordern typischerweise fortgeschrittene Techniken. Das Finden gültiger 17-Hinweis-Rätsel erforderte selbst jahrzehntelange Rechenarbeit. Zum Zeitpunkt der Erstellung dieses Textes sind über 49,000 im Wesentlichen unterschiedliche 17-Hinweis-Sudoku-Rätsel bekannt.
Was dies für das Puzzle-Design bedeutet
Veröffentlichte Rätsel, die sich an menschliche Löser richten, gehen selten unter 22 Hinweise. Experten- und Meister-Schwierigkeitsrätsel verwenden typischerweise 22-27 vorgegebene Ziffern, während einfache Rätsel 36-45 verwenden. Das 17-Hinweise-Minimum ist eine theoretische Grenze - In der Praxis sind Lösbarkeit mit guter Technik und ein angenehmer Lösungsweg weitaus wichtiger als die reine Hinweisanzahl.