ctpz -- contribution to c't journal's 2003/3/24 puzzle
german language version of this page /
deutschsprachige Version dieser Seite
Author: Eric Laroche, firstname.lastname@example.org, 2003
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.
screenshot of the problem's input VRML
representation (produced by '
ctpz -displayinput -vrml')
[a photo could be found
Similar packing/tiling problems are known with the
two-dimensional polynominoes (pieces
consisting of interconnected squares, probably best known are the size 5
two screenshots of the first solution's VRML
1a.2b.3c.4p.7g.11a.12j.5v.8k.6b.9j.10k, one of the files produced
some advertising ;->
- 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
- 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
- virtual reality (VRML) representations
- VRML has been chosen as the format for the solution
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.250.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 and i386-win32 platform executable, as submitted 2003/4/30:
Patch that implements position specific search lists:
See the disclaimer printed in the sources' header.
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
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 @...
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 '
-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
The fastest counts are obtained by '
ctpz' on a
single-CPU system, and '
number-of-cpus' on a multiprocessor machine.
Thu May 1 2003
Sun May 11 2003