Die Energie sagt uns also, “wie falsch” ein Sudoku ausgefüllt wurde. (Ihr könnt also ab jetzt einfach irgendwelche Zahlen in das Sudoku reinschreiben und sagen, dass ihr Hochenergie-Sudokus löst (oder auch “heiße Sudokus” – weil bei hohen Temperaturen ja höhere Energien auftreten).) Den Zustand mit der niedrigsten Energie hat das Sudoku, wenn es korrekt ausgefüllt wurde, dann gibt es keine Fehler, also ist die Energie Null.
Eine Besonderheit des Sudokus als physikalisches System ist, dass der räumliche Abstand zwischen zwei Punkten keine Rolle spielt. Zwei Punkte können sich entweder direkt beeinflussen (wenn sie zur selben Reihe, Spalte oder zum selben Block gehören), oder sie sind über zwei Punkte indirekt verbunden (denn es liegt immer ein Feld in der Reihe des einen und Spalte des anderen Punktes und umgekehrt). Es gibt also nicht die Möglichkeit, dass zwei Punkte “weit entfernt” voneinander liegen wie in anderen physikalischen Systemen.
So, wir haben also ein Sudoku, in dem anfänglich schon Hinweise drinstehen und das wir dann ausfüllen. Dann können wir seine “Energie” berechnen. Jetzt muss noch irgendwie die Thermodynamik ins Spiel kommen.
Dazu brauchen wir jetzt das wichtigste Gesetz der Thermodynamik, das Boltzmann-Gesetz. Es besagt (für Sudokus) Folgendes: Wenn wir unser Sudoku bei einer bestimmten Temperatur angucken (das ist natürlich eine rein fiktive Temperatur, die nichts damit zu tun hat, wo ihr das Sudoku-Heft aufbewahrt), dann können wir jeden denkbaren Zustand unseres Sudokus finden. Allerdings sind nicht alle Zustände gleichwahrscheinlich: Je höher die Energie eines Zustandes ist, desto unwahrscheinlicher werden wir ihn finden. (Mathematisch steckt da eine Exponentialfunktion drin, das findet ihr in der Entropie-Serie erklärt – rechts bei “Artikelserien” klicken.) Die Temperatur regelt dabei, wie viel unwahrscheinlicher ein Zustand mit hoher Energie ist als ein Zustand mit niedriger Energie – ist die Temperatur sehr niedrig, sind Zustände mit hoher Energie extrem unwahrscheinlich, geht die Temperatur gegen unendlich, dann sind auch Zustände mit hoher Energie genau so wahrscheinlich wie Zustände mit niedriger Energie.
“Echte” physikalische Systeme haben eine Dynamik, sie wechseln also von einem Zustand in einen anderen. Dabei können sie ihre Energie ändern, weil sie ja bei einer bestimmten Temperatur betrachtet werden – sie stehen also in Kontakt mit irgendeinem großen Wärmebad, dass sie auf Temperatur hält (beispielsweise ein Ofen, ein Kühlschrank oder so etwas). Wenn man die Energie über lange Zeit mittelt, dann stellt man fest, dass die Wahrscheinlichkeit der Zustände genau der Boltzmann-Verteilung entspricht.
Nun gibt es Sudokus nicht als echte physikalische Systeme und ihr könnt euer ausgefülltes Heft zwar mal für ein paar Stunden in den Ofen schieben, ich bezweifle aber, dass sich dadurch die Zahlen in den Feldern ändern werden (es sei denn, die Temperatur ist zu hoch, dann werden sie vermutlich braun). Wenn ihr aber euer Sudoku in eurem Computer abgespeichert habt, dann könnt ihr dort die Zahlen natürlich auch ändern – und zwar am besten genau so, dass ihr die richtige Wahrscheinlichkeitsverteilung für die Sudokus mit unterschiedlicher Energie bekommt, so dass also Zustände mit hoher Energie unwahrscheinlich und Zustände mit niedriger Energie wahrscheinlicher sind. Passende Algorithmen hat man Mitte des letzten Jahrhunderts ausgeknobelt (ursprünglich, um das Verhalten von Atombomben zu simulieren, inzwischen haben diese Algorithmen aber auch endlos viele nützlichere und ganz friedliche Anwendungen, beispielsweise in der Materialwissenschaft). Wir wählen also immer zufällig ein Feld aus und ändern die Zahl in diesem Feld nach bestimmten Regeln, die sicherstellen, dass am Ende die korrekte Thermodynamik herauskommt. (Wenn ihr die Regeln wissen wollt, könnt ihr ja mal mein Vorlesungsskript (Kap. 7) lesen – das pdf ist sogar kostenlos…) Dabei bestimmt, wie gesagt, die “Temperatur”, wie die Wahrscheinlichkeiten genau verteilt sind.
Wendet man so einen Algorithmus auf das Sudoku an, so verändert es sich also ständig. (Dabei ist es wichtig, dass die Hinweisfelder nicht verändert werden dürfen, sondern “eingefroren” bleiben.) Mal hat es Zustände mit hoher, mal mit niedrigerer Energie.Nach dem, was ich bisher geschrieben hab, könntet ihr annehmen, dass sich das Sudoku die meiste Zeit in dem Zustand der korrekten Lösung aufhält, denn der hat ja die niedrigste Energie (Null) und ist deshalb am wahrscheinlichsten. So ist es aber nicht, denn in einem eindeutigen Sudoku (das also nur eine Lösung hat) gibt es nur einen einzigen solchen Zustand, aber Millionen oder gar Milliarden andere mit höherer Energie. Nur bei extrem niedrigen Temperaturen “gewinnt” der Lösungszustand, wenn die Temperatur höher ist, dann findet man das Sudoku meist in einem Zustand mit mehr oder weniger vielen Fehlern, weil es davon einfach so viele gibt.
Kommentare (10)