Lösungsstrategien für Polyformen 2: Substitution

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 die am wenigsten nützlichsten Steine zu benutzen. Dies entspricht der Eröffnung aus dem Schachspiel. Hier wollen wir uns dem Äquivalent des Endspiels widmen: Wie bringt man die allerletzten Steine unter? 

Teil 2: Die Substitutionsmethode für die letzten Steine

Zunächst wollen wir uns dem allerletzten Stein bei den Pentominos zuwenden: Elf der zwölf Steine befinden sich im Rahmen, und die fünf freien Elementarquadrate haben auch die Form eines Pentominos. Allerdings passt die Lücke nicht für das zwölfte Pentomino, sondern wir haben das fehlende Pentomino bereits verbaut. Diese Konfiguration soll in diesem Post als Beinahe-Lösung bezeichnet werden.

Wenn Sie jetzt aus Verzweiflung alle Steine wieder auf den Tisch schütten und es noch einmal von vorn versuchen, dann haben Sie vielleicht eine Chance verpasst: Vielleicht wäre die Beinahe-Lösung mit geringem Aufwand zu reparieren gewesen? Hier kommt die Substitutionsmethode ins Spiel. Sie besteht aus zwei Schritten. Die Ausgangssituation ist folgendermaßen: Die Beinahe-Lösung enthält eine Lücke in Form eines Steins A, zur Verfügung steht aber nur ein anderer Stein B.

Schritt 1: Entferne einen Stein C neben der Lücke, so dass sich die Lücke vergrößert. Prüfe, ob jetzt die beiden Steine B und C in die vergrößerte Lücke X passen. Falls ja, ist das Puzzle gelöst.

Beispiel 1: In der abgebildeten Situation haben wir eine Lücke in Form eines Y-Pentominos, der letzte vorhandene Stein ist ein F-Pentomino. Wir können die Situation aber retten, indem wir das neben der Lücke befindliche U-Pentomino entnehmen. Die entstandene größere Lücke können wir mit U und F füllen. Geschafft!

Falls dieser Schritt nicht zum Ziel führt, führe vorher eine Substitution aus: 

Schritt 2: Entferne den Stein A und füge ihn in die Lücke ein. Jetzt haben wir eine Situation wie vorher, nur dass sich Lücke in Form des Steins A an anderer Stelle befindet und wir immer noch den Stein B übrig haben. Aber wir können wieder Schritt 1 ausführen.

Beispiel 2: Nehmen wir eine andere Ausgangssituation. Angenommen, wir starten mit der unten abgebildeten Situation. Wieder  haben wir eine Lücke in Form eines Y-Pentominos, der übrige Stein ist das F-Pentomino. Der Trick aus Schritt 1, indem wir W oder Z herausnehmen, hilft an dieser Stelle nicht. Aber wenn wir zunächst die Lücke in Form eines Y mit dem Y-Pentomino füllen, haben wir die Situation auf die obige Situation aus Schritt 1 zurückgeführt und können alle Steine einfügen.

Falls wir wieder nicht zum Ziel kommen, können wir leider denselben Trick nicht noch einmal machen. Aber vielleicht können wir den Stein A in einer anderen Position in der großen Lücke einfügen, so dass eine kleine Lücke für einen anderen Stein als B bleibt. Dann können wir wieder Schritt 2 anwenden.

Wenn wir so gar nicht weiterkommen, können wir in Schritt 1 auch zwei oder mehr Steine entfernen und uns so noch viel mehr Möglichkeiten verschaffen. Wichtig ist, dass wir jetzt immer nur eine relativ kleine ungefüllte Lücke haben und nur wenige Steine bewegt werden müssen. Der Erfolg der Methode ist nicht garantiert, da man oft mehrere Möglichkeiten hat und sich für eine entscheiden muss. Im schlimmsten Fall kann man auch in einer Sackgasse landen und man hat keine weiteren Optionen. Aber verblüffend oft führt diese Strategie zum Ziel.

Dieses Vorgehen lässt sich auch gut auf den Computer übertragen. Im obigen Beispiel benötigt man ein Verzeichnis der möglichen größeren Lücken für zwei Steine sowie Paare von Steinen, die diese Lücke füllen. Beispielsweise lässt sich die Lücke

füllen durch jedes der folgenden Paare von Pentominos: F+U, L+P, P+T, P+V, P+Y, P+Z und U+Y. Daraus lassen sich jetzt die möglichen Substitutionen ableiten. Finden wir in der Lücke z.B. ein U-Pentomino, dann finden wir im Verzeichnis die folgenden Paare mit einem U: F+U und U+Y. Das bedeutet, dass wir in dieser Lücke ein F gegen ein Y substituieren können und umgekehrt. Genau das haben wir im Schritt 1 getan.

Diese Methode lässt sich genauso bei anderen Polyominos (und anderen Polyformen) verwenden, ein Beispiel für Hexominos findet sich bei [1].

Mehr Infos:

[1] polyominoes.blogspot.com/...