Beschreibung des Algorithmus zur Lösung des c't-Puzzles
Autor: Tobias Glasmachers, Tobias.Glasmachers@rub.de

So, dies ist also mein Beitrag zum Wettbewerb. Ich möchte im Folgenden kurz meine Vorgehensweise erleutern:

Der X-Trick

Es ist sehr auffällig, dass der X-förmige Bauklotz eine Sonderrolle spielen kann, weil er im Vergleich zu den anderen Bauklötzen extrem symmetrisch ist. Betrachtet man seine Positionen im Quader, die nicht durch Drehungen des Quaders ineinander überführbar sind, so kommt man mit 12 Positionierungen aus. Dabei wird in 4 Fällen der Bauklotz bei einer Drehung des Quaders in sich selbst abgebildet, d.h. eine Symmetrie bleibt bestehen. Es ist klar, dass dieser Bauklotz zuerst platziert werden sollte.

Die Rekursion

Ist der X-förmige Klotz platziert, so werden rekursiv die fünf 3x4-Ebenen des Quaders gefüllt. Es gibt 5 rekursive Routinen, jede ist mit dem Füllen einer Ebene betraut. Ist diese voll, so wird die Routine für die nächste Ebene aufgerufen. Ist die 5. Ebene voll, so wird eine Lösung vermerkt.

Während ihres Ablaufs setzt eine solche Routine einen Bauklotz ein. Immer wenn eine Routine aufgerufen wird, entscheidet der Algorithmus, welches der maximal 12 noch freien Felder als nächstes zu besetzen ist, und dazu werden Hashtabellen benutzt. Der ursprüngliche Algorithmus verwendete einen 24bit-Index, also 2 volle Ebenen. Da es sich als sehr ungünstig erweist, Tabellen zu benutzen, die deutlich größer als der Prozessorcache sind, werden eine 12-Bit-Tabelle und eine 17-Bit-Tabelle verwendet.

Die 17-Bit-Tabelle liefert einen Wert zwischen 0 und 191. Darin sind alle Möglichkeiten kodiert, auf die ein Feld belegte oder freie Nachbarn haben kann. Beispiel: Das Feld links oben in der 3x4-Ebene braucht 3 Bit zur Beschreibung seiner Nachbarn, denn 2 Ränder sind immer da und die dahinterliegende Ebene ist ebenfalls garantiert voll besetzt. Es bleiben die beiden Richtungen innerhalb der Ebene sowie die Ebene davor. Betrachtet man so alle 12 Felder, so ergeben sich 192 Möglichkeiten.

Jetzt gibt es für jede 3x4-Ebene (außer der zweiten) 192 Zeiger in eine Tabelle, in der die Bauklötze verzeichnet sind, die bei gegebenem Feld und gegebenen Nachbarn eingesetzt werden können. Diese werden von der Rekursionsroutine durchprobiert.

Die verwendeten Tricks

Hier eine Auflistung der Tricks, die den Algorithmus vielleicht von Anderen unterscheiden:

• Ganz wichtig: Der X-Trick (s.o.)
• Das nächste zu besetzende Feld wird dynamisch bestimmt. Dies verkürzt den Suchbaum deutlich. Allerdings wird die Suche auf die aktuelle Ebene eingeschränkt.
• Die Bestimmung geschieht mit Hilfe von im Voraus berechneten Tabellen, was natürlich nicht immer das optimale Resultat bringt, aber deutlich schneller als die Bestimmung des wirklich besten Feldes ist.
• Die Tabellen werden auf eine solche Größe beschränkt, dass der Prozessor sie (hoffentlich) im Cache unterbringen kann (580KB). Dafür werden keine zusätzlichen Speicherzugriffe in Kauf genommen, sondern ein etwas größerer Suchbaum.
• Es gibt eine eigene Routine für jede 3x4-Ebene. Dies spart Verwaltungsaufwand und Fallunterscheidungen.
• Vor dem Sprung in die 5. Ebene wird geprüft, ob noch einer der beiden nicht in eine Ebene passenden 3D-Bauklötze abzulegen ist. Falls ja wird der Fall nicht weiter untersucht.

Statistik

Ich kenne mich leider überhaupt nicht mit aktuellen Prozessoren oder Compilern aus. Zum endgültigen Kompilieren des Programms habe ich aber in gutem Glauben den C-Compiler von Intel mit den Optionen -O3 -Qip -QaxW bzw. auf dem Pentium 4 -QxW verwendet. Die Datei TG_P4.exe läuft nur auf einem Pentium 4, die Datei TG_ALL läuft auch auf anderen Rechnern.

Ich habe das Programm auf verschiedenen Systemen getestet, hier sind die Ergebnisse:

Prozessor Zeit Athlon, 1400 MHz 2:21 Athlon XP 2000, 1666 MHz 1:59 Pentium 4, 2400 MHz 1:53

Schon erstaunlich, der Pentium 4 scheint trotz Intel-Compiler und Pentium4-Optimierung echte Probleme mit der Performance zu haben.

weitere Verwendung

Ich habe nichts dagegen, wenn der Sourcecode von Anderen weiterverwendet wird. Vielleicht kann ja irgendjemand etwas wirklich sinnvolles damit anfangen. Wenn allerdings eine veränderte Version des Codes weitergegeben wird, so verlange ich eine entsprechende Kennzeichnung.

Viel Spaß damit!