Ungewöhnliche Formen
Bei Pentominos werden fünf Elementarquadrate auf alle möglichen Arten in einem Quadratgitter zusammengesetzt und so erhält man die zwölf Pentominos. Man kann die Zahl fünf variieren und erhält beispielsweise Tetrominos (aus vier Elementarquadraten) oder Hexominos (aus sechs). Aber man kann auch die Elementarquadrate durch andere Formen ersetzen. Statt Elementarquadraten kann man mit Dominos starten und man kann auch diagonal halbierte Quadrate oder Dominos (also jeweils Dreiecke) anfügen. Dies passiert so, dass man niemals das zugrundeliegende Quadratgitter verlässt.
Es gibt beispielsweise acht Steine bestehend aus einem Domino und einem diagonal halbierten Domino. Diese haben zusammen eine Fläche von 24 Elementarquadraten und lassen sich zu einem Rechteck der Größe 4x6 packen.
Die folgenden Steine bestehen jeweils aus einem Elementarquadrat, einem halben Elementarquadrat sowie aus einem halben Domino. Es gibt 32 solcher Steine mit einer Gesamtfläche von 80 und die sind im folgenden Bild zu einem 8x10-Rechteck angeordnet.
Weitere Attribute
Das Programm kann mit weiteren Attributen umgehen. So können wir einseitige Steine verwenden (diese dürfen dann nicht gewendet werden). Polyominos können mit Schachbrettmuster versehen werden oder auch polarisiert (d.h. gestaucht) werden. Mehrere Attribute können kombiniert werden, und diese Attributliste ist auch nicht vollständig.
Beispielsweise gibt es 18 Pentominos mit Schachbrettmuster, und diese lassen sich zu einem 9x10-Rechteck anordnen.
Viele Teile
Aufgaben mit vielen Polyominos werden schnell schwierig und bereiten auch dem Computer oft Schwierigkeiten. Dies kommt daher, dass die Anzahl der zu betrachtenden Möglichkeiten mit der Anzahl der Steine exponentiell wächst. Dies ist zumindest wahr, wenn man die Gesamtzahl aller möglichen Lösungen für eine Aufgabe wissen möchte.
Einfacher wird die Situation, wenn wir mit einer einzigen Lösung oder wenigen Lösungen zufrieden sind, es aber insgesamt sehr viele Lösungen gibt. Das bedeutet aber nicht, dass man eine dieser vielen Lösungen auch schnell findet. Im Extremfall findet man Millionen von Beinahe-Lösungen, bei denen man alle bis auf einen Stein einfügen kann, bevor auch der letzte Stein passt. Hier helfen Strategien, die über normales Bachtracking hinausgehen und in der Reihe über Lösungsstrategien für Polyformen vorgestellt wurden (Teil1, Teil2 und Teil3). Dies soll hier praktisch angewendet werden.
Einige der implementierten Lösungsstrategien sollen hier kurz vorgestellt werden:
- Die Nützlichkeit der einzelnen Steine lässt sich vor Beginn der eigentlichen Lösung berechnen. Bei der Lösung können die nützlichsten Steine bis zuletzt aufgehoben werden.
- Es gibt die Möglichkeit, Steine möglichst so anzulegen, dass die Fläche des gelösten Teils möglichst kompakt ist.
- Der Algorithmus verwendet eine randomisierte Breitensuche. Mit einem Parameter kann die Breite der Suche gesteuert werden.
- Die Anzahl der Schritte, um die Hälfte der Fläche zu füllen, kann beschränkt werden.
Keine Kommentare:
Kommentar veröffentlichen