Die Lösung aller Probleme
Zoltan Toroczkai von der Notre Dame University beschäftigt sich mit dem sogenannten Erfüllbarkeitsproblem der Aussagenlogik. "Ich hatte mich früher nie für Sudoku interessiert. Da es aber zu dieser Klasse mathematischer Probleme gehört, dachte ich, es wäre ein guter Prüfstand für meine Formeln. Die interessante Frage für mich und meine Kollegen ist: Wie weit können wir beim Lösen dieser Rätsel kommen, wenn wir sie deterministisch lösen - also ohne zu raten?"
Die Studie:
"The Chaos Within Sudoku" von Zoltan Toroczkai und Maria Ercsey-Ravaz ist am 11.10 in "Scientific Reports" (doi:10.1038/srep00725) erschienen.
Die Antwort gibt Toroczkai nun im Fachblatt "Scientific Reports". Der typische Sudoku-Spieler findet die Lösung durch eine Strategie, die man in der Mathematik als Brute-Force-Methode bezeichnet: Ausprobieren, scheitern, nochmals probieren - bis die richtige Kombination gefunden ist. Das ist natürlich nicht die eleganteste Methode. Eine, die dieses Prädikat eher verdient, hat nun Toroczkai mit seiner Kollegin Maria Ercsey-Ravaz entwickelt: Der Algorithmus arbeitet ohne Zufall und rollt das Problem auch nicht mehrmals von neuem auf, findet also den "sauberen" Lösungsweg.
Die beiden Mathematiker haben auch eine Klassifikationsmethode für Sudoku-Probleme entwickelt, bei der die Lösungszeit den Schwierigkeitsgrad angibt. Die Lösung eines Problems mit einem Rating von 2 nimmt demnach 10 Mal so viel Zeit in Anspruch wie jene eines Problems des Klasse 1. Die bislang höchste vergebene Note war 3,6 (Kategorie "ultra-schwierig"), ob es noch höhere Noten gibt, ist unklar. Toroczkais Forschungen hatten allerdings eine unerwartete Nebenwirkung: Er wurde Sudoku-süchtig.
"Meine Frau und ich haben einige Sudoku-Apps auf unsere Smartphones. Wir müssen uns tausende Male duelliert haben auf der Suche nach dem kürzesten Lösungsweg. Meine Frau findet oft Muster, die ich komplett übersehe. Ich muss die Möglichkeiten aufschreiben und die Lösung ableiten. Ohne Papier und Bleistift bin ich bei schwierigen Problemen verloren."
Robert Czepel, science.ORF.at
- Antwort auf das Sudoku-Rätsel: 17
- Computer erobern japanisches Schach
- Schachspieler halten sich ans Gesetz
- Studie + Mathe = weniger Zitate
