Nein, in diesem Artikel geht es nicht darum, Sudoku-Hefte zu verbrennen. Aber mit etwas Phantasie kann man Sudokus tatsächlich als physikalische Objekte behandeln und dabei etwas über Thermodynamik lernen.

Sudokus sind ja bekanntlich Zahlenrätsel. Auch wenn ihr nie vom Sudoku-Fieber infiziert wart (war ich auch nie, habe nur einige Samurai-Sudoku und eine Handvoll leichter Killer-Sudoku gelöst) kennt ihr vermutlich die Regeln: Man hat ein Raster mit 9×9 Feldern und muss die Ziffern von 1 bis 9 so verteilen, dass in keiner Zeile, Spalte und in keinem Block eine Ziffer doppelt vorkommt. Am Anfang hat man bestimmte Hinweise, nämlich Felder, in denen schon Zahlen drinstehen. So sieht so etwas aus (geklaut von Wikipedia):

 

Sudoku problem 1.svg
Von WikipitEigenes Werk, CC BY-SA 3.0, Link

Und hier ist die Lösung:

Sudoku solution 1.svg
Von WikipitEigenes Werk, CC BY-SA 3.0, Link

Mit Physik hat das erst mal nicht viel zu tun, oder?

Aber PhysikerInnen haben ja manchmal eine seltsame Art zu denken und sehen die Welt auf ihre ganz eigene Weise. Und wenn man ein Sudoku mit PhysikerInnen-Augen ansieht, dann fällt einem vielleicht die Ähnlichkeit zu einigen physikalischen Modellen auf. Genau das haben A. Williams und G. Ackland getan – wobei ich auf den Artikel nur aufmerksam wurde, weil ich mit Graeme Ackland an einem gemeinsamen Projekt beteiligt war und ihn deshalb ein bisschen kenne.

In der Thermodynamik geht es ja darum, wie physikalische Systeme sich bei unterschiedlichen Temperaturen verhalten. Darüber kann man dicke Bücher schreiben (ich empfehle z.B. das von Reif), aber da das hier ein Blog-Eintrag ist, mache ich’s kurz (wobei das natürlich relativ ist, die kürzesten Blogeinträge der Welt schreibe ich ja nicht gerade). Eine etwas längere Einführung in viele thermodynamische Konzepte findet ihr natürlich auch hier auf dem Blog.

Das Grundprinzip hinter der Thermodynamik ist ziemlich simpel: Wir brauchen ein System, das in verschiedenen Zuständen existieren kann. 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 9 hoch 81 (danke, wereatheist) mögliche Zustände, also immerhin etwa 150 Billiarden (1,5e17) 2 mal 10 hoch 77.

In der Thermodynamik geht es außerdem immer um Temperaturen. Aus dem Alltag wisst ihr schon (auch wenn ihr vielleicht noch nie bewusst darüber nachgedacht habt), dass bei niedrigen Temperaturen Systeme bevorzugt in Zuständen mit niedriger Energie vorliegen. Deshalb gefriert Wasser zu Eis (weil die Eiskristalle energetisch günstig angeordnet sind) oder verdampft bei hoher Temperatur (wobei dann die Bindungskräfte zwischen den Molekülen sehr klein sind, so dass der Energiegehalt steigt). Zur Rolle der Energie habe ich übrigens auch mal was geschrieben.

Temperatur und Energie hängen also irgendwie zusammen. Bevor wir das klären, schauen wir erst einmal, wie man die Energie eines Sudokus definieren kann. Dazu schaut man sich an, wie falsch das Sudoku gelöst ist. Nehmen wir an, das Sudoku ist irgendwie mit Ziffern gefüllt. Klappert jetzt der Reihe nach jedes der 81 Felder ab. Fangen wir links oben an. Jetzt guckt ihr der Reihe nach alle Felder in derselben Zeile (also der obersten) an und jedesmal, wenn dort dieselbe Zahl steht wie im Feld links oben, dann macht ihr einen Strich (Fehler!). Dasselbe tut ihr für alle Felder in derselben Spalte und dann für alle Felder im selben Block. Mit anderen Worten, ihr sucht nach Fehlern – danach, ob diese Zahl, die ihr gerade anguckt, dafür sorgt, dass das Sudoku falsch ausgefüllt wurde. Alle diese Fehlerstriche (für alle 81 Felder) addiert ihr auf. Das ergibt dann eine Gesamtfehlerzahl, die man die Falschheit des Sudoku nennen könnte – aber weil wir Thermodynamik betreiben wollen, nennen wir sie die “Energie”. (Wer spitzfindig ist könnte einwenden, dass wir ja jeden Fehler doppelt zählen – einmal Feld X mit Feld Y, dann nochmal Feld Y mit Feld X. Man könnte alles nochmal durch zwei teilen, um das auszugleichen, aber da es ein konstanter Vorfaktor ist, spielt das hier keine Rolle und wir können das ignorieren.)

1 / 2 / 3 / 4 / Auf einer Seite lesen

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
    http://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.