Im ersten Teil dieser Reihe haben wir versucht, die Steine eines Polyformpuzzles mit Hilfe einer (gefühlten oder gemessenen) Nützlichkeit zu ordnen und zuerst mit den am wenigsten nützlichsten Steinen zu beginnen. Im zweiten Teil haben wir Wege kennengelernt, die allerletzten Lücken zu füllen. Mit diesen zwei Methoden kann man wirklich extrem große Polyomino-Puzzles lösen, wie die folgende fast übermenschliche Leistung zeigt: Auf [1] finden Sie ganz unten eine Lösung, wie man die 1285 verschiedenen Enneominos (bestehend aus jeweils 9 Elementarquadraten) zusammen mit 60 Löchern (in symmetrischer Anordnung) in ein Rechteck der Größe 93x125 packen kann. Der Autor Lewis Patterson löste dieses Puzzle vollständig per Hand und benötigte dazu nach eigenen Angaben zwischen 11 und 12 Stunden. Im Bild sieht man sehr schön, dass zuletzt der Bereich oben in der Mitte und oben rechts gelöst wurde, dafür wurden die besonders nützlichen Steine mit Blöcken der Größe 2x2 und 2x3 aufgehoben.
Dieses Vorgehen funktioniert, weil die Anzahl von verschiedenen Lösungen derartig groß ist, dass man am Ende mit einer akzeptablen Anzahl von Substitutionsschritten eine Lösung findet. Mit anderen Worten, wenn man das Geduldspiel beinahe fertig gelöst hat und nur wenige Steine nicht passen (wir sprechen von einer Beinahe-Lösung), dann kann man diesen Mangel mit wenigen Veränderungen korrigieren und findet eine Lösung.
Teil 3: Mensch und Maschine gemeinsam
Wenn es für eine Aufgabe vergleichsweise weniger Lösungen gibt, dann befindet man sich mit einer Beinahe-Lösung nicht so nahe an einer vollständigen Lösung und man muss so viele Veränderungen vornehmen, dass man als Mensch überfordert ist. Dabei kann die Anzahl der Lösungen immer noch gigantisch groß sein, aber kleiner im Vergleich zu allen denkbaren Anordnungen der Steine.
Bei der Substitutionsmethode wurden nur ganz wenige Steine (1-3 Stück) entfernt und anders wieder eingefügt, um Platz für einen verbliebenen Stein zu schaffen. Wir können aber auch mehr Steine entfernen und versuchen, alle restlichen Steine passend einzufügen. Hier kann uns der Computer helfen. Wir benutzen den Computer also nur für die letzten Steine. Deren genaue Anzahl muss noch festgelegt werden, und zwar so, dass mit diesen Steinen (darunter möglichst viele nützliche Steine) fast jede Form passender Größe gefüllt werden kann. Dann sollte es doch auch für die Restfläche des Puzzles reichen.
Mit diesem Vorgehen hat man den Vorteil, dass der Computer sich nur mit wenigen Steinen beschäftigen muss, unabhängig von der Gesamtanzahl der Steine.
Für welche Polyformpuzzles ist dieser Ansatz erfolgversprechend? Sicher nicht für alle, denn wenn ein solches Polyformpuzzle nur eine einzige Lösung besitzt, kann man diese niemals durch Umlegen weniger Steine aus einer Beinahe-Lösung erzeugen. Dann müssen im typischen Fall alle Steine an eine andere Position gebracht werden.
Ein Beispiel von Livio Zucca [2] ist der quadratische Rahmen der Größe 210x210, gefüllt mit 4410 Decominos (aus je 10 Elementarquadraten) ohne Löcher. Es gibt insgesamt 4655 verschiedene Decominos, davon haben 4460 Decominos keine Löcher [3]. Es wurden also nicht alle Decominos verwendet. Wieder sieht man viele der nützlicheren Decominos in der rechten unteren Ecke. Wie üblich wurden die Decominos nach Nützlichkeit sortiert und dann in dieser Reihenfolge (die nützlichsten zuletzt) in den Rahmen von links oben nach rechts unten eingefügt. Wenn das Programm in einer Sackgasse landete, wurden manuell einiger der Steine anders positioniert und das Programm versuchte dann, mit dieser Hilfe eine Lösung zu finden. Nach einigen Dutzend solcher Versuche wurde die Lösung gefunden.
Ein zweites Beispiel stammt wieder von Lewis Patterson: Die 369 Oktominos sollen in neun Rechtecke der Größe 9x37 gepackt werden. Dabei befinden sich in jedem der neun Rechtecke 41 Oktominos und fünf Elementarquadrate bleiben frei. Diese freien Felder sollen sich wie im Bild in der Mitte jedes Rechtecks an der gleichen Stelle befinden.
Chris Patterson beschreibt seinen Lösungsvorgang in [4] so: Er konnte acht der neun Rechtecke per Hand füllen und war sich relativ sicher, dass sich mit den verbleibenden Steinen das letzte Rechteck füllen lässt. Allerdings gelang dies nicht per Hand und er bat die Community um Hilfe. Patrick Hamlyn gelang es schließlich mit Hilfe seines Computerprogramms, auch das letzte Rechteck zu füllen. Bevor dies aber gelungen war, scheiterte das Programm rund 866.000 mal mit entsprechend vielen Beinahe-Lösungen, bei denen jeweils 40 der 41 verbliebenen Oktominos in den Rahmen gepackt wurden. Hier war die Entscheidung, den Computer zu Hilfe zu nehmen, offensichtlich angebracht.
Mehr Quellen
Keine Kommentare:
Kommentar veröffentlichen