Rätsel berechnet: Wann Sudokus eindeutig lösbar sind

Dublin (Irland) - Das „Kreuzworträtsel für Zahlenfans” – Sudoku – ist für Mathematiker weniger ein Zeitvertreib als eine harte Nuss. Denn statt sich aufs Ausfüllen der Kästchen zu beschränken, versuchen sie die Frage zu beantworten: Mit wie vielen Zahlen in den 9 mal 9 Feldern ist ein Sudoku eindeutig lösbar? Es sind 17, sagen jetzt irische Forscher. Sie konnten zwar keinen eleganten mathematischen Beweis vorlegen, lösten das Problem aber mit der Rechenkraft eines Supercomputers: Er konnte auch bei geschickter Vereinfachung in sieben Millionen Rechenstunden kein eindeutig lösbares 16-Zahlen-Sudoku finden. Dieses Ergebnis, online in der wissenschaftlichen Datenbank arXiv präsentiert, bestätigt, was Rätselfans seit Jahren vermuten. Auch Mathematiker halten die Lösung, die sie kürzlich auf einer Fachkonferenz in Boston erfuhren, für plausibel. Allerdings dürfte das Überprüfen wegen der enormen Rechenzeit eine Weile dauern. Derweil ist die Herangehensweise der Forscher auch für andere Bereiche interessant: Sie dürfte auch in der Gen-Analyse und Bioinformatik die Testauswertungen beschleunigen, ebenso wie bei Computernetzwerken und der Software-Entwicklung.

„Unsere Suche hat kein Sudoku mit 16 Hinweiszahlen geliefert, aber würde eines existieren, dann hätten wir es gefunden“, sagt das Team um Gary McGuire vom University College Dublin. „Das beweist, dass die Antwort tatsächlich 17 ist“, heißt es in der Veröffentlichung. Die Menge der Hinweiszahlen – jener Zahlen, die in den 81 Feldern eines Sudoku-Gitters bereits vorgedruckt sind – bestimmt seinen Schwierigkeitsgrad. Denn ein Sudoku ist dann gelöst, wenn die Ziffern 1 bis 9 so verteilt sind, dass sie in jeder senkrechten Zeile, in jeder waagerechten Zeile und auch in jedem Unterbereich von 3 mal 3 Feldern jeweils nur einmal vorkommen. Je mehr Zahlen schon vorgegeben ist, desto einfacher wird es, die restlichen mit Logik und Ausprobieren zu ergänzen. Auf den Rätselseiten von Zeitungen etwa sind es im Schnitt 25. Erfahrene Tüftler können auch Sudokus mit unter 20 Vorgaben relativ schnell lösen. Sind es aber zu wenige, so gibt es offenbar keine eindeutige Lösung mehr, mehrere Varianten sind dann möglich.

Da Theoretiker für diesen Erfahrungswert bisher keinen mathematischen Beweis vorlegen konnten, setzten McGuire und Kollegen auf die Rechenkraft eines Supercomputers. Allerdings grenzten sie das Problem vorher ein, denn das reine Ausrechnen aller Varianten hätte auch den stärksten heutigen Rechner weit überfordert: Zusammengenommen existieren rund 6,67 Trilliarden – also Millionen Millionen Milliarden – mögliche Sudokus. Nimmt man gedrehte, gespiegelte und andere Symmetrie-Varianten heraus, so sind es noch immer 5.472.730.538 – rund 5,5 Milliarden. Für diese müsste nun gezeigt werden, dass es beim Füllen von nur 16 Feldern nie zu einem eindeutigen Ergebnis kommt. Allerdings erhöht das die Zahl der Berechnungen wieder, sogar über die Trilliarden hinaus, da für jedes der 5,5 Milliarden Sudokus wieder fast 3,5 Billiarden Varianten existieren, 16 Felder vorzugeben.

Ein weiterer Trick der Mengentheorie war nötig, damit der von den Forschern entwickelte Algorithmus die möglichen Fälle einigermaßen effizient durchtesten konnte: das so genannte Hitting Set Problem. Es beschreibt die Tatsache, dass bei bestimmten Anordnungen der Zahlen im fertigen Sudoku austauschbar und somit uneindeutig sind. Um dies zu vermeiden, müssen einige Vorgaben-Sets einander überlappen – die Hitting Sets. Sind solche Fälle identifiziert, verringert sich die Lösungsmenge wieder deutlich, um zahlreiche Größenordnungen. Zwei Jahre lang testete McGuires Team zunächst den Algorithmus.

Als er zum Einsatz kam, waren trotzdem noch 7 Millionen Rechenstunden nötig – auf einem PC mit nur einem Prozessor wären das knapp 800 Jahre. Die Forscher nutzten deshalb einen Superrechner am Trinity Centre for High-End Computing in Dublin, der 640 Stück Intel Xeon Hexa-Core-Prozessoren kombiniert – so genannte Sechskernprozessoren. Dieser lief dann „nur“ zwischen Januar und Dezember 2011, um das Sudoku-Problem zu lösen. Übrigens bedeutet das Ergebnis nicht, dass alle Sudokus mit 17 Vorgaben eindeutig lösbar sind, sondern nur, dass es solche gibt – im Gegensatz zu solchen mit 16 Vorgaben. Auf einen eleganten mathematischen Ableitungsbeweis wartet die Forschung weiterhin. McGuire selbst hat über den Berechnungen die Lust am Sudoku etwas verloren, sagt er: „Ich bevorzuge zum Entspannen Kreuzworträtsel.“