ctpz -- Beitrag zum Puzzle aus dem c't Magazin 2003/3/24

[ englischsprachige Version dieser Seite / english language version of this page ]

Autor: Eric Laroche, laroche@lrdev.com, 2003

das Puzzle

Das Puzzle von Harald Bögeholz und des c't Magazins (magazin für computer technik) wurde 2003/3/24 publiziert. Die Problemstellung war, schnelle Ansätze zur Berechnung von dreidimensionalen Packungen von 12 Puzzleteilen in ein Quader passender Größe zu finden. Die Puzzleteile bestehen aus vier bis sechs an den Seiten verbundenen Würfeln gleicher Größe. [Links: 1, 2, 3]

[die 12 Puzzleteile]
Screenshot der VRML Repräsentation des Problem-Inputs (generiert durch 'ctpz -displayinput -vrml') [ein Photo konnte hier gefunden werden]

Ähnliche Packungs/Kachelungs-Probleme (packing/tiling problems) sind bekannt für die zweidimensionalen Polynominos (Teile bestehend aus verbundenen Quadraten; am besten bekannt sind wohl die Pentominos der Größe 5).

Lösungen

[Puzzlelösung #1, aus anderer Perspektive]

Screenshots der VRML Repräsentation der ersten Lösung (Packung 1a.2b.3c.4p.7g.11a.12j.5v.8k.6b.9j.10k, eine der durch '

ctpz
-vrml

' generierten Dateien)

Implementierung

ein wenig Werbung ;->

C++: C++ Implementierungen sind schnell und erlauben strikte Kontrolle (wie eben benötigt für dieses Optimierungsproblem; wie es C auch unterstützt). Zusätzlich werden eine bessere Kapselung ermöglicht und die Kodierung erleichtert (z.B. mittels C++ Referenztypen). Bemerkung: Polymorphismus ('virtual' Attribut) wurde nicht verwendet, ebenso nicht Exceptions (beide werden für dieses spezifische Problem nicht benötigt).
Multithreading: Multithreading wird (optional) benutzt, um bis zu 12 Threads parallel nach Lösungen suchen zu lassen. Diese 12 Threads werden initial gestartet, während die Benutzer die Anzahl gleichzeitig laufender Threads spezifizieren können (üblicherweise entsprechend der Anzahl CPUs; gesteuert durch eine Semaphore). Bemerkung: Multithreading ist nur für das win32 API implementiert, die wenigen Calls (Threadgenerierung, Locking und Semaphoren) können aber einfach portiert werden.
Virtual Reality (VRML) Darstellungen: Als Format zur Lösungsdarstellung wurde VRML ausgewählt. Es erlaubt die Navigation durch die Packungen, um vielleicht ein besseres Bild deren Strukturen zu erhalten. VRML-Output-Generierung entkoppelt auch vom aufwendigen Task des Bilder-Renderings.
Tunnels in VRML Darstellungen: Tunnels erlauben es, durch Packungen zu 'walken' (VRML Terminologie), ohne durch Wände gehen zu müssen, und erlauben es, die Sequenz der Puzzleteile in alle Dimensionen zu betrachten.
Tunnels im Goldenen Schnitt: Der Goldene Schnitt (1.25^0.5+0.5) mag den VRML Darstellungen ein besseres Aussehen verleihen.
Ad-hoc Rotationen: Der Puzzle-Input muß weder die rotationalen Varianten (Rotamere) der Teile noch Symmetrie-Eigenschaften spezifizieren. Das Programm berechnet die maximal 24 Rotamere pro Teil on-the-fly und beschränkt jene eines speziellen Teils auf 6, um die Berechnung symmetrischer Packungs-Lösungen zu verhindern.
minimale Abhängigkeiten: Die Intermodul-Abhängigkeiten sind (wie immer) minimiert.
minimaler main Programm-Code: Da meiste ist in einem Klassen-Framework implementiert. Dies wird als klarerer Objekt-orientierter Design-Ansatz angesehen.
Inline Datenzugriff: Die grundlegenden Datenstrukturen (Würfel, Figur, etc) sind direkt zugreifbar in dieser speziellen Problemdomäne, um schnellste Implementierung der inneren Backtracking Loops zu erlauben. Der CPU Register Datentyp (int) wird benutzt für die Koordinaten und Indizes; es wird angenommen, daß diese am schnellsten verarbeitet werden (passendes Alignment, keine Umwandlungsschritte vor und nach den Operationsschritten, etc).
generalisierter Input Parser: Das Inputparsing ist in einer allgemeinen Art implementiert, was Code-Redundanzen vermindert, etc.

Sourcen

Sourcen und i386-win32 Plattform Executable, eingesandt 2003/4/30: lrctpz-20030430.zip

Patch, der positions-spezifische Suchlisten implementiert: lrctpz-20030510a-patch.zip

Siehe auch Disclaimer in den Source Headern.

Benutzung

ctpz -? : Benutzung, Hilfe.




usage: ctpz [-count] [-displayinput] [-threads #] [-verbose] [-vrml]


e.g. 'ctpz' (or 'ctpz -count') for solution count


e.g. 'ctpz -threads 4' for solution count on a 4 CPU machine


e.g. 'ctpz -vrml' for VRML representations


e.g. 'ctpz -displayinput -vrml' for VRML representation of input

ctpz oder ctpz -count : Berechne die Anzahl Lösungen. Dies ist die Kernfunktionalität des Programms.

ctpz -count -threads 4 : Berechne die Anzahl Lösungen auf einer Maschine mit 4 verfügbaren CPUs. Dies ist erwartungsgemäß etwa 4 mal schneller (der inter-thread Synchronisation Overhead ist in diesem Fall klein). Bis zu 12 Threads / CPUs werden unterstützt.

ctpz -count -verbose : Berechne die Anzahl Lösungen, während der Progreß angezeigt wird. Dies ist einigermaßen langsamer, da Output teuer ist und der Output Synchronisations Overhead das ganze weiter verlangsamt. #1 1a.2b.3c.4p.7g.11a.12j.5v.8k.6b.9j.10k @... #2 1a.2b.3c.6g.10j.8k.12d.4g.7p.9d.5j.11a @... ... #409962 12x.10w.8k.7h.9d.2k.3c.6l.11b.1d.4s.5p @... #409963 12x.10w.8k.7i.1j.11c.3d.4p.9i.5f.6b.2b @... 409963

ctpz -vrml : Generiere VRML Repräsentationen der Lösungen. Dateien ctpz.1.wrl, ctpz.2.wrl, etc werden generiert. [Dies tendiert dazu, Speichermedien zu füllen.] [Der VRML Output kann allerdings komprimiert werden (mittels 'gzip -9'), was die Dateigröße um etwa Faktor 13 reduziert (wegen den sich exakt wiederholenden 'IndexedFaceSet' Werten, und anderen Ähnlichkeiten); das gzip Format wird von den VRML Browsern typischerweise gut erkannt.]

ctpz -displayinput -vrml : Generiere eine VRML Repräsentation des Puzzle-Inputs (die isolierten Teile).

Die schnellsten Zählungen werden durch 'ctpz' auf einzel-CPU Systemen, und 'ctpz -threads anzahl-cpus' auf Multiprozessor-Maschinen erreicht.

http://www.lrdev.com/lr/c/ctpz.de.html
Eric Laroche, laroche@lrdev.com / Don 1. Mai 2003 / letzte Änderung: Son 11. Mai 2003