Sudoku

Nicht nur in der Mathematik gibt es für (fast) jedes Problem eine Lösung. Auch, wenn die Lösung manchmal keine Lösung ist. Unter Umständen braucht es nur ein wenig Mühe, um sie zu finden. Nehmen wir Sudoku, ein sehr beliebtes Zahlenrätsel. Das Ausfüllen der leeren Kästchen mit Zahlen kann für Fans Stunden oder sogar Tage dauern. Die Zahlen von 1 bis 9 dürfen nur einmal in jeder Spalte, jeder Zeile und einem der neun 3×3-Blöcke vorkommen, aus denen ein Sudoku-Rätsel besteht. Die Herausforderung wird umso schwieriger, je weniger der insgesamt 81 Zahlen vorhanden sind. Wenn nicht mindestens 17 vorgegebene Felder vorhanden sind, gibt es keine offensichtliche Möglichkeit. Die Erfahrung mit Sudoku lehrt uns das. Lässt es sich aber auch beweisen?

Viele Mathematiker bereits am Rätsel gescheitert

Die Frage beschäftigt Zahlenjongleure schon seit langem. Der australische Mathematiker Gordon F. Royle hat bereits 49.151 Fälle von Sudoku-Rätseln entdeckt, bei denen 17 vorausgefüllte Kästchen wirklich ausreichen, aber noch keinen einzigen, der eine eindeutige Lösung mit nur 16 Hinweisen liefert.

Ein 17-jähriges Mädchen aus Wilhelmshaven sorgte 2008 für Aufsehen, als sie beim Wettbewerb „Jugend forscht“ eine Formel einreichte und behauptete, damit sei der Beweis erbracht, dass es unmöglich sei, ein Sudoku zu erstellen, das offensichtlich lösbar sei, aber weniger als 17 vorgegebene Ziffern habe. Leider hatte der Beweis eine Schwachstelle. Daher ist die Frage, wie viele Sudoku-Hinweise erforderlich sind, noch nicht beantwortet.

Lösung wurde gefunden

Gary McGuire, ein irischer Mathematiker, scheint das Rätsel zu dieser Zeit gelöst zu haben. Er hat in seinem Rezept die mathematische Schönheit durch schiere Rechenleistung ersetzt. Um zu dem Schluss zu kommen, dass es ein eindeutig lösbares Sudoku mit 16 Hinweisen tatsächlich nicht gibt, konnte McGuire seine „Checker“ getaufte Software so optimieren, dass er statt der ursprünglich erwarteten 300.000 Jahre nur 7,1 Millionen Stunden Rechenzeit auf einem Supercomputer benötigte.

„Der Ansatz ist logisch und plausibel. Es besteht meiner Meinung nach eine vorsichtige Hoffnung. „

Lob erhielt er von seinem amerikanischen Kollegen Jason Rosenhouse, ebenfalls ein Sudoku-Experte, am Rande des weltgrößten Mathematiker-Treffens, das am Wochenende in Boston, Massachusetts, zu Ende ging. Jeder, der ein Sudoku-Rätsel mit 17 Hinweisen löst, ist am Ziel. Gut zu wissen für die Rätselfans unter uns.

Was macht McGuire übrigens selbst, wenn er nicht gerade an seinen Algorithmen arbeitet? Gegenüber der Online-Ausgabe des Wissenschaftsmagazins „Nature“ gab er zu, dass er es zwar äußerst angenehm findet, sich gelegentlich mit Sudokus zu entspannen,

„(…) aber um ehrlich zu sein, liebe ich Kreuzworträtsel viel mehr“.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.