Hier wollen wir wieder auf die Aufgabe 2 der Sammlung von Heptomino-Aufgaben zurückkommen. Der Rahmen der Größe 33x23 lässt sich durch zwei senkrechte Schnitte in drei gleiche Teile zerlegen, jedes der Teile besteht aus 252=36*7 Elementarquadraten und enthält ein Loch genau im Zentrum. Lassen sich diese drei Teile mit den 108 Heptominos füllen?
Die Antwort ist ja, eine entsprechende Abbildung findet sich im Buch Polyominos [1] aus dem Jahr 1965, die dort abgebildete Lösung stammt von David Klarner. Sie wurde von Hand gefunden, wir wollen hier aber die Unterstützung des Computers in Anspruch nehmen.
Hier soll ein mögliches Vorgehen bei der Lösung der Aufgabe beschrieben werden sowie einige Versuche, die nicht zum Ziel geführt haben. Das liegt daran, dass entweder die entsprechende Software mit der Komplexität der Aufgabe überfordert war oder auch nur nicht die passenden Einstellungen gefunden wurden.
Die erste Idee besteht darin den vorgegebenen Rahmen "einfach so" durch ein Computerprogramm füllen zu lassen. Das wurde versucht mit den sonst oft erfolgreichen Programmen PolySolver, Polycube und mops.exe. Keines lieferte in vertretbarer Zeit eine Lösung, so dass im zweiten Versuch nach einer schrittweisen Lösung gesucht werden muss.
Hier bietet mops.exe als einziges Programm auf komfortable Weise alle Möglichkeiten an, um der Lösungsstrategie mit Berücksichtigung der der Nützlichkeit zu folgen. Wir bemühen uns, den ersten Rahmen zu füllen, indem wir möglichst viele Steine mit großer Nützlichkeit zurückhalten. Für den zweiten Rahmen erlauben wir außer den bisher unverwendeten Steinen einige weitere Steine, halten aber weiter die Steine mit der allergrößten Nützlichkeit zurück. Während wir beim ersten und zweiten Rahmen auf eine Lösung hoffen, weil wir mehr Steine zur Verfügung stellen als gebraucht werden, soll sich der dritte Rahmen füllen lassen wegen der großen Zahl nützlicher Steine, die wir für den letzten Schritt aufgehoben haben.
Soweit der Plan, aber die konkrete Umsetzung erfordert noch einige Entscheidungen, die über den Erfolg entscheiden werden. Im Folgenden wird der komplette Ablauf für eine erfolgreiche Lösung beschrieben.
Die globalen Einstellungen wurden folgendermaßen gewählt: Volumentest einschalten (Pack > Void Check), Paramenter für Breitensuche (Pack > Breadth): 40, Maximalzahl der Versuche, um die halbe Fläche zu füllen (Pack > Maximun Placements): 30.000. Zunächst keine zusätzlichen globalen Beschränkungen durch Rand (Bound > Boundary) oder Frequenz (Bound > Frequency).
Als erstes müssen die Heptominos sowie der zu füllende Rahmen beschafft werden. Beim Start von mops.exe werden Pentominos geladen, durch zweimaliges Pieces > Add Square verfügen wir über die gewünschten 108 Heptominos.
Dann muss die Nützlichkeit über die Verwendungshäufigkeit (Pack > Determine Frequency) ermittelt werden. Dazu kann man einen kleinen rechteckigen Rahmen der Größe 10x14 insgesamt 5.000mal füllen lassen. Dadurch erhält man z.B. Frequenzen zwischen 0 (für den Stein mit Loch) und 2665 mit einem Mittelwert von ca. 926.
Als nächstes benötigen wir den Rahmen der Größe 11x23. Er muss bei Pattern > Free Pattern von Hand gezeichnet werden, um das Loch in der Mitte einfügen zu können.
Um die Steine auszuwählen, die für das Füllen des ersten Rahmens zugelassen werden, wird eine maximale Frequenz vorgegeben, so dass zunächst möglichst viele Steine geringer Nützlichkeit verbraucht werden: Praktisch ist eine Maximalfrequenz von 1050, dann stehen 75 Steine zur Verfügung. Die Steine sind wegen ihrer geringen Frequenz schwierig zu benutzen, aber mit 75 Steinen haben wir viel mehr als die benötigten 36 zur Verfügung. Und die 33 nützlichsten Steine werden gar nicht benutzt.
Praktisch lassen sich die Steine auswählen mit Lock > Lock High Frequencies. Die dadurch gesperrten Steine hoher Frequenz werden jetzt nicht benutzt.
Das Füllen des Rahmens wird jetzt mit Pack gestartet und liefert nach einigen Sekunden eine Lösung. Es erweist sich als praktisch, wenn der Lösungsvorgang nicht blitzartig zum Erfolg führt. Geht es zu schnell, wurden mehr nützliche Steine verwendet als nötig und die Maximalfrequenz kann etwas heruntergesetzt werden, um in den späteren Schritten mehr nützliche Steine zur Verfügung zu haben.
Jetzt können wir die Lösung für Rahmen 1 abspeichern und uns Rahmen 2 widmen. Um die Steinmenge dafür geeignet einzuschränken, machen wir folgendes:
Lock > Unlock All gibt wieder alle Steine frei.
Lock > Lock Used Pieces sperrt die bereits im ersten Rahmen verbrauchten Steine.
Lock > Lock High Frequencies sperrt die nützlichsten Steine für den letzten Rahmen. Eine nützliche Grenze ist hier eine Frequenz von 1500. Dann stehen 57 Steine zur Verfügung, von denen 36 benötigt werden. Und für den dritten Rahmen heben wir uns die 15 allernützlichsten Steine auf.
Auch Rahmen 2 wird nach einigen Sekunden gefüllt und wir können die Lösung für Rahmen 2 abspeichern und uns dem letzten Rahmen widmen. Dazu müssen wir zunächst bereits alle verbrauchten Steine blockieren. Das klappt mit den folgenden Schritten:
Lock > Unlock All gibt wieder alle Steine frei.
Lock > Lock Used Pieces sperrt die soeben im zweiten Rahmen verbrauchten Steine.
File > Load Solution: Erste Lösung erneut laden
Lock > Lock Used Pieces sperrt die bereits ersten Rahmen verbrauchten Steine.
Damit sind genau 36 Steine für den letzten Rahmen übrig, darunter viele nützliche Steine, so dass wir optimistisch sein können eine Lösung für den dritten Rahmen zu finden. Aber ganz so einfach ist es nicht. Trotz der Volumenkontrolle hat das Programm ein Problem mit dem Stein mit Loch. Dieser wurde bisher noch nicht benutzt und das Programm hat offensichtlich Schwierigkeiten, in vertretbarer Zeit den Platz für diesen Stein so zu finden, dass er das Loch im Rahmen umschließt.
Also müssen wir hier eingreifen und helfen: Wir platzieren den Stein sozusagen von Hand. Weil die Software dies aber nicht direkt unterstützt, müssen wir etwas umständlicher vorgehen. Erstens blockieren wir den Stein mit Loch von Hand mittels Anklicken bei View > Pieces. Und zweitens erweitern wir das Loch in der Mitte des dritten Rahmens so, dass dort zum Schluss genau der Stein mit Loch hineinpasst.
Jetzt muss nur noch der veränderte Rahmen mit den übrigen 35 Steinen gefüllt werden. Wir starten mit Pack und warten. Binnen Sekunden wird diesmal leider keine Lösung gefunden. Wenn uns das Warten zu lange dauert, können wir noch die im Programm eingebaute Strategie verwenden, dass die nützlichsten Steine erst möglichst spät verwendet werden. Setzen wir bei Bound > Frequency die Zahlen L=1500, S=15 und R=140, so bedeutet dies: Die nützlichen Steine mit Frequenz <1500 dürfen nur 15% aller verwendeten Steine ausmachen, solange noch 140 Elementarquadrate frei sind. Mit anderen Worten, für die restlichen 140 Elementarquadrate sollen möglichst viele nützliche Steine zur Verfügung stehen, so dass auch eine Lösung gefunden wird. Und tatsächlich wird nach ca. drei Minuten auch der dritte Rahmen erfolgreich gefüllt. Hier der Original-Screenshot von mops.exe:
Im allerletzten Schritt müssen wir nun den fehlenden Stein in der Mitte wieder einfügen und die drei Teillösungen zusammenfügen.
Bei dieser Lösung sieht man deutlich, dass im dritten Rechteck deutliche mehr nützliche Steine verwendet wurden als in den ersten beiden: Es gibt mehr 2x2-Blöcke in den Steinen und Steine mit langen, geraden Kantenstücken. Die verwendete Strategie ist also im Ergebnis noch erkennbar.
Mehr Infos:
[1] Solomon W. Golomb: Polyominoes: Puzzles, Patterns, Problems, and Packings - Revised and Expanded Second Edition (Princeton Science Library), 1996
