Die Lösung des Intermezzos

Vorgestern und gestern Abend habe ich mich endlich mal ernsthaft um das Holzpuzzle gekümmert. Ernsthaft heißt in diesem Fall, dass ich nur mit einem Ohr beim Fernsehkrimi oder der Fußballübertragung zugehört habe und meine Aufmerksamkeit stattdessen der Programmierung einer Suche nach einer Lösung gewidmet habe. Ein bisschen eingerostet sind meine Java-Programmierkenntnisse ja, aber gestern Abend um 23:30 Uhr war es dann endlich so weit, dass ich das Suchprogramm starten konnte.

          -   2   2   -   -
        -   -   2   -   0   -
      -   -   -   2   -   -   1
    -   -   -   -   2   1   1   -
  -   -   -   -   -   -   -   1   -
    -   -   -   -   -   -   -   1
      -   -   -   -   -   -   -
        -   -   -   -   -   -
          -   -   -   -   -

Etwa eine halbe Stunde lang sah ich den Programmausgaben zu und mir wurde klar, dass es noch viel Raum für Laufzeitverbesserungen gab. Während dieser Zeit hatte das Programm nämlich den Stein mit der Nummer 1 wie im Bild unten platziert und versuchte vergeblich, die verbleibenden freien Felder mit den restlichen 11 Puzzleteilen zu füllen. Die abgeschnittene Ecke mit den 2 freien Feldern kann natürlich nie gefüllt werden ...

Noch hatte ich die Hoffnung auf eine schnelle Lösungsfindung noch nicht verloren und ging erst einmal ins Bett. Als sich um 2:30 Uhr wie üblich aufwachte, habe ich mal kurz nachgesehen, wie weit das Programm war. Was soll ich sagen: Windows hatte wegen eines Updates den Rechner durchgestartet und dadurch das Programm abgebrochen! Ich habe es neu gestartet und das Programm analysierte die aussichtslose Position von oben aufs Neue ...

Heute früh um 6:30 Uhr hatte das Programm dann schon weitere Positionen für Stein 1 untersucht. In einer ersten Abschätzung kam ich auf eine vermutliche Laufzeit von etwa 300 Stunden. Unter der Dusche habe ich dann zunächst darüber nachgedacht, wie man Wiederaufsetzpunkte einbaut, damit der nächste Windows-Update nicht wieder alles kaputt macht. Und im Geiste entwickelte ich schon den Algorithmus zur Ermittlung der Zusammenhangskomponenten. Wenn man nach jedem Platzieren eines Steins nur dann in die Tiefe weitersucht, wenn die verbleibenden Zusammenhangskomponenten alle ein Vielfaches von fünf Feldern betragen, dann sollte das Programm noch vor dem Islandurlaub, der in 12 Tagen beginnt, fertig werden können.

Als ich nach der Dusche wieder an den Rechner kam, konnte ich meinen Augen kaum trauen: Das Programm hatte eine Lösung gefunden!

          2   2   2   2   b
        7   7   7   2   0   b
      7   1   8   8   8   b   b
    7   1   9   9   8   b   4   c
  1   1   a   9   9   8   4   4   c
    3   1   a   a   9   5   4   c
      3   3   3   a   5   4   c
        6   3   6   a   5   c
          6   6   6   5   5

In der Realität sieht das dann so aus:

Jetzt bin ich beruhigt, dass ich auch diese Aufgabe gelöst habe. Nochmal Danke an Maren und Joachim!
Weiter geht's am nächsten Samstag bei Horst und Renate in Hollingstedt.