Betreibt man das Sudoku bei niedriger Temperatur, dann fällt es schnell in so ein lokales Minimum und bleibt darin. Erhöht man die Temperatur, dann verbringt es immer noch viel Zeit innerhalb der Zustände mit kleiner Energie, kann aber zwischen diesen hin- und herwechseln. Bei solchen mittleren Temperaturen befindet sich das Sudoku deshalb auch oft um Zustand mit der kleinsten Energie, also im Zustand der korrekten Lösung. Hier seht ihr, wie viel Zeit das System im Zustand der korrekten Lösung verbringt, wenn man unterschiedliche Temperaturen einstellt:
Aus Williams and Ackland, s.u.
Bei ganz niedrigen Temperaturen sind wir in einem fast richtigen Zustand gefangen (dass man tatsächlich die Lösung erwischt, ist sehr unwahrscheinlich), bei mittleren Temperaturen wechseln wir zwischen Zuständen mit niedriger Energie und sind deshalb auch oft im Lösungszustand, bei hohen Temperaturen findet man den Lösungszustand auch nahezu nie vor, weil die anderen falschen Zustände ja dann fast genauso wahrscheinlich sind.
Wenn ihr die Temperaturskala mit der im Bild oben vergleicht, dann seht ihr, dass der Phasenübergang, den wir oben bei der Wärmekapazität entdeckt haben, etwas oberhalb von der Temperatur stattfindet, bei der das Sudoku die maximale Zeit im Zustand der korrekten Lösung verbringt. Es gibt also drei Phasen: Die Hochtemperaturphase, in der sehr viele Fehler auftreten, die Phase bei mittlerer Temperatur, in der das Sudoku meist in einem lokalen Minimum ist, aber zwischen diesen Minima hin- und herwechseln kann, und dann die Niedrigtemperaturphase, bei der das System in einem lokalen Minimum eingefroren ist. Die drei Phasen werden – wegen unterschiedlicher Analogien zu anderen physikalischen Systemen – auch als “paramagnetische Phase”, “kondensierte (oder feste) Phase” und “Glasphase” bezeichnet.
Durch Variation der Temperatur kann man den Algorithmus übrigens auch tatsächlich zum Lösen von Sudokus verwenden. Das ist allerdings nicht besonders effizient – es gibt wesentlich bessere Möglichkeiten zum Lösen von Sudokus. An dem Bild seht ihr aber noch etwas anderes: Die unterschiedlichen Sudokus unterscheiden sich in der Zahl der vorgegebenen Hinweise (die Nummer in Klammern) und auch in ihrem Schwierigkeitsgrad – das ist jeweils die erste Zahl vor dem Strich. (Der Schwierigkeitsgrad wird dabei, wenn ich es richtig verstehe, darüber festgelegt, welche Schlussfolgerungstechnik man zum Lösen anwenden muss.) Ihr seht also, dass schwierige Sudokus auch als thermodynamische Systeme betrachtet weniger gern im Grundzustand sind als einfache – die Schwierigkeit für den Menschen korreliert zumindest einigermaßen mit dem thermodynamischen Verhalten.
Ist das alles denn auch zu irgendetwas gut? Ja, das ist es: Komplexe thermodynamische Systeme zu verstehen, ist nicht einfach. PhysikerInnen sind deshalb immer auf der Suche nach Modellsystemen, an denen sie ihre Ideen testen können. Das Sudoku-System ist einerseits erstaunlich einfach, zeigt aber mit seinen vielen lokalen Minima bei niedrigen Temperaturen und dem doppelten Phasenübergang ein ziemlich reichhaltiges Repertoire an thermodynamischen Phänomenen. Es ist also damit zu rechnen, dass das System in Zukunft noch weiter erforscht wird – und zusätzlich hat es den Vorteil, das Physik-DoktorandInnen in Zukunft immer behaupten können, dass sie Wissenschaft betreiben, wenn sie mit einem Sudoku-Heft erwischt werden.
A Williams and G. J. Ackland
Paramagnetic and glass transitions in sudoku
PHYSICAL REVIEW E 86, 031109 (2012)
Kommentare (10)