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.

1 / 2 / 3 / 4

Kommentare (10)

  1. #1 wereatheist
    24. Oktober 2012

    Beispielsweise unser Sudoku: Wir können uns vorstellen, dass jedes der 81 Felder einen der 9 möglichen Werte annehmen kann (die meisten Kombinationen geben aber natürlich kein korrekt gelöstes Sudoku, sondern Unsinn). Damit haben wir dann 81 hoch 9 mögliche Zustände, also immerhin etwa 150 Billiarden (1,5e17).

    Sorry, in diesem Fall gibt es 9^81 mögliche Zustände.

  2. #2 roel
    *****
    24. Oktober 2012

    @MartinB Wahnsinn, ich bin begeistert. Wofür doch Sudokus alles gut sind. Habe es aber erst einmal gelesen. Im Regelfall brauche ich deutlich öfter. Für das zweite Mal ist heute noch Zeit, aber dann ist für heute “wirklich Schluss”.

    Vielen Dank für das pdf.

  3. #3 MartinB
    25. Oktober 2012

    @wereatheist
    Autsch, wie konnte das passieren?
    Danke, hab’s korrigiert..

  4. #4 wereatheist
    partyzone friedrichshain
    25. Oktober 2012

    Shit happens, oder so 🙂
    Irgendwie hat mich das an Modelle für Ferromagnetismus erinnert (Ising-Modell). Lang ist´s her

  5. #5 MartinB
    25. Oktober 2012

    @wereatheist
    Ja, im paper wird auch explizit von Potts-Modellen (Ising-Modell mit mehreren Spin-Werten) gesprochen.
    Gibt im Netz auch einige nette Ising-Applets, z.B. bei javalab
    https://www.pha.jhu.edu/~javalab/ising/ising.html

  6. #6 Quacki
    26. Oktober 2012

    Es ist auch ohne weiteres möglich, ein Sudoku auf ein System mit Ising-Modell mit nur zwei möglichen Spins abzubilden. Hab ich in meiner Studienarbeit im Studium gemacht. Leider hab ich nicht die Thermodynamik untersucht, sondern lediglich ganz grob ob man mit so einem Modell Sudokus lösen kann. Hach, das juckt in den Fingern die Programme mal wieder rauszukramen und mal versuchen, die Ergebnisse von dem Paper nachzukochen … 🙂

    Was ich zum Beispiel schön finde, ist die letzte Abb. hier. Ich hab damals das Modell unter Abkühlung simuliert, bis T = 0 und sich nichts mehr tat. Ich wusste nicht, dass es eine Temperatur gibt, bei der man sich mit einer hohen Wahrscheinlich im Ground State befindet. Sollte ich mal nachprüfen, ob das bei mir auch gilt.

  7. #7 MartinB
    26. Oktober 2012

    @Quacki
    Wie bildet man denn die 9 Zahlen auf 2 ab? Nimmt man dann ein größeres Gitter? Und wie funktioniert das mit der Lokalität – das Ising-Modell ist ja lokal, das Sudoku nichtlokal?

  8. #8 Rennkuh
    26. Oktober 2012

    Spannender Beitrag.
    Wusste nicht, dass ich mich während des Grundstudiums so aktiv mit thermodynamischen Phänomenen beschäftigt habe.

  9. #9 Quacki
    26. Oktober 2012

    Was heißt genau lokal? Dass die Spins in einem Gitter stecken, wo die Gitterpunkte einem Ort im Raum entsprechen und die Kopplung durch die Entfernung zwischen zwei Gitterpunkten festgelegt ist?

    Ich hätte das wohl gleich genauer sagen sollen: Ich hab ein Hopfield-Netz gebastelt, welches Sudokus lösen kann. Mit Neuronen die die Werte -1,+1 annehmen, entspricht das H-Netz einem Ising-Modell, nur dass die Kopplungen unabhängig von einem räumlichen Zusammenhang sind. Ich hab allerdings Neurone mit Werten 0,+1 verwendet, so dass es nicht mehr ganz äquivalent ist (+1 bedeutet, die zugehörige Zahl ist aktiv, 0 heißt die Zahl ist nicht aktiv.)
    Man nimmt ein größeres Gitter, bzw. einen 9x9x9-Würfel, wobei die letzte Dimension die zugehörige Zahl im Sudokufeld bezeichnet. Das führt dann dazu, dass auch zwei (und mehr) Zahlen pro Feld aktiv sein können, aber in der richtigen Lösung ist’s natürlich nur eine. Wie man so ein Netz (insbesondere die Kopplungen) basteln kann, steht im Großen und Ganzen in diesem Artikel, in Kapitel 11. (allerdings sind die keine diskreten Spins am Werk, sondern Neurone mit kontinuierlichem Wertebereich zwischen 0 und 1. Ist sozusagen eine Art Mittelung über das Ensemble.). Alles in Allem war das damals eine kleine Tüftelaufgabe, die mir ziemlich viel Spaß gemacht hat.

  10. #10 MartinB
    26. Oktober 2012

    @Quacki
    Mit “lokal” meine ich, dass es in einem Ising-Modell die berühmte “taxi-driver”-distanz gibt – Punkte an entgegengesetzten Ecken sind nur indirekt über viele Schritte aneinander gekoppelt. Im Sudoku sind ja – wie oben gesagt – alle Punkte maximal über einen Zwischenscrhitt gekoppelt.

    Auf das 9^3-Gitter wäre ich nicht gekommen.