Lösungsstrategien für Polyformen 1: Nützlichkeit

Einleitung

In dieser Serie von Posts sollen Lösungsstrategien für Geduldspiele mit Polyformen vorgestellt werden. In den Beispielen werden wir Polyominos verwenden, und zwar hauptsächlich Pentominos und Hexominos. Die meisten Aufgaben für Pentominos lassen sich zwar auch ohne solche theoretischen Hilfsmittel lösen, aber bei größeren Steinen und größeren Rahmen ist ein wenig theoretischer Hintergrund hilfreich. Und dies sowohl für den Menschen wie für den Computer. Denn auch der Computer kommt wegen des exponentiellen Wachstums der Zahl der möglichen Anordnungen schnell an seine Grenzen.

Die nachfolgenden Tipps sind nur dann nützlich, wenn es wirklich viele Möglichkeiten gibt, die Steine in den vorgegebenen Rahmen zu packen. Denn die Annahme ist immer, dass man erst gegen Ende wirklich sorgfältig vorgehen muss. Denn zunächst packt man (meist vom Rand beginnend, dann weiter nach innen) eine große Anzahl der Steine so in den Rahmen, dass nur in der Mitte ein großes Loch bleibt und keine weiteren Lücken. Irgendwann wird es schwieriger und wir hoffen nun, dass es immer noch möglich ist, dieses Loch zu füllen und somit eine Lösung zu finden, ohne allzuviel der bisher eingefügten Steine wieder anfassen zu müssen. Andererseits: Wenn es nur eine oder nur wenige Lösungen für das gesamte Puzzle gibt, wird diese Annahme sicher falsch sein. Dann gibt es für einzelne Steine nur eine (oder ganz wenige) mögliche Positionen, und Fehler zu Beginn lassen sich praktisch später nicht beheben. Die gute Nachricht ist aber, dass viele Aufgaben mit Polyformen aber sehr, sehr viele Lösungen haben und deshalb unser Ansatz funktionieren kann.

Teil 1: Für Mensch und Maschine: Nützlichkeit verschiedener Formen

Jeder, der schon mit Pentominos oder anderen ähnlich komplexen Steinen gearbeitet hat, weiß: Die Steine haben nicht nur verschiedenes Aussehen, sie verhalten sich auch anders. Manche sind "gutmütig", sie sind nützlicher als andere, weil sie sich oft auch zum Schluss noch in den Rahmen einfügen lassen. Andere wollen zum Schluss nur schlecht passen und werden deshalb gern am Anfang verbaut. Dann ist man sie los und hat nur noch die gutmütigen Steine unterzubringen.

Daraus lässt sich eine Strategie formulieren: In einem ersten Schritt werden die vorhandenen Steine in verschiedene Gruppen nach Nützlichkeit eingeteilt. Im zweiten Schritt werden die Steine  entsprechend ihrer Nützlichkeit verwendet, wobei die nützlichsten so spät wie möglich verwendet werden.

Für Menschen ist dies offensichtlich eine brauchbare Strategie, aber auch dem Computer ist damit geholfen. Bei Algorithmen wie dem Backtracking wird versucht, die Steine nacheinander in den Rahmen einzupassen. Bleiben hier zum Schluss möglichst gutmütige Steine, um die verbliebene Restfläche zu füllen, dann sind die Chancen für einen schnellen Erfolg höher.

Es bleibt die Frage, wie die Nützlichkeit ermittelt werden kann. Eine erste Möglichkeit besteht in der Auswertung der eigenen Erfahrung bei der Lösung entsprechender Aufgaben. Bei Pentominos können sich viele darauf einigen, dass P und F gutmütige Pentominos sind und das X am allerwenigsten gutmütig ist.

Wenn wir nun an größere Steine wie Hexominos, Heptominos usw. denken, benötigen wir brauchbare Kriterien, die auf der Form der Steine beruhen können oder auf wirklich messbaren Kriterien. 

Auf Grund ihrer Form gibt es vielleicht die folgenden Kriterien:

• lange gerade Stücken in Steinen sind nützlich (z.B. bei I und L), bei gradlinig begrenzten Rahmen werden viele davon am Rand benötigt.
• lange Stücken mit immer wiederkehrenden Formen an einer Seite lassen sich an mehreren Stellen zusammenfügen. Dies betrifft neben geraden Stücken auch treppenförmige Ränder. (W)
• 2x2-Blöcke in Steinen sind nützlich (bei P)
• Wenig Symmetrie erlaubt mehr verschiedene Möglichkeiten und ist nützlich (P, L, F, Y, ..)
• Viel Symmetrie erlaubt wenige verschiedene Möglichkeiten und ist weniger nützlich (I, X)
• Viele herausstehende "stachelige" Teile sind wenig nützlich (X)

Hier wurden Pentominos eingeordnet, aber auch bei größeren Steinen sind diese Kriterien sinnvoll. Für Pentominos, Hexominos und Heptominos erhält man so eine Einteilung der Steine in nützlich J und schwierig L. 

Gibt es eine Möglichkeit, diese Nützlichkeit automatisiert zu messen? Dem soll in einem eigenen Post über die Messung der Nützlichkeit nachgegangen werden.

Ein ähnliches Experiment stammt von Lewis Patterson [1] aus dem Jahr 2019.

Mehr Infos:

[1] https://polyominoes.blogspot.com/2019/04/the-most-useful-pentominoes-experiment.html