ctpz -- contribution to c't journal's 2003/3/24 puzzle

[ german language version of this page / deutschsprachige Version dieser Seite ]

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

the puzzle

The c't journal's (magazin für computer technik) puzzle by Harald Bögeholz was published 2003/3/24. The problem was to find fast ways to calculate three-dimensional packings of 12 puzzle pieces into a cuboid of appropriate size. The pieces consist of four to six cubes of the same size, interconnected at the cubes' sides. [links: 1, 2, 3]

[the 12 puzzle pieces]
screenshot of the problem's input VRML representation (produced by 'ctpz -displayinput -vrml') [a photo could be found here]

Similar packing/tiling problems are known with the two-dimensional polynominoes (pieces consisting of interconnected squares, probably best known are the size 5 pentominoes).

solutions

[puzzle solution #1, from another perspective]

two screenshots of the first solution's VRML representation (packing 1a.2b.3c.4p.7g.11a.12j.5v.8k.6b.9j.10k, one of the files produced by 'ctpz -vrml')

implementation

some advertising ;->

C++: C++ is fast and allows extreme control (as needed for this optimization problem, as C does too). Additionally it facilitates good encapsulation and eases coding (e.g. using C++ reference types as syntactic sugar). Note that polymorphism ('virtual' attribute) has not been used, neither have been exceptions (both are not needed for this specific problem).
multithreading: Multithreading is (optionally) used to allow up to 12 threads to search for solutions in parallel. These 12 threads are started initially, while users can specify how many of them should run concurrently (usually the number of CPUs; controlled by use of a semaphore). Note that multithreading is only implemented for the win32 API, however the few calls (thread creation, locking and semaphores) are easy to port.
virtual reality (VRML) representations: VRML has been chosen as the format for the solution representations. It allows navigating thru the packings, to maybe get a better idea of their structures. Generating VRML output also decouples from the extensive task of rendering the images.
tunnels in the VRML representations: Tunnels allow 'walking' (VRML term) thru packings without needing to go thru walls and allow to see the sequence of puzzle pieces in all dimensions.
tunnels in golden ratio: Golden ratio (1.25^0.5+0.5) may give the VRML representations a better look.
rotations done on the fly: The puzzle input neither is required to specify the pieces' rotational variants (rotameres) nor to specify symmetry properties. The program calculates the maximal 24 rotameres per piece on the fly and confines those of one specific piece to 6, to avoid the calculation of symmetric packing solutions.
minimized dependencies: Intermodule dependencies are (as always) minimized.
minimized main program code: Most stuff is implemented in a class framework. This is considered a cleaner object oriented design approach.
inline data access: The base data structures (cube, figure, etc) are directly accessible in this specific problem domain, to allow fastest implementation of the inner backtracking loops. Native CPU register type (int) is used for coordinates and indices, for it is assumed to be handled fastest (proper alignment, no conversion steps before and after operations needed, etc).
generalized input parser: Input parsing is implemented in a generalized manner, cutting code redundancies, etc.

sources

Sources and i386-win32 platform executable, as submitted 2003/4/30: lrctpz-20030430.zip

Patch that implements position specific search lists: lrctpz-20030510a-patch.zip

See the disclaimer printed in the sources' header.

usage

ctpz -? : Usage, help.




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 or ctpz -count : Calculate the solution count. This is the program's core functionality.

ctpz -count -threads 4 : Calculate the solution count on a machine with 4 CPUs available. This is expected to be about 4 times faster (the inter-thread synchronization overhead is small in this case). Up to 12 threads / CPUs are supported.

ctpz -count -verbose : Calculate the solution count, while displaying progress. This is much slower, since output is expensive and output synchronization overhead slows things down too. #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 : Generate VRML representations of the solutions. Files ctpz.1.wrl, ctpz.2.wrl, etc will be generated. [This tends to fill storage media.] [The VRML output could however be compressed (by 'gzip -9'), which will reduce the file size by about factor 13 (due to the exactly repeating 'IndexedFaceSet' values, and other similarities); the gzip format is typically well recognized by the VRML browsers.]

ctpz -displayinput -vrml : Generate a VRML representation of the puzzle's input (the isolated pieces).

The fastest counts are obtained by 'ctpz' on a single-CPU system, and 'ctpz -threads number-of-cpus' on a multiprocessor machine.

http://www.lrdev.com/lr/c/ctpz.html
Eric Laroche, laroche@lrdev.com / Thu May 1 2003 / last update: Sun May 11 2003