[ > zurück zu den Proben ]

¬ Ackern auf 81 Feldern

Weltmeister brauchen bis zu einer Viertelstunde für ein schweres Sudoku. Der Computer von Thorsten Koch schafft das schneller: "Wir lösen Sudoku-Rätsel in Millisekunden", sagt der Mathematiker am Berliner DFG-Forschungszentrum Matheon. Dafür bereiten dem Forscher andere Fragen Kopfzerbrechen. Zum Beispiel: Wie viele nicht vollständig ausgefüllte Sudokus gibt es? Klar ist: Man kann neun mal neun Felder auf 66709037520210729369602 verschiedene Weisen nach den Sudoku-Regeln füllen. Das hat der Informatiker Bertram Felgenhauer an der Technischen Universität Dresden ausgerechnet. Doch diese Zahl sagt nichts über die Anzahl möglicher Rätsel, also der teilweise ausgefüllten Gitter, die sich eindeutig vervollständigen lassen.

Und wie viele Zahlen müssen in Sudoku-Gittern mindestens stehen? "Das ist unseres Wissens auch eine noch offene Frage", sagt Volker Kaibel, Kollege von Koch am Matheon. Klar ist: 17 können genug sein, denn dafür kennt man Beispiele. Doch geht es auch mit weniger? Das wollen Kaibel und Koch nun testen: Ab morgen kann man auf der Webseite des Matheon Sudokus eingeben und mit der Matheon-Software lösen lassen. Die Sudokus mit besonders wenigen vorausgefüllten Feldern werden registriert -- und prämiert.

Zum Lösen der Sudokus wird der Webserver auf Software zurückgreifen, die am Matheon eigentlich für ganz andere Zwecke verwendet wird: Zur Routenplanung oder bei der Verteilung von Handyfrequenzen zum Beispiel. "Solche Probleme gehören zur großen Problemklasse der ganzzahligen Programme -- genau wie Sudokus", erklärt Kaibel.

Keine halben Sachen

Bei der Lösung von Sudokus wird in jedes Spielfeld genau eine Zahl zwischen Eins und Neun gesetzt. Das haben die Mathematiker in ein mathematisches Modell übertragen: "Wir errichten über jedem der 81 Felder einen Turm mit neun Stockwerken. Wenn im fünften Stock eine Eins steht, dann heißt das: Wir setzen in dieses Feld eine Fünf", erklärt Kaibel. "Anderenfalls steht in diesem Stockwerk eine Null. Jede Lösung besteht daher aus einer Menge Einsen und Nullen." Brüche wie 1/2 oder 1/3 haben in der Lösung gar nichts verloren.

"Die Bedingungen, die beim Sudoku an die Zahlen gestellt werden, bauen wir dann mit einfachen Gleichungen nach", so Kaibel. Beispiel: Damit nie zwei gleiche Zahlen in einer Zeile landen, muss in jeder Zeile und jedem Stockwerk die Summe der Werte genau Eins ergeben. "Daher ist das Sudoku-Lösen ein ganzzahliges Programm: Die Lösung besteht aus ganzen Zahlen und die Nebenbedingungen aus linearen Gleichungen und Ungleichungen", so Kaibel.

Probleme dieser Art werden bereits seit 70 Jahren untersucht. Damals entstand auch der Begriff "linear program": Die Mathematiker John von Neumann und George Dantzig entwickelten Methoden -- "programs" --, um den gerade aufkommenden Computern beizubringen, wie man Unternehmen effizienter rechnet.

Geometrische Entsprechung

Was die Mathematiker freute: Es gibt eine geometrische Entsprechung für die Formeln der linearen Programme. Die Nebenbedingungen in den Programmen beschreiben eckige Körper mit geraden Begrenzungsflächen in einem hochdimensionalen Raum, so genannte Polytope. Und die Lösungen der Programme sind genau die Ecken dieser Polytope. "Eine Standardmethode zur Lösung eines linearen Programms besteht darin, den Computer entlang von Kanten des Polytops wandern zu lassen, bis er auf eine Ecke stößt, die der besten Lösung entspricht", erklärt Kaibel.

Doch davor werden heute extrem ausgefeilte Methoden eingesetzt: Da werden die Polytope auf Symmetrien untersucht und uninteressante oder unsinnige Lösungen noch vor Start der eigentlichen Suche weggeschnitten. Nur so lassen sich optimale Lösungen für große Alltagsprobleme wie die Linienplanung der BVG finden. Die basiert auf einem Riesenpolytop, das zu Anfang mehr Ecken besitzt als das Universum Atome hat. Mit denselben Mitteln beackert die Matheon-Software auch die 81 Sudoku-Felder so rasant: Sie schneidet so viel vom Suchpolytop ab, dass eine echte Suche gar nicht mehr nötig ist -- die Lösung ist in Millisekunden da. Da bleibt Zeit zum Lösen der wirklich kniffligen Fragen.



[ > zurück zu den Proben ]