http://www.faz.net/-gwz-6yel5

Mathematik : Der Heilige Gral der Sudokus

  • Aktualisiert am

Erwischt: Bundesfinanzminister Wolfgang Schäuble spielt am 28.02.12 Sudoku auf der Regierungsbank, während der deutsche Bundestag über das zweite „Rettungspaket“ für Griechenland über 130 Milliarden Euro. Bild: ARD Tagesschau

Jetzt ist es streng mathematisch bewiesen: Für eine eindeutige Lösung des beliebten Rätsels müssen mindestens siebzehn Zahlen vorgegeben sein.

          Vor zehn Jahren in Europa noch vollkommen unbekannt, sind Sudokus heute schon weiter verbreitet als Kreuzworträtsel. Das Spiel und seine Regeln sind denkbar einfach. Ein Quadrat ist in neun Blöcke unterteilt und jeder Block wiederum in neun Felder. Insgesamt hat ein Sudoku also einundachtzig Felder, die schachbrettartig zu neun Zeilen und neun Spalten angeordnet sind. Bei einem richtig gelösten Sudoku muss in jedem der einundachtzig Felder eine der Zahlen von 1 bis 9 stehen. In keiner Zeile, in keiner Spalte und in keinem Block darf eine Zahl mehrfach vorkommen. Einige Zahlen sind stets vorgegeben, und die Aufgabe ist nun, die restlichen Zahlen zu finden. Das kann manchmal recht leicht, aber auch mit stundenlanger Grübelei verbunden sein. Je weniger Zahlen vorgegeben sind, desto schwerer ist ein Sudoku zu lösen. Bei den Rätseln, die man in Zeitungen und Zeitschriften findet, sind es meistens zwischen 25 und 30 Zahlen, die es zu finden gilt.

          Rätselhafte Sudokus

          Die große Popularität der Sudokus hat längst auch die Mathematiker auf den Plan gerufen. Sie sind weniger an der Lösung einzelner Rätsel interessiert als an grundsätzlichen Fragen. Wer ein Sudoku entwirft, kann nicht völlig willkürlich einige Zahlen in das leere Raster setzen. Denn dann kann es passieren, dass es unlösbar ist, weil alle Möglichkeiten, die restlichen Felder zu füllen, zu Widersprüchen führen. Oder es kann passieren, dass es nicht nur eine, sondern mehrere Lösungen gibt, was immer der Fall ist, wenn zu wenige Zahlen vorgegeben werden. Die Mathematiker fragten sich deshalb schon seit Jahren, wie viele Zahlen in einem Sudoku mindestens vorgegeben sein müssen, damit es überhaupt eine eindeutige Lösung geben kann. Der Statistiker Gary McGuire vom University College Dublin in Irland und die beiden Informatiker Bastian Tugemann und Gilles Civario haben die Antwort gefunden. Sie lautet „17“.

          Die Lösung  heißt 17

          Dass 17 die Mindestzahl ist, damit ein Sudoku eindeutig zu lösen ist, wird schon seit mehreren Jahren vermutet. Denn man kannte kein einziges Sudoku mit 16 oder weniger vorgegebenen Zahlen, das eine eindeutige Lösung besitzt, wohl aber eine ganze Reihe mit 17 Zahlen. Der australische Mathematiker Gordon F. Royle von der University of Western Australia in Perth hat sogar fast 50 000 eindeutig lösbare Sudokus mit 17 Zahlen gesammelt und stellt sie im Internet jedem zur Verfügung .

          Im Jahre 2005 haben Bertram Felgenhauer und Frazer Jarvis berechnet, dass es fast 6,7 Trilliarden verschiedene Möglichkeiten gibt, die Zahlen von 1 bis 9 regelkonform auf die 81 Felder eines Sudoku-Rasters zu verteilen. Allerdings gibt es unter diesen Lösungen Ähnlichkeiten. Sudokus weisen nämlich etliche Symmetrien auf. Man kann ein Sudoku drehen oder spiegeln, Zeilen oder Spalten einer Blockreihe vertauschen oder Zahlen gegeneinander auswechseln und erhält dennoch jedes Mal wieder gültige Sudokus. Zählt man alle symmetrischen Lösungen nur einmal, bleiben von den 6,7 Trilliarden Möglichkeiten nur noch 5,5 Milliarden übrig.

          Siebzehn Zahlen müsst ihr mindestens sein
          Siebzehn Zahlen müsst ihr mindestens sein : Bild: F.A.Z.

          Der Supercomputer als Helfer

          Die Grundidee, wie McGuire und seine Kollegen mit dem Computer bewiesen haben, dass für eine eindeutige Lösung des Sudokus mindestens 17 Zahlen vorgegeben sein müssen, ist ganz einfach: Es gibt etwa 34 Billiarden Möglichkeiten, aus einem Sukodu 16 Felder auszuwählen. Mit Hilfe eines Computers überprüften die Wissenschaftler all diese Möglichkeiten für die 5,5 Milliarden verschiedenen Sukodus auf die Frage hin, ob sie zu einer eindeutigen Lösung führen. Sie haben keinen einzigen Fall gefunden. Damit war die Vermutung bewiesen, wie die drei Wissenschaftler in ihrem Artikel in der Online-Datenbank „arXiv“ berichten. Die Methode ist zwar kein eleganter mathematischer Beweis und wird von vielen Mathematikern als unästhetisch empfunden, da sie auf einem Computer basiert. Aber sie wird akzeptiert, weil sie unbestritten das richtige Ergebnis liefert. Auch bei der Berechnung großer Primzahlen haben sich Rechner schließlich bewährt.

          Gigantischer Aufwand

          Natürlich geht es nicht nur darum, 34 Billiarden mal 5,5 Milliarden Sudokus von Hand lösen. Selbst die größten und schnellsten Computer der Welt wären dazu nicht in der Lage. McGuire, Tugemann und Civario haben vielmehr Methoden entwickelt, mit denen sich die Anzahl der tatsächlich zu überprüfenden Sudokus um viele Größenordnungen verringern lässt. Beispielsweise machten sie sich zunutze, dass bestimmte Konfigurationen von nur wenigen Zahlen bereits zu mehrdeutigen Lösungen führen können, wenn nicht mindestens eine Zahl von vornherein vorgegeben ist. Trotzdem war der Aufwand noch gigantisch.

          Arbeit für ein ganzes Jahr

          Zwei Jahre lang testeten McGuire und seine Kollegen ihre Vorgehensweise, auf deren Grundlage sie ein Computerprogramm namens „Checker“ entwickelten. Dennoch waren noch mehr als sieben Millionen Rechenstunden dazu notwendig, alle Sudokus zu überprüfen. Ein normaler PC hätte dafür fast 800 Jahre laufen müssen. Die Wissenschaftler verwendeten einen Superrechner am Trinity Centre for High-End Computing in Dublin mit 640 parallel arbeitenden Prozessoren. Doch auch mit diesem Rechner dauerte es noch ein ganzes Jahr, bis alle Möglichkeiten durchprobiert waren. Damit weiß man nun also, dass es keine eindeutig lösbaren Sudokus mit 16 oder weniger vorgegebenen Zahlen gibt. Doch schon wartet die nächste große Frage auf die Mathematiker: Wie viele eindeutig lösbare Sudokus mit 17 vorgegebenen Zahlen gibt es nun tatsächlich?

          Quelle: F.A.Z.

          Weitere Themen

          Der Star-Wars-Millenium-Falke Video-Seite öffnen

          Lego : Der Star-Wars-Millenium-Falke

          Der neue Star Wars Millennium Falcon von Lego ist der größte Bausatz des Spieleherstellers: Mehr als 7500 Teile und ein stolzer Preise - den Sammler aber sicher zahlen werden.

          Topmeldungen

          „Wir haben mit einem übersteigerten, ausgrenzenden Nationalismus, mit Europafeindlichkeit und Ausländerhass nichts zu tun“, sagt Edmund Stoiber

          Edmund Stoiber im Interview : „Gauland steht für völkisch-dumpfes Niveau“

          Auf dem Höhepunkt der Flüchtlingskrise kritisierte Edmund Stoiber die Kanzlerin scharf – jetzt findet er nur noch lobende Worte für Angela Merkel. Ein Gespräch über politische Konkurrenz rechts neben der CSU, das Klima in der Union und seine legendäre Transrapid-Rede.
          Hier steht er und kann wohl leider wirklich nicht anders: Frank-Walter Steinmeier eröffnet über ergraute Köpfe hinweg eine neue Veranstaltungsreihe zur Zukunft der Demokratie.

          Steinmeier hält eine Rede : Sie nennen es Debatte

          So so, Europa ist also in Gefahr? Reden können spannend sein wie Bingo, wenn jede politische Hohlformel zielsicher abgehakt wird. Ein Werteschaulaufen im Schloss Bellevue.
          Anklage: Eine Unterstützerin der pro-kurdischen HDP hält Fotos der Parteichefs Selahattin Demirtas und Figen Yuksekdag hoch, die in Haft sind.

          Brief aus Istanbul : Wir holen sie aus ihrem Grab

          In der Türkei bekennen sich mittlerweile selbst Wissenschaftler zu ihren Mordgelüsten. Unter kräftigem Zutun der Regierenden vergiftet und zerstört die Hasssprache den sozialen Frieden im Land.

          Newsletter

          Immer auf dem Laufenden Sie haben Post! Abonnieren Sie unsere FAZ.NET-Newsletter und wir liefern die wichtigsten Nachrichten direkt in Ihre Mailbox. Es ist ein Fehler aufgetreten. Bitte versuchen Sie es erneut.
          Vielen Dank für Ihr Interesse an den F.A.Z.-Newslettern. Sie erhalten in wenigen Minuten eine E-Mail, um Ihre Newsletterbestellung zu bestätigen.