Das Puzzle besteht aus folgenden Teilen:
Diese sollen zu einem Wuerfel zusammengesetzt werden. Das Ergebnis sieht dann so aus:
Die folgenden Abschnitte stellen ein C-Programm zur Loesung dieses Puzzles und ein Povray-Script zur anschaulichen Darstellung der Loesung vor. Das Archiv wuerfel_v1.zip enthaelt alle benoetigten Dateien.
Zunaechst muessen die Puzzleteile in computerlesbarer Form beschrieben werden. Dazu wird jedes Teil in seinem eigenen Koordinatensystem beschrieben:
Die Beschreibungsdatei enthaelt 27 Zeilen, wobei in jeder Zeile zunaechst die Nummer des Teils (0..5) und dann die Koordinaten eines Elements des Teils stehen. Das erste Element jedes Teils hat die Koordinaten 0 0 0. Der Bezugspunkt muss so gewaehlt werden, dass die Koordinaten nicht negativ werden. Hier die ersten Zeilen der Datei blau.parts:
0 0 0 0 0 1 0 0 0 2 0 0 0 0 1 0 1 0 0 0 1 1 0 0 1 2 0 0 1 0 0 1 1 0 1 1 2 0 0 0 ...
Die vollstaendige Datei muss 27 Zeilen haben, da der Wuerfel aus 3*3*3=27 Teilelementen besteht.
Die Datei heisst uebrigens blau.parts, weil das orignale Puzzle aus blauen Kunststoffteilen besteht.
Das Programm wuerfel.c wird wie folgt uebersetzt und gestartet:
gcc -g -o wuerfel wuerfel.c ./wuerfel <blau.parts >out.pov
Ich verwende Suse Linux, es sollte aber mit jedem 32 Bit C-Compiler laufen. Der Code ist echtes VHIT = vom Hirn ins Terminal, also kein Muster an sauberer Programmierung.
Das Programm berechnet zunaechst in convertpart() von jedem Teil alle moeglichen Positionierungen im Loesungsraum. Diese werden als Bitmaske dargestellt - jedes Element des Loesungsraumes wird als ein Bit dargestellt - eine 1 bedeutet belegt.
Im zweiten Schritt werden in solve() durch rekursives Aufrufen alle moeglichen Kombinationen der Teile durchprobiert. Jede Loesung wird entsprechend der moeglichen Rotationen des Wuerfels 24 mal gefunden. Ein Aussortieren dieser Mehrfachloesungen ist nicht implementiert - es wird einfach die erste gefundene Loesung weiterverarbeitet.
Schliesslich wird in calcprio() noch eine Sortierung der Teile vorgenommen, damit die graphische Darstellung der Loesung schoener wird.
Die Ausgabe out.pov des Programms ist bereits fuer Povray formatiert.
Zur anschaulichen Darstellung der Loesung ist Povray gut geeignet. Das Script zur Darstellung wuerfel.pov laedt die Beschreibung der Loesung aus out.pov.
Der Aufruf lautet z.B.
povray +i wuerfel.pov +o blau.png -W1000 -H750 +FN16 xv blau.png &
Das Ergebnis ist folgende Zusammenbauanleitung (fuer's web aus xv als jpeg gespeichert):
Fuer andere Puzzleteile muss nur eine neue Beschreibungsdatei geschrieben werden. Die Teile muessen in einen 3*3*3-Wuerfel passen. Das Script fuer Povray geht von 6 Teilen aus, so dass bei einer anderen Anzahl von Teilen das Script entsprechend angepasst werden muss.
© 2005 Hans-Georg Köpken