Mehrere gleiche oder ähnliche Figuren aus einem Satz Polyominos legen

Wir haben schon Hexominos und Heptominos in Kisten gepackt, indem wir mehrere Quadrate gelegt haben und diese übereinander in eine Box packten. Wir hatten 

• Heptominos in einer 8x8-Box, gestapelt in 12 Schichten mit jeweils einem Loch an der gleichen Stelle, sowie
• Pentominos und Hexominos in einer 6x9-Box, gestapelt in fünf Schichten.

Die Überlegungen hier wollen wir später benutzen, um (wie im Bild) sechs Rahmen der Größe 6x6 mit Hexominos und Trominos zu füllen.

Wenn man keine Lösung kennt, wie findet man eine? Und wie findet man weitere Lösungen? Von Hand sind solche Aufgaben wirklich kaum mehr zu schaffen, und auch der Computer bekommt Probleme. Im Unterschied zu den üblichen Aufgaben mit nur einem großen Rahmen gibt es hier viel weniger Lösungen, und deshalb müssen viel mehr Möglichkeiten durchprobiert werden, bevor die erste Lösung gefunden wird. Die bisher betrachteten Algorithmen und Lösungsstrategien führen in vertretbarer Zeit nicht zum Ziel, weil die entsprechende Software mit der Komplexität der Aufgabe überfordert war oder auch nur nicht die passenden Einstellungen gefunden wurden.

Aber wir können noch einen zusätzlichen Trick anwenden und die schwierige Aufgabe, mehrere gleiche Rahmen mit allen Steinen zu füllen, in zwei einfachere Teilaufgaben zerlegen, von denen jede viel einfacher gelöst werden kann.

Angenommen, wir haben n gleiche Rahmen, die mit den Steinen gefüllt werden sollen.

1. Teilaufgabe: Fülle nur einen Rahmen vollständig mit Steinen und suche dafür nach allen Lösungen. Für jede Lösung notieren wir nur die verwendeten Steine, nicht deren tatsächliche Anordnung im Rahmen. Danach sortieren wir diese Liste der Lösungen und entfernen dabei Dubletten. Das Ergebnis ist eine Liste L aller Teilmengen von Steinen, mit denen sich ein Rahmen füllen lässt. Diese erste Teilaufgabe lässt sich mit verschiedenen Computerprogrammen schnell lösen.

2. Teilaufgabe: Suche in der Liste L nach n verschiedenen Zeilen, so dass insgesamt kein Stein doppelt vorkommt. Wenn wir n solche Zeilen finden, dann haben wir genügend verschiedene Steine, um alle n Rahmen zu füllen. Dabei müssen wir auch alle unsere Steine verwenden, da keine überzähligen Steine vorhanden sind. 

Für die zweite Teilaufgabe finden wir keine vorgefertigte Lösungssoftware und wir müssen selbst programmieren. Zur Auswahl stehen (mindestens) zwei verschiedene Lösungsansätze: Wir können wieder einmal einen SMT-Solver einsetzen. Als zweite Möglichkeit bietet sich an, die Aufgabenstellung als Problem der exakten Überdeckung (siehe [1]) zu betrachten. Auf dieses Exact Cover Problem und den dazugehörigen Algorithmus X von Donald Knuth soll in einen eigenen Post eingegangen werden.

Zur Lösung mit einem SMT-Solver verwenden wir die Liste L. in jeder Zeile stehen die Namen einiger Steine, die zusammen den Rahmen füllen. Wir benutzen die Namen der Steine als Variablen und wollen jeder von ihnen als Wert eine Zahl zwischen 1 und n zuweisen, je nachdem, im wievielten Rahmen der Stein verwendet wird. Dazu nehmen wir n Kopien unserer Liste L und nennen sie L1, L2, .. Ln. Nun machen wir folgendes. Wir suchen mit dem SMT-Solver nach einer Belegung der Variablen mit den Werten 1,..., n mit den folgenden Bedingungen.

(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)

Mit anderen Worten lassen wir den Solver nach einer Belegung mit Werten, so dass es für jede Zahl zwischen 1 und n eine Zeile in der Liste gibt, deren Variable alle diesen gleichen Wert haben. Mit diesen n Zahlen haben wir n disjunkte Lösungen für unsere n Rahmen. Jeder Stein wird nur einmal verwendet, da jede Variable mit nur einem Wert belegt werden kann.

Das Verfahren soll an einigen Aufgaben demonstriert werden:

• Hexominos und Tetrominos in 6 Rahmen 6x6
• Spezielle Hexomino-Lösung in 6 Teilen

Mehr Infos

[1] https://en.wikipedia.org/wiki/Exact_cover