Polycube ist ein weiteres Programm (für Windows und Linux), mit dem man Polyomino-Aufgaben lösen kann. Es stellt sich die Frage, wozu ein weiteres Programm nötig ist. Deshalb erst einmal die wichtigsten Eigenschaften im Überblick:
- Polycube ist ein reines Kommandozeilen-Programm. Als Eingabe benötigt es die Beschreibung der Aufgabe in standardisierter Version, eine Ausgabedatei enthält die Lösungen der Aufgabe. Man mag das Fehlen einer grafischen Benutzeroberfläche bedauern, aber es hat auch Vorteile: Falls man viele Aufgaben lösen will, kann man Polycube mittels Stapelverarbeitung wiederholt aufrufen und vorher ggf. die Eingabedateien automatisch mit einem Skript erzeugen.
- Polycube lässt sich über viele Kommandozeilen-Parameter vielseitig steuern.
- Es gibt optionale Volumenfilter und Paritätsprüfung.
- Mehrere Backtracking-Algorithmen stehen zur Auswahl, während der Suche kann bei einem bestimmten Fortschritt der Algorithmus gewechselt werden.
- Für Backtracking mit dem Algorithmus DLX gibt es verschiedene Reihenfolgen zur Auswahl des nächsten Steins.
- Die Suche nach einer Lösung kann vorzeitig abgebrochen werden oder mit Monte-Carlo-Sampling kann die Suche in gewissen Zeitabschnitten randomisiert werden.
Für einfache Polyform-Aufgaben (z.B. für Pentominos) sind diese vielen Optionen nicht wirklich nötig, man erhält auch in den Standardeinstellungen praktisch sofort eine Lösung. Hier muss man sich um die Parameter nicht wirklich kümmern. Diese Vielfalt an Möglichkeiten wird dann interessant, wenn mit den Standardeinstellungen in vertretbarer Zeit keine Lösung gefunden wird und andere Programme auch nicht helfen. Dann hat man hier die reelle Chance, dass eine günstige Wahl der Parameter doch noch zu einer Lösung führt. Allerdings sind oft mehrere Versuche nötig.
Als Standard-Kommandozeile bietet sich Folgendes an:
polycube.exe -V -p -- Eingabedatei > Ausgabedatei
Dabei schaltet der Parameter -V den Volumentest ein und -p sorgt für eine Paritätsprüfung. Mehr Details gibt es bei [1]. Die Ausgabedatei enthält die Lösungen gut verständlicher Form. Hier ein Beispiel für die Pentominos in einem 8x8-Quadrat mit einem Loch der Größe 2x2 im Zentrum:
Hier im Blog wird immer angegeben, welches Programm zur automatischen Lösung verwendet wurde. Polycube wird meist für die Aufgabenserien für Polyominos sowie für einige schwierige einzelne Aufgaben. Für die Abbildungen der Lösungen wird die Textausgabe von polycube.exe in png-Bild umgewandelt.
Keine Kommentare:
Kommentar veröffentlichen