Computerberechnung löst Rätsel um Sudoku-Minimum

Ein klassisches Sudoku-Rätsel mit 17 Hinweisen
Ein klassisches Sudoku-Rätsel mit 17 Hinweisen

Zahlenrätsel wie Sudoku erfreuen sich wachsender Beliebtheit. Aber während sich die meisten Hobby-Knobler mit der Lösung eines oder mehrerer Sudoku-Rätsel zufrieden geben, sehen Mathematiker in solchen Spielchen bisweilen völlig andere Probleme. Ihnen geht es eher um die Lösung grundsätzlicher Fragestellungen, die sich bei der Lösung von Sudoku-Rätseln ergeben.

Da wahrscheinlich nicht jeder Leser ein Knobelfan ist und die Sudoku-Spielregeln im Kopf hat, erkläre ich sie an dieser Stelle kurz. Ein (klassisches) Sudoku-Spielfeld besteht aus 9 x 9 = 81 kleinen Quadraten (siehe das nebenstehende Bild). Jeweils neun von ihnen bilden ein größeres Quadrat. Die Aufgabe des Rätselknackers ist es, die Ziffern 1 bis 9 so anzuordnen, dass jede Spalte, jede Reihe und jedes der 9 größeren Quadrate die Ziffern 1 bis 9 enthält, wobei die Reihenfolge unwichtig ist. Um dieses Ziel zu erreichen, sind bereits mehrere Zellen mit einer Ziffer versehen, was dem Spieler als Ansatzpunkt dient. In diesem Beispiel sind es 17 Ziffern, die dem Spieler Hilfestellung bei der Lösung des Rätsels geben sollen.

Bei einer der für Mathematiker interessanten Fragen dreht es sich nicht um die Lösung dieses spezifischen Sudokus, sondern darum, wieviele Hinweise mindestens gegeben sein müssen, um das Rätsel überhaupt lösen zu können. Hier sind es 17 Hinweise. Wäre eine eindeutige Lösung auch mit 16 Hinweisen möglich? Oder mit zehn Hinweisen?

Gary McGuire und einige Kollegen vom University College Dublin gingen dieser Frage nach. Für Laien mag das nicht sonderlich spektakulär oder schwierig klingen, aber es gibt exakt 6.670.903.752.021.072.936.960 (ungefähr 6,7 * 1021) potenzielle Sudoku-Lösungen. Es wäre vielleicht durchaus möglich, dass sich darunter eine befindet, die sich mit nur 16 Hinweisen finden lässt – vielleicht aber auch nicht. Um dies herauszufinden, müsste jede einzelne Lösungsvariante getestet werden, was angesichts der schieren Anzahl allerdings selbst für einen Supercomputer ein erheblicher Zeit- und Rechenaufwand wäre. Zum Glück gibt es zahlreiche Lösungen, die vollkommen symmetrisch zu anderen Lösungsvarianten sind. So konnte die Anzahl der zu überprüfenden Möglichkeiten auf “nur” noch 5.472.730.538 gesenkt werden.

McGuire und sein Team schrieben ein Computerprogramm namens “Checker”, um diese Varianten dahingehend zu testen, ob sie mit 16 Hinweisen lösbar sind. Aber dieser Prozess ist ebenfalls äußerst komplex. Jede potenzielle Lösung muss einzeln untersucht werden, wobei jede mögliche Anordnung der 16 Hinweise bedacht werden muss. Auch hier ließ sich der Arbeitsaufwand deutlich reduzieren, weil die Wissenschaftler zeigen konnten, dass viele Anordnungen äquivalent sind.

Die Berechnung der Lösungsvarianten war trotz der mathematischen Erleichterungen extrem aufwändig. McGuire zufolge wurde für die Berechnung ein Supercomputer mit 640 Intel Xeon Hex-Core Prozessoren verwendet. Sie wurde im Januar 2011 gestartet und erst im Dezember 2011 stand das Ergebnis fest.

Das Ergebnis war negativ, es gibt also kein (klassisches) Sudoku-Rätsel, das sich mit nur 16 Hinweisen lösen lässt. Man benötigt mindestens 17 Hinweise in Form der schon vorher eingetragenen Ziffern, um die Lösung des Sudokus finden zu können. Vollständig gelöst ist diese Fragestellung trotzdem noch nicht – zumindest nicht für Mathematiker. Um diese Frage zu beantworten, wurde lediglich die Brute-Force-Rechenmethode angewandt, bei der jede Variante einzeln geprüft wird. Es fehlt ein eleganter Beweis dafür, warum die Mindestanzahl der Hinweise 17 ist.

Referenz: http://arxiv.org/abs/1201.0749 “There Is No 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem”

(THK)

Werbung

Ersten Kommentar schreiben

Antworten

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


*