Im Original von Tenyo sollen die 35 Hexominos in einen rechteckigen Rahmen der Größe 19x11 mit einem oben in der Mitte angesetzten Elementarquadrat gefüllt werden (siehe Aufgabe 1 der Hexomino-Aufgaben). Wem dies zu einfach ist, der kann sich darum bemühen, die Hexominos in diesem Rahmen auf möglichst elegante Weise anzuordnen.
Eine solche elegante Art ist die Zerlegung des Rahmens in sechs Rechtecke (wieder mit einem einzelnen angefügten Elementarquadrat), die jeweils aus 30, 36 oder 42 Elementarquadraten bestehen. Lässt sich auch dieser Rahmen mit den Hexominos füllen?
Diese Aufgabe ist unvergleichlich schwieriger, als ohne diese Zerlegung. Sie wurde bereits im Jahr 2000 von Ishino Keiichiro [1] gelöst. Eine vollständige Analyse ergab, dass es insgesamt 8507 Lösungen gibt. Wir wollen hier eine eigene Lösung finden und dabei so vorgehen wie beim Packen der Hexominos und Trominos in 6 Rahmen 6x6: Wir zerlegen die Aufgabe zunächst in sechs Teilaufgaben entsprechend der sechs Rahmenteile. Dann lösen wir diese Aufgabe einzeln. Im dritten Schritt suchen wir nach einer Kombination von sechs Lösungen der sechs Teilaufgaben (d.h. jeweils eine Lösung für jede Teilaufgabe), die insgesamt alle 35 Steine enthalten. Wenn uns das gelingt, haben wir eine Lösung gefunden.
Das Vorgehen ist analog wie beim Packen der Hexominos und Trominos in 6 Rahmen 6x6:
Im ersten Schritt werden mit dem Programm mops.exe Listen aller Lösungen für die vier verschiedenen Rahmen ermittelt. Zwei der Listen werden doppelt verwendet, da jeweils zwei Rahmen gleich groß sind. Alle Listen werden sortiert und dedupliziert, um Duplikate zu entfernen. Im zweiten Schritt wird mittels SMT-Solver aus jeder Liste eine Zeile ausgewählt, so dass alle Steine in den sechs Zeilen vorkommen. Dadurch kommt auch kein Stein in diesen ausgewählten Zeilen doppelt vor.
Damit haben wir die Nummern der Steine für jeden der sechs Rahmen und müssen diese noch einmal in die entsprechenden Rahmen packen, um endgültig eine Lösung zu finden.
Wieder haben wir zunächst keinerlei Vorstellungen, ob die Laufzeit einige Minuten, einige Tage oder gar Jahre betragen wird. Als Maßstab nehmen wir die bereits gelöste Aufgabe. Diese hatte mit den Trominos zwei zusätzliche Steine, könnte also komplizierter sein. Auch gab es nur zwei verschiedene Listen statt diesmal vier. Der bisher verwendete SMT-Solver findet in vertretbarer Zeit (ca. 1 Woche) keine Lösung, so dass nach alternativer Software gesucht wurde. Bei Python 3 findet man das Paket Ecact Cover [2], welches wiederum Numpy benutzt. Dort ist der so genannte Algorithmus X von Donald Knuth implementiert, welcher Exact-Cover-Probleme sehr effizient löst. Damit wurde die oben abgebildete Lösung als erste gefunden, und zwar nach zwei Tagen. Danach wurden weitere Lösungen in unterschiedlichen Zeitabständen gefunden, manchmal dauerte es nur Sekunden bis zur nächsten Lösung. Bis zum Abbruch nach 5 Tagen wurden rund 100 verschiedene Lösungen gefunden.
Mehr Infos:
[1] https://puzzlewillbeplayed.com/Hexominoes/
[2] https://github.com/jwg4/exact_cover
Keine Kommentare:
Kommentar veröffentlichen