Rätsel berechnet: Wann Sudokus eindeutig lösbar sind
„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.“