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

          Topmeldungen

          Lebenslang für Ratko Mladic : Ein historisches Urteil

          Das Urteil gegen Ratko Mladic ist gerechtfertigt. Der ehemalige bosnisch-serbische General wird den Rest seines Lebens in Haft verbingen – dort, wo er spätestens seit 1995 hingehört. Ein Kommentar.
          Es wird alles mitgenommen am „Black Friday“ in Amerika.

          Einkaufen am „Black Friday“ : Bereit für die Schnäppchen?

          Die aus Amerika herüber geschwappte vorweihnachtliche Schnäppchenwelle erfasst in diesen Tagen auch die deutschen Innenstädte. Aber nicht jedes Sonderangebot am „Black Friday“ und „Cyber Monday“ ist auch wirklich eines.

          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.