Für jedes Problem gibt es eine Lösung. Sie zu finden, kostet manchmal nur etwas Mühe. Zum Beispiel beim Sudoku, dem beliebten Zahlenrätsel. Fans können Stunden oder Tage damit verbringen, die leeren Kästchen mit Zahlen zu füllen. In jeder Spalte, jeder Zeile und jedem der neun 3x3-Blöcke eines Sudokus dürfen die Ziffern von 1 bis 9 nur ein einziges Mal vorkommen. Je weniger der insgesamt 81 Zahlen vorgegeben sind, desto schwerer ist das Rätsel. Mindestens 17 vorbelegte Kästchen müssen es sein, sonst gibt es keine eindeutige Lösung. Das lehrt die Sudoku-Erfahrung. Aber lässt diese sich auch beweisen?

Die Frage quält die Zahlenakrobatiker seit vielen Jahren. Gordon F. Royle, ein Mathematiker aus Australien, hat inzwischen 49 151 Beispiele für Sudokus gefunden, bei denen 17 vorbelegte Kästchen tatsächlich reichen, aber noch keines, das mit nur 16 Hinweisen eine eindeutige Lösung ergäbe.

Eine 17-jährige Schülerin aus Wilhelmshaven erregte 2008 großes Aufsehen, als sie im Rahmen des "Jugend forscht"-Wettbewerbs eine Formel präsentierte, die angeblich bewies, dass ein eindeutig lösbares Sudoku mit weniger als 17 vorgegebenen Ziffern unmöglich sei. Doch die Beweisführung war leider fehlerhaft. So blieb die Frage nach der Mindestanzahl der Hinweise beim Sudoku weiter offen.

Rätsel geknackt

Jetzt hat der irische Mathematiker Gary McGuire das Rätsel offenbar geknackt. Sein Rezept: brutale Rechengewalt statt mathematischer Eleganz. McGuire konnte sein Programm namens "Checker" so optimieren, dass er statt der ursprünglich geschätzten 300 000 Jahre nur 7,1 Millionen Stunden Rechenzeit auf einem Supercomputer brauchte, um zu dem Ergebnis zu kommen, dass ein eindeutig lösbares Sudoku mit 16 Hinweisen tatsächlich nicht existiert.

"Die Methode ist vernünftig und plausibel. Ich würde sagen, es herrscht vorsichtiger Optimismus", lobte ihn sein US-Kollege Jason Rosenhouse, ebenfalls Sudoku-Spezialist, am Rande des weltweit größten Mathematiker-Treffens, das am Wochenende in Boston (Massachusetts) zu Ende ging. Wer ein Sudoku mit 17 Hinweisen löst, hätte demnach das Ende der Fahnenstange erreicht. Gut zu wissen für alle Rätselfreunde.

Und McGuire selbst, was tut er, wenn er nicht an seinen Algorithmen bastelt? Er finde es hin und wieder ganz angenehm, sich mit Sudokus zu entspannen, gestand er dem Online-Dienst des Wissenschaftsmagazins "Nature": "Aber um ehrlich zu sein, Kreuzworträtsel sind mir noch lieber."

---

---