Standort: science.ORF.at / Meldung: "Antwort auf das Sudoku-Rätsel: 17"

Jemand füllt ein Sudoku aus

Antwort auf das Sudoku-Rätsel: 17

Die übliche Herausforderung von Sudokus besteht darin, fehlende Zahlen in ein quadratisches Raster einzufügen. Es gibt aber auch ein mathematisches Sudoku-Rätsel, nämlich die Frage, wie viele Ziffern vorgegeben sein müssen, damit es nur eine eindeutige Lösung gibt. Ein irischer Mathematiker sagt nun: 17.

Mathematik 09.01.2012

Mit 16 oder weniger Ziffern zu Beginn gibt es keine eindeutige Lösung, schreiben Gary McGuire vom University College in Dublin und Kollegen in einer online veröffentlichten Studie.

Die Studie:

"There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem" von Gary McGuire und Kollegen ist auf dem Preprint-Server "arXiv.org" erschienen.

Trilliarden von Varianten

Sudokus, in den USA erfunden, aber dann in Japan populär geworden, zählen heute auch in Österreich zu den beliebtesten Formaten von Rätselfreunden. Ziel ist es, ein Gitter aus 9x9 Flächen derart mit den Ziffern von eins bis neun zu füllen, dass jede in jeder Zeile, jeder Spalte und jedem Block nur genau einmal verwendet wird.

Zu Beginn sind einige der Ziffern bereits vorgegeben: je weniger desto schwieriger ist die Aufgabe. Einfache Sudokus haben 25 oder mehr Ziffern, schwierige 20 oder weniger. In den Zeitungen liegt der Durchschnittswert bei 25. Dass es mit 17 eine Grenze gibt, unterhalb der es keine eindeutige Lösung gibt, ist von Rätselfreunden empirisch schon oft beobachtet worden.

Mathematisch bewiesen wurde das bisher aber noch nicht. Und das liegt in erster Linie daran, dass die Möglichkeiten dazu riesig groß sind: Laut unterschiedlichen Berechnungen gibt es rund 6,7 Trilliarden Suduko-Varianten.

Sieben Millionen Stunden Rechenzeit

Für den mathematischen Beweis, dass 17 tatsächlich die Untergrenze für eindeutige Lösungen darstellt, hat es deshalb einer ganzen Menge Rechenzeit bedurft: Sieben Millionen Stunden sind es geworden, bis der von Gary McGuire am Computerzentrum in Dublin entworfene Algorithmus endlich das gewünschte Resultat liefern konnte.

Eine Konsequenz davon ist, dass es eine ganze Zeit dauern könnte, um die Berechnungen zu überprüfen. Die US-Mathematiker-Gemeinde, die sich vergangene Woche in Boston traf, hält die Arbeit jedenfalls für wertvoll, wie "Nature" berichtet. Mc Guire selbst füllt laut dem Magazin hin und wieder Sudokus aus, bevorzugt "aber ehrlich gesagt Kreuzworträtsel".

Lukas Wieselberg, science.ORF.at

Mehr zu dem Thema: