Hexominos und Trominos in 6 Rahmen 6x6

Nimmt man zu den 35 Hexominos noch die zwei Trominos hinzu, so belegen diese 36*6+2*3 = 216 Elementarquadrate. Lässt sich daraus ein 18x12-Rechteck legen? Ja, aber diese Aufgabe ist uns heute viel zu einfach. Wir fragen uns: Lassen sich sechs Quadrate der Größe 6x6 mit den gegebenen Steinen füllen? Falls ja, brauchen wir diese 6 großen Quadrate nur in einem Rechteck der Größe 3x2 anzuordnen und fertig ist das 18x12-Rechteck mit einer sehr eleganten Unterteilung.

Um eine Lösung zu finden, gehen wir folgendermaßen in zwei Schritten vor, wie allgemein beschrieben, um mehrere gleiche oder ähnliche Figuren aus einem Satz Polyominos legen.

Für die erste Teilaufgabe erzeugen wir die Liste aller Lösungen für jeden einzelnen Rahmen. Da alle sechs Rahmen gleich sind, ergibt das nur eine Liste, die sich beispielsweise einfach mit mops.exe erzeugen lässt. Zuerst benötigt mops.exe die Steinmenge aus Trominos und Hexominos. Das geht am einfachsten, indem man zunächst die Hexominos als Steinmenge erzeugt und abspeichert. Danach erzeugt man die Trominos und lädt die Hexominos dazu. Damit verfügt man über die 37 Steine.

Als Rahmen (pattern) nimmt man ein 6x6-Quadrat und sucht nach allen Lösungen (>pack>all solutions). Dabei werden 2.574.456 Lösungen gefunden und diese werden automatisch abgespeichert. Danach wird die Liste mit einem kleinen Skript umformatiert, dass nur noch die Steinnummern enthalten sind und diese innerhalb der Zeile sortiert sind. Dann wird diese Liste zeilenweise sortiert und Dubletten werden entfernt (sort -u). Danach liegt die Liste L vor. Sie hat 84.614 Einträge.

Aus dieser Liste L erstellen wir nun die 6 Listen L1 bis L6 für die sechs Rahmen. Wir können ohne Beschränkung der Allgemeinheit die beiden Trominos in den ersten Rahmen packen, denn beide Trominos müssen ja in denselben Rahmen. Damit besteht L1 aus allen Einträgen von L, welche die Trominos enthalten, dies sind 70.904 Zeilen. Die Listen L2 bis L6 sind identisch und bestehen aus dem Rest von L, nachdem L1 entfernt wurde. Sie enthalten jeweils 13.710 Zeilen.

Für die zweite Teilaufgabe werden die Listen in eine logische Formel umgesetzt, für die später nach einer Lösung gesucht wird. Dies passiert genau wie in diesem Post beschrieben. Die Namen der Steine werden als Variablen betrachtet und ein langer logischer Ausdruck wird exakt genauso konstruiert:

(Alle Variablen in der ersten Zeile von L1 haben den Wert 1
ODER alle Variablen in der zweiten Zeile von L1 haben den Wert 1
ODER ...
ODER alle Variablen in der letzten Zeile von L1 haben den Wert 1)
UND
(Alle Variablen in der ersten Zeile von L2 haben den Wert 2
ODER alle Variablen in der zweiten Zeile von L2 haben den Wert 2
ODER ...

ODER alle Variablen in der letzten Zeile von L2 haben den Wert 2)
UND
...
UND
(Alle Variablen in der ersten Zeile von Ln haben den Wert n
ODER alle Variablen in der zweiten Zeile von Ln haben den Wert n
ODER ...
ODER alle Variablen in der letzten Zeile von Ln haben den Wert n)

Diesen Ausdruck übergeben wir dem SMT-Solver Z3 und hoffen, dass er in vertretbarer Zeit eine Lösung findet. Wenn wir die Größe des Ausdrucks betrachten, dann besteht er aus ### UND-Verknüpfungen (jede ODER-Zeile hat weitere 5 bzw. 6 UND-Verknüpfungen) und ### ODER-Verknüpfungen mit 37 Variablen. Wir haben zunächst keinerlei Vorstellungen, ob die Laufzeit einige Minuten, einige Tage oder gar Jahre betragen wird. Versuchen wir, es herauszufinden: Wir starten den Versuch auf einem normalen PC und binnen einiger Minuten und auch Stunden passiert erst einmal gar nichts. Aber nach knapp drei Tagen Laufzeit kommt die erste Lösung. Hier die Nummern der Rahmen für die 37 Steine.

1 1 1 5 3 4 5 6 3 3 2 4 1 4 2 2 6 3 6 5 3 6 5 4 6 1 2 2 6 5 2 3 1 4 4 5 1 

Dies bedeutet: Stein Nummer 1 erscheint im Rahmen1, ebenso die Steine 2 und 3. Stein Nummer 4 erscheint in Rahmen 5, Stein Nr. 3 in Rahmen 3 usw. Nach weiteren knapp 2 Tagen gibt es eine weitere Lösung 

1 1 2 2 4 6 5 5 2 6 1 4 3 5 5 2 3 5 6 3 6 4 5 1 1 3 2 6 3 4 2 3 4 6 1 4 1

und gleich darauf eine dritte, die allerdings nur die Steine in den Rahmen 2 und 4 vertauscht. Danach wurde der Prozess abgebrochen.

Um diese Nummern in eine echte Lösung für die sechs Rahmen zu verwandeln, müssen wir noch einmal die Aufgabe lösen, die Steine tatsächlich in den entsprechenden Rahmen zu packen. Hier ist das Ergebnis für die erste Lösung:

Historisches: Die Aufgabe wurde 1999 von Michael Reid gestellt. Da wusste man schon, dass es nicht möglich ist, sechs Rahmen der Größe 6x6 mit den 35 verschiedenen Hexominos sowie einem weiteren, doppelt verwendeten Hexomino zu füllen. Deshalb vermutet man nur vergleichsweise wenige Lösungen für die gestellte Aufgabe. Die erste Lösung wurde von Patrick Hamlyn gefunden [1] 

Mehr Infos:

[1] https://www.mathpuzzle.com/6x6x6.html