Zusammengewürfelt
Bei Computerspielen denken die meisten an dreidimensionale Ego-Shooter, teure 3D-Grafikkarten und hochgezüchtete Prozessoren. Es gibt aber auch eine kreativere Art, mit dem Computer zu spielen, bei der Grips mehr ausrichten kann als Rechenpower.
- Dr. Harald Bögeholz
Eigentlich ist es ja dafür gedacht, von Hand gelöst zu werden, das Holzpuzzle, das Kollege Stiller neulich zum Geburtstag bekommen hat. Neun Teile aus jeweils drei rechtwinklig zusammengesetzten kleinen Würfeln (siehe folgende Abbildung) müssen zu einem größeren 3 x 3 x 3-Würfel zusammengesetzt werden. Damit das nicht so einfach ist, haben die Teile verschiedene Bohrungen, und das Ziel ist ein Würfel, bei dem die Löcher jeweils ganz durchgehen (siehe Aufmacher-Foto).
Das Rumprobieren mit Puzzleteilen ist nicht so meine Sache. Da schreibe ich doch lieber ein Computerprogramm, das mir diese ‘Arbeit’ abnimmt. Also flugs den C++-Compiler rausgekramt und ein bisschen nachgedacht. Schließlich soll das Programm ja nicht nur funktionieren, sondern auch in endlicher Zeit fertig werden.
Der im Folgenden vorgestellte Lösungsansatz lässt sich auf vielfache Weise verallgemeinern, zum Beispiel auf verschieden geformte Puzzleteile oder Teile mit anderen Attributen als Löchern, etwa Kerben oder Farben. Soma-Würfel und Pentomino-Puzzles, die ebenfalls aus Würfeln zusammengesetzt sind, lassen sich zum Beispiel mit derselben Technik sehr effizient lösen. Um das Programm nicht zu überfrachten, habe ich aber auf allzu viel Allgemeinheit verzichtet und es auf die Lösung dieses speziellen Problems zugeschnitten. Den vollständigen C++-Quelltext sowie eine ausführbare Version für Windows finden Sie über den Soft-Link am Ende des Artikels zum Download.
Ans Werk
Grundsätzlich ist die Vorgehensweise klar: Systematisch alle Kombinationen ausprobieren. Also ein Teil hinlegen, ein weiteres dazu und so weiter, bis man irgendwann an einen Punkt kommt, wo kein Teil mehr passt, ohne irgendwelche Löcher wieder zu verbauen. Dann das letzte gelegte Teil zurücknehmen und was anderes probieren, später eventuell auch das vorletzte zurücknehmen und so weiter, bis alle Lösungen gefunden sind - ein klassischer ‘Backtracking’-Algorithmus.
So etwas lässt sich schön rekursiv programmieren: Man schreibt eine Funktion, die ein Teil auf alle möglichen Arten hinlegt und dann jeweils sich selbst aufruft, um das nächste und in Folge alle Kombinationen der übrigen Teile durchzuprobieren.
Dabei orientiere ich mich am Zielkörper: Erst versuche ich, das Würfelchen in der linken unteren Ecke zu füllen, dann das benachbarte und so weiter, sodass die Lösung schichtweise von vorn nach hinten und von unten nach oben aufgebaut wird. Würde ich stattdessen stur ein Teil nach dem anderen in einer festen Reihenfolge verbauen, dann würden recht früh Hohlräume entstehen, in die kein Teil mehr passt, und das Programm würde viel Zeit mit dem Durchprobieren ohnehin aussichtsloser Kombinationen verpulvern.
Das gilt es unbedingt zu vermeiden, denn sonst wäre die Rechenzeit ‘unendlich’, wie eine kurze Überschlagsrechnung ergibt. Ohne es zu drehen, passt so ein winkelförmiges Teil auf vier verschiedene Arten in die Grundfläche, mal drei Stockwerke ergibt zwölf Möglichkeiten. Außerdem gibt es 24 mögliche Orientierungen eines (vollständig asymmetrischen) Teils im Raum. Das macht man sich am leichtesten klar, indem man an einen Spielwürfel denkt: Erst wählt man gedanklich eine Fläche, die oben liegt (6 Möglichkeiten). Dann gibt es noch vier Möglichkeiten, die vordere Fläche zu wählen, macht insgesamt 6 · 4 = 24 Möglichkeiten. 24 Orientierungen mal jeweils zwölf Verschiebungen ergibt 288 Kombinationen. Das hoch neun (und durch 2 dividiert, weil Teil Nummer 7 symmetrisch ist), ergibt 7 · 1021 Kombinationen von 9 Teilen. Diese Zahl ist natürlich viel zu hoch gegriffen, weil sie auch Anordnungen mit überlappenden Teilen enthält, zeigt aber, dass man gut daran tut, den Suchbaum möglichst pfiffig zu beschneiden und auch sonst ein bisschen an effiziente Programmierung zu denken.
Dabei kommen mir als Nächstes die Datenstrukturen in den Sinn: Wie stelle ich das Puzzle am besten dar? Um zu prüfen, ob ein Teil in einer bestimmten Orientierung in den Zielwürfel passt, genügt es zu wissen, welche Felder belegt und welche frei sind. Das lässt sich mit einem einzigen Bit pro Feld ausdrücken, insgesamt also 3 · 3 · 3 = 27 Bit. Eine mögliche Orientierung eines Teils kann man ebenfalls mit solch einem 27-bittigen ‘Bitvektor’ beschreiben, in dem genau drei Bit für die Lage der drei Einzelwürfel gesetzt sind. Der Test, ob ein Teil in dieser Lage an eine bestimmte Stelle des Spielfelds passt, reduziert sich damit auf eine bitweise Und-Verknüpfung: Nur wenn das Ergebnis Null ist, kollidiert das Teil mit keinem bereits gelegten.
Bit für Bit
27 Bit passen bequem in einen 32-bittigen Integer. Damit sich das Programm auf größere Puzzles erweitern lässt, habe ich diesen in eine Klasse Bitvector gepackt, die sich bei Bedarf zu einem Array aus Integern aufbohren lässt:
class Bitvector
{
unsigned int word;
public:
Bitvector::Bitvector(void) { word = 0; }63
void set(const Bitvector& bv) { word |= bv.word; }
void set(int bit) { word |= 1 << bit; }
bool test(const Bitvector& bv) const
{ return (word & bv.word) != 0; }
bool test(int bit) const
{ return (word & (1 << bit)) != 0; }
bool operator== (const Bitvector& bv) const
{ return word == bv.word; }
};
Die Zuordnung der Felder zu den einzelnen Bits ist eine Eigenschaft des Puzzles, weswegen sie in die noch weiter auszuführende Klasse Puzzle wandert:
inline int Puzzle::pos_to_bit(int x, int y, int z)
{ return z*9 + y*3 + x; }
Die Felder werden also von links nach rechts, von vorne nach hinten und dann von unten nach oben durchnummeriert (siehe folgende Abbildung). Jetzt fehlt noch eine Datenstruktur für die Löcher. Es gibt 27 mögliche Bohrungen durch den Würfel, 9 in jeder Raumrichtung. Ich nummeriere sie entsprechend der übernächsten Abbildung durch: Erst die 9 Bohrungen parallel zur x-Achse, dann die parallel zur y-Achse und schließlich die in z-Richtung. Für jede muss ich im Verlauf der Lösungssuche drei Zustände unterscheiden: Loch, kein Loch und ‘unentschlossen’. Dafür genügen zwei Bitvektoren à 27 Bit: einer für Löcher und einer für ‘Nicht-Löcher’. Wenn an einer Stelle in keinem der beiden Vektoren ein Bit gesetzt ist, liegt noch kein Teil auf der entsprechenden Achse (‘unentschlossen’).
Als Nächstes geht es daran, alle möglichen Lagen eines Teils im Raum zu erzeugen. Das mache ich zweckmäßigerweise nur einmal zu Beginn des Programms und lege das Ergebnis in einer Tabelle ab, damit ich nicht in der eigentlichen Backtracking-Routine dauernd mit geometrischen 3D-Transformationen hantieren muss. Die Maximalgröße dieser Tabelle steht nach den einleitenden Bemerkungen fest: 288 verschiedene Lagen kann ein Teil im Zielwürfel höchstens einnehmen:
const int MAX_PARTPOS=288;
Sieben mögliche Bohrungen gibt es in den L-förmigen Teilen dieses Puzzles, je zwei in x- und y- und drei in z-Richtung. Damit nimmt die Klasse Part, die ein Puzzleteil repräsentiert, allmählich Gestalt an. Der Konstruktor benötigt sieben boolesche Parameter für die Bohrungen. Er errechnet daraus alle möglichen Lagen des Teils in der Zielfigur und speichert für jede mögliche Lage drei Bitvektoren in einer Tabelle: bvPos[ i ] für die vom Teil belegten Zielfelder, bvHole[ i ] für die durch das Teil festgelegten Löcher und bvNonHole[ i ] für die Nicht-Löcher. Zusammen mit ein paar Hilfsfunktionen (siehe unten) ergibt sich die Klassendeklaration
class Part
{
bool hx0, hx1, hy0, hy1, hz00, hz10, hz01;
void twist(void);
void turn( int [3][3],
int, const Projection&);
void place( int [3][3],
int, const Projection&,
int, const Projection&);
public:
Bitvector bvPos[MAX_PARTPOS];
Bitvector bvHole[MAX_PARTPOS];
Bitvector bvNonHole[MAX_PARTPOS];
int nbv; // number of Bitvectors
Part(bool, bool, bool, bool, bool, bool, bool);
};
Der Konstruktur birgt wenig Überraschungen, da er die eigentliche Arbeit einer Hilfsfunktion überlässt:
Part::Part(bool hx0, bool hx1, bool hy0, bool hy1,
bool hz00, bool hz10, bool hz01)
{
Part::hx0 = hx0; Part::hx1 = hx1;
Part::hy0 = hy0; Part::hy1 = hy1;
Part::hz00 = hz00; Part::hz10 = hz10; Part::hz01 = hz01;
nbv = 0;
twist();
printf("Teil initialisiert: %d mögliche Lagen\n", nbv);
}
C++-Kenner mögen mir das printf verzeihen - ich mag die iostreams einfach nicht. Um alle möglichen Orientierungen im Raum zu erzeugen, lege ich in der Funktion twist() zunächst eine Raumrichtung fest, in die der in den Abbildungen nach rechts weisende Schenkel des Puzzleteils zeigt und speichere sie in der ersten Spalte der Matrix m[][]. m[0][0] gibt also an, was man zur x-Koordinate addieren muss, um sich in die entsprechende Richtung zu bewegen, entsprechend m[1][0] für die y-Koordinate und m[2][0] für die z-Koordinate.
Bei der Raumrichtung herrscht freie Auswahl; für jede der sechs Möglichkeiten rufe ich turn() auf und lege dort die Raumrichtung für den zweiten Schenkel des winkelförmigen Teils fest. Sie landet in der zweiten Spalte der Matrix, also m[...][1]. Hierfür gibt es nur noch vier Möglichkeiten, da der zweite Schenkel mit dem ersten ja einen rechten Winkel bilden muss.
Drehen und wenden
Wenn man ein Teil dreht, drehen sich natürlich auch die Löcher mit. Auf der Suche nach einer eleganten Möglichkeit, ein irgendwie gedrehtes Loch auf die entsprechende Seitenfläche und schließlich eine Bit-Nummer abzubilden, habe ich mir folgendes überlegt: Ein Loch an der Position (x, y, z), das in einer bestimmten Raumrichtung verläuft, beispielsweise in y-Richtung, muss entlang dieser Richtung auf eine Seitenfläche abgebildet werden. Dabei fällt eine der drei Koordinaten, nämlich die Projektionsrichtung, unter den Tisch, und die beiden anderen ergeben die Bit-Nummer innerhalb der betreffenden Ebene, im Beispiel x + 3 · z. Hinzu kommt der Offset in den Bitvektor, im Falle der y-Richtung 9. Eine kleine Klasse hilft, diese Projektion kürzer hinzuschreiben:
class Projection
{
int fx, fy, fz, fo;
public:
void set(int ffx, int ffy, int ffz, int ffo)
{ fx = ffx; fy = ffy; fz = ffz; fo = ffo; }
int to_bit(int x, int y, int z) const
{ return x*fx + y*fy + z*fz + fo; }
};
Um wie im Beispiel eine Projektion in y-Richtung auszudrücken, initialisiert man sie mit set(1, 0, 3, 9). Damit ist das Rüstzeug beisammen, um alle möglichen Orientierungen im Raum zu erzeugen:
void Part::twist(void)
{
int m[3][3];
Projection xaxis;
for (int i=0; i<3; ++i)
for (int j=0; j<3; ++j)
m[ i ][ j ] = 0;
xaxis.set(0, 1, 3, 0);
m[0][0] = 1; turn(m, 0, xaxis);
m[0][0] = -1; turn(m, 0, xaxis);
m[0][0] = 0;
xaxis.set(1, 0, 3, 9);
m[1][0] = 1; turn(m, 1, xaxis);
m[1][0] = -1; turn(m, 1, xaxis);
m[1][0] = 0;
xaxis.set(1, 3, 0, 18);
m[2][0] = 1; turn(m, 2, xaxis);
m[2][0] = -1; turn(m, 2, xaxis);
m[2][0] = 0;
}
void Part::turn(int m[3][3],
int i, const Projection& xaxis)
{
Projection yaxis;
if (i != 0)
{
yaxis.set(0, 1, 3, 0);
m[0][1] = 1; place(m, i, xaxis, 0, yaxis);
m[0][1] = -1; place(m, i, xaxis, 0, yaxis);
m[0][1] = 0;
}
if (i != 1)
{
yaxis.set(1, 0, 3, 9);
m[1][1] = 1; place(m, i, xaxis, 1, yaxis);
m[1][1] = -1; place(m, i, xaxis, 1, yaxis);
m[1][1] = 0;
}
if (i != 2)
{
yaxis.set(1, 3, 0, 18);
m[2][1] = 1; place(m, i, xaxis, 2, yaxis);
m[2][1] = -1; place(m, i, xaxis, 2, yaxis);
m[2][1] = 0;
}
}
Ist das Teil erst einmal gedreht und gewendet, muss ich es noch verschieben und schließlich die entsprechenden Bits in den Bitvektoren für Position, Löcher und Nicht-Löcher setzen. Das macht die Funktion place(), die ich im Folgenden häppchenweise präsentiere. Zunächst legt sie die Projektion für die z-Richtung so fest, dass sie in die nach x und y noch übrige Raumrichtung weist.
void Part::place(int m[3][3],
int i, const Projection& xaxis,
int j, const Projection& yaxis)
{
Projection zaxis;
int n;
if (i != 0 && j != 0) zaxis.set(0, 1, 3, 0);
if (i != 1 && j != 1) zaxis.set(1, 0, 3, 9);
if (i != 2 && j != 2) zaxis.set(1, 3, 0, 18);
m[0][2]=m[1][0]*m[2][1]-m[1][1]*m[2][0];
m[1][2]=m[0][1]*m[2][0]-m[0][0]*m[2][1];
m[2][2]=m[0][0]*m[1][1]-m[1][0]*m[0][1];
...
Die dritte Spalte der Transformationsmatrix ergibt sich aus den ersten beiden als derjenige Vektor, der senkrecht auf den beiden anderen steht und die richtige Orientierung aufweist (Mathe-Cracks erkennen hier das Kreuzprodukt). Da die Teile dieses speziellen Puzzles alle flach sind, wird die dritte Spalte der Matrix allerdings gar nicht benötigt. Ich habe die letzten drei Zeilen daher in der endgültigen Programmversion auskommentiert.
Jetzt schiebe ich das Teil an alle möglichen Positionen innerhalb des Würfels, wobei ich mich jeweils vergewissern muss, dass die beiden Schenkel nicht über den Würfelrand herausragen:
for (int z=0; z<3; ++z)
for (int y=0; y<3; ++y)
for (int x=0; x<3; ++x)
if (0 <= x+m[0][0] && x+m[0][0] < 3 &&
0 <= x+m[0][1] && x+m[0][1] < 3 &&
0 <= y+m[1][0] && y+m[1][0] < 3 &&
0 <= y+m[1][1] && y+m[1][1] < 3 &&
0 <= z+m[2][0] && z+m[2][0] < 3 &&
0 <= z+m[2][1] && z+m[2][1] < 3)
{ /* Bitvektoren bauen und abspeichern */ }
Nach diesen Vorbereitungen kommt innerhalb der Schleife die eigentliche Arbeit. Zunächst konstruiere ich den Bitvektor bvNewPos, in dem genau die drei Bits gesetzt sind, die der aktuellen Position des Teils im Würfel entsprechen:
Bitvector bvNewPos;
bvNewPos.set(Puzzle::pos_to_bit(x, y, z));
bvNewPos.set(Puzzle::pos_to_bit(x+m[0][0], y+m[1][0],
z+m[2][0]));
bvNewPos.set(Puzzle::pos_to_bit(x+m[0][1], y+m[1][1],
z+m[2][1]));
Als Nächstes kommen die beiden Bitvektoren für die Löcher und die Nicht-Löcher an die Reihe. Für jede der sieben möglichen Bohrungen durch das Teil projiziere ich diese zunächst auf die ihrer Lage entsprechende Bit-Nummer und setze das Bit entweder in bvNewHole, wenn das Teil hier ein Loch hat, oder ansonsten in bvNewNonHole. Die Variablen für die Bohrungen sind gemäß der folgenden Abbildung benannt.
Bitvector bvNewHole;
Bitvector bvNewNonHole;
if (hx0)
bvNewHole.set(xaxis.to_bit(x, y, z));
else
bvNewNonHole.set(xaxis.to_bit(x, y, z));
if (hx1)
bvNewHole.set(xaxis.to_bit(x+m[0][1], y+m[1][1],
z+m[2][1]));
else
bvNewNonHole.set(xaxis.to_bit(x+m[0][1], y+m[1][1],
z+m[2][1]));
if (hy0)
bvNewHole.set(yaxis.to_bit(x, y, z));
else
bvNewNonHole.set(yaxis.to_bit(x, y, z));
// ähnlicher Code für vier weitere mögliche Bohrungen
Die drei so konstruierten Bitvektoren bvNewPos, bvNewHole und bvNewNonHole beschreiben jetzt die Lage des Teils im Raum sowie seinen Einfluss auf die Löcherverteilung. Bevor ich diese in die Tabelle aufnehme, schaue ich aber zuerst, ob sie schon drinstehen:
for (n=0; n<nbv; ++n)
if (bvPos[n] == bvNewPos &&
bvHole[n] == bvNewHole &&
bvNonHole[n] == bvNewNonHole)
break;
if (n == nbv)
{
bvPos[nbv] = bvNewPos;
bvHole[nbv] = bvNewHole;
bvNonHole[nbv++] = bvNewNonHole;
}
Das Durchsuchen der bisherigen Tabelle wäre bei vollkommen asymmetrischen Teilen überflüssig. Bei diesem Puzzle ist aber Teil Nummer sieben symmetrisch, und so ergeben sich nur 144 echt verschiedene Lagen dieses Teils in der Zielfigur.
Zur Erinnerung: Alles bisher Programmierte findet im Konstruktor von Part statt und dient dazu, als Vorbereitung für den eigentlichen Backtracking-Algorithmus für jedes Teil all seine möglichen Lagen im Zielwürfel in Form von Bitvektoren zu kodieren und in Tabellen abzulegen. Bevor es an die eigentliche Lösung geht, hier erst einmal zur Entspannung das Hauptprogramm: neun Teile reinstecken in ein Puzzle, lösen und fertig:
int main(int argc, char *argv[])
{
printf("lochwuerfel 0.1 (C)2003 by Harald Bögeholz\n");
Part parts[] =
{
Part(false, true, false, false, true, false, false),
Part(false, false, false, true, false, true, false),
Part(false, true, false, false, true, false, true),
Part(false, false, true, false, false, true, false),
Part(false, true, true, false, true, false, false),
Part(true, false, false, true, false, false, true),
Part(true, false, true, false, true, false, true),
Part(false, false, false, false, false, true, true),
Part(false, false, true, false, true, false, true)
};
Puzzle puzzle(parts);
puzzle.solve();
return 0;
}
Jetzt geht es ans eigentliche Lösen. Das findet in der Klasse Puzzle statt, die dazu ein paar Hilfsvariablen benötigt, unter anderem ein Array part_used[], in dem steht, welche Teile schon weg sind und ein Array part_pos[], das für jedes Teil angibt, in welcher seiner möglichen Lagen es verbaut wurde:
const int nparts=9;
const int flatbits=27;
class Puzzle
{
Part *parts;
bool part_used[nparts];
int nsolutions; // Anzahl gefundener Lösungen
int part_pos[nparts];
void solve1(Bitvector, Bitvector, Bitvector, int);
void found_solution(Bitvector);
public:
static int pos_to_bit(int, int, int);
Puzzle(Part *);
void solve(void);
};
Puzzle::Puzzle(Part *parts)
{
Puzzle::parts = parts;
nsolutions = 0;
for (int i=0; i<nparts; ++i)
part_used[ i ] = false;
// hier kommt später noch ein "Symmetrie-Hack" hin
}
Zum Lösen des Puzzles gehe ich von einem leeren Spielfeld in Form der drei nagelneuen Bitvektoren bvField, bvHole und bvNonHole aus und rufe damit die rekursive Backtracking-Routine solve1() auf. Deren letzter Parameter gibt die Aufruftiefe an. Er wäre eigentlich entbehrlich, aber ich führe ihn der Klarheit halber trotzdem mit.
void Puzzle::solve(void)
{
Bitvector bvField, bvHole, bvNonHole;
solve1(bvField, bvHole, bvNonHole, 1);
}
Die Aufgabe von solve1() ist es nun schließlich, zu dem teilweise gelösten Puzzle ein Teil passend hinzuzulegen und sich selbst rekursiv aufzurufen, falls noch nicht alle Teile verbraucht sind. Wie oben geschildert, versucht die Funktion, das Puzzle systematisch von vorn nach hinten und von unten nach oben aufzubauen. Übersetzt in die Bitvektor-Darstellung bedeutet dies ganz einfach, dass der Bitvektor bvField beginnend mit Bit 0 aufsteigend gefüllt wird.
Zusammenpuzzeln
Bei jeder möglichen Lage eines bisher ungenutzten Teils gilt es vier Bedingungen zu überprüfen:
- es belegt das nächstbeste freie Bit,
- seine Lage kollidiert mit keinem der bisher gelegten Teile,
- es hat keine Nicht-Löcher in einer Achse, in der bereits ein Teil mit Loch liegt und
- es hat keine Löcher in einer Achse, in der bereits ein Teil ohne Loch liegt.
Wenn das der Fall ist, lege ich es hin und habe dadurch entweder die Lösung gefunden oder muss solve1() rekursiv aufrufen:
void Puzzle::solve1(Bitvector bvField, Bitvector bvHole,
Bitvector bvNonHole,int level)
{
int next_bit;
for (next_bit = 0; bvField.test(next_bit); ++next_bit)
; // suche das erstbeste noch nicht gesetzte Bit
for (int part=0; part<nparts; ++part)
if (!part_used[part])
for (int pos=0; pos<parts[part].nbv; ++pos)
if (parts[part].bvPos[pos].test(next_bit) &&
!bvField.test(parts[part].bvPos[pos]) &&
!bvHole.test(parts[part].bvNonHole[pos]) &&
!bvNonHole.test(parts[part].bvHole[pos]))
{
part_used[part] = true;
part_pos[part] = pos;
Bitvector bvNewField = bvField;
bvNewField.set(parts[part].bvPos[pos]);
Bitvector bvNewHole = bvHole;
bvNewHole.set(parts[part].bvHole[pos]);
Bitvector bvNewNonHole = bvNonHole;
bvNewNonHole.set(parts[part].bvNonHole[pos]);
if (level == nparts)
found_solution(bvNewHole);
else
solve1( bvNewField, bvNewHole,
bvNewNonHole, level+1);
part_used[part] = false;
}
}
Um eine gefundene Lösung auszugeben, muss die Funktion found_solution() aus den zusammengeschobenen Bitmustern wieder etwas menschenlesbares zurückgewinnen. Statt einer aufwendigen grafischen Oberfläche habe ich nur eine ‘3D-Darstellung’ mit ASCII-Zeichen programmiert. Die Funktion selbst ist unspektakulär; ihre Ausgabe sieht so aus:
877
437
433
855
816
411
225
026
006
. o .
. o o
o . .
.
o .
. o o . . .
o . o . .
. . . o
Mit etwas Fantasie erkennt man in den oberen drei Ziffernblöcken die drei Schichten des Würfels; die Ziffern geben die Lage der Teile an. Teil Nummer 0 liegt beispielsweise flach in der linken unteren Ecke, Teil 6 steht hochkant unten in der rechten Seitenfläche. Der untere Teil der Ausgabe soll eine Ansicht der oberen, linken und vorderen Seitenfläche darstellen, wobei ein o ein Loch symbolisiert.
In seiner jetzigen Form liefert das Programm insgesamt 96 Lösungen. Unter diesen sind aber nur vier wirklich verschieden, denn zu jeder Lösung findet das Programm natürlich auch die 23 Varianten, die durch Drehung des gesamten Würfels aus dieser hervorgehen. Um diese Symmetrien zu eliminieren, bediene ich mich eines einfachen ‘Hacks’: In den Konstruktor von Puzzle füge ich am Ende einfach die Zeile
Puzzle::parts[0].nbv = 12;
ein. Dadurch benutzt das Programm von den 288 möglichen Lagen, die Teil Nummer 0 im Puzzle einnehmen kann, nur die ersten zwölf. Das sind genau die, die nur durch Verschieben dieses Teils im Raum entstehen; Teil 0 wird also anders als die anderen nicht in alle möglichen Orientierungen im Raum gedreht.
Am Ziel
Das fertige Programm benötigt auf einem Athlon-1400 jetzt nur noch etwa zwei Sekunden, um alle vier Lösungen auszugeben. Hätte ich geahnt, dass es so schnell wird, hätte ich mir vielleicht die Optimierung mit den Bitvektoren gespart und das Puzzle lieber anschaulicher mit Arrays dargestellt.
Kollege Stiller hat übrigens unabhängig von mir ein Delphi-Programm geschrieben, das das Puzzle löst. Es arbeitet mit Arrays statt Bitvektoren und geht ein bisschen anders vor. Zunächst ermittelt es alle Möglichkeiten, winkelförmige Teile ohne Berücksichtigung der Löcher zu einem Würfel zusammenzusetzen. Aus den 5328 gefundenen Lösungen eliminiert es als Nächstes die Symmetrien und behält so 222 echt verschiedene übrig. Erst dann versucht es, die Teile mit Löchern in dieses Raster hineinzulegen und findet am Ende ebenfalls vier Lösungen - in gar nicht mal so viel schlechteren fünf Sekunden auf demselben PC.
Der Lochwürfel ist also zu einfach, als dass sich das Optimieren wirklich gelohnt hätte. Anders sieht es da schon mit dem abgebildeten c't-Puzzle aus. Es besteht aus zwölf Teilen zu je fünf Einheitswürfeln - mit Ausnahme des t-Teils, das sechs Würfel umfasst, und zum Ausgleich einem Vierer. Die Teile des c't-Puzzles lassen sich auf vielfältige Arten zusammensetzen (Beispiele auf www.ctpuzzle.de). Seinem Namen macht das Puzzle aber nur Ehre, wenn man daraus einen 3x4x5-Quader mit c't-Logo auf der Oberseite baut. Damit das nicht zu einfach ist, sind drei Teile mit einem Apostroph bedruckt. Die beiden ‘Ablenk-Apostrophe’ verschwinden bei der korrekten Lösung im Inneren des Quaders.
Programmierwettbewerb
Das c't-Puzzle hat nur eine Lösung mit korrekt platziertem Logo, aber es gibt hunderttausende von Möglichkeiten, die Teile ohne Berücksichtigung des Aufdrucks zu einem 3x4x5-Quader zusammenzusetzen, und trotz Bitvektor-Optimierung kommen auch auf schnellen Prozessoren leicht Laufzeiten im mehrstündigen Bereich zusammen, will man sie alle ausrechnen.
Genau das sollen Sie nun versuchen: Schreiben Sie ein Programm, das das c't-Puzzle löst. Werfen Sie Ihren Lieblings-Compiler oder -Assembler an und lassen Sie sich etwas einfallen. Nutzen Sie die Programmiersprache Ihrer Wahl, verwenden Sie nach Herzenslust MMX, SSE, HyperThreading oder was auch immer. Denkansätze liefert dieser Artikel, aber vielleicht fällt Ihnen ja auch etwas viel Besseres ein.
Für praktische Zwecke wäre es natürlich schön, wenn Ihr Programm die Lösung mit korrektem c't-Logo liefern könnte. Für den Wettbewerb lautet die Aufgabenstellung aber, alle Möglichkeiten zu finden, ohne Berücksichtigung des Aufdrucks aus den Teilen des c't-Puzzles einen 3x4x5-Quader zu bauen. Als Ausgabe erwarte ich lediglich die Anzahl gefundener Lösungen, Symmetrien nicht mitgerechnet.
Ihr Programm sollte ohne Installation lauffähig sein und keine besonderen Bibliotheken erfordern. Schicken Sie eine ausführbare Version inklusive Quelltext bis zum 30. April per E-Mail an (bo). Ich werde alle Einsendungen auf einem aktuellen Pentium-4-System mit 512 MByte Speicher und aktiviertem HyperThreading unter Windows XP testen, alternativ unter einem aktuellen Red-Hat-Linux. Ein printf mit der richtigen Zahl genügt übrigens nicht; anhand des Quelltextes werde ich mich vergewissern, dass das Programm auch tatsächlich das Puzzle löst.
Als Lohn für die schnellste Implementierung des c't-Puzzles gibt es die langsamste: die abgebildeten Holzteile. Außer Konkurrenz dürfen Sie sich auch an einer grafischen Oberfläche versuchen. Hier gibt es natürlich keine objektiven Kriterien - die nach Meinung einer Jury aus c't-Redakteuren schönste wird ebenfalls mit einem c't-Puzzle belohnt. Der Rechtsweg ist ausgeschlossen. (bo)
