aps - Assembly Puzzle Solver
aps is a software package and results for an assembly puzzle
solver. The software is object-oriented C++ source code and
executable programs for Linux and Windows. The results are the
solutions to a variety of puzzles, their assembled parts and shape
positions, with trivial reflections and rotations excluded.
puzzles are mechanical puzzles in which a set of parts needs
to be assembled to form a given shape. Most of these puzzles are
three-dimensional cubes composed of sub-cubes. Perhaps the most
famous is the Soma
cube. But the category broadly includes tangram, "Drive Ya
Nuts" and Sudoku
The following are executable programs, a batch script called
"doboxer" and input files for boxer. The Linux programs were
compiled for a Red Hat x86 system. The Windows programs were
compiled on a late model Microsoft compiler.
The executable programs are invoked from a console window and print
solution(s) to standard output. The following are the included
- sudoko - solves Sudoku puzzles. Takes one command line
argument, the name of an input file; with no argument it reads
standard input. Input consists of nine lines, each of nine
characters, where filled positions are represented by digits 1
to 9 and unfilled positions are represented by any other
- queen - solves the queens on a chessboard problem for a n
× n board. Takes one argument, n; with
no arguments the default is 8.
- nuts - solves the "Drive Ya Nuts" puzzle
- tangram - solves the tangram square puzzle
- pent - solves the pentominos puzzle for 3 × 20, 4
× 15, 5 × 12 and 6 × 10 rectangles given
one command line argument 3, 4, 5 or 6. With no argument, the
default is 6. Prints assembled parts and shape positions.
- y25 - solves 5 × 5 × 5 cube puzzle consisting of
25 "Y" pentomino parts. Prints assembled parts and shape
- bedlam - solves the 4 × 4 × 4 Bedlam cube puzzle.
Prints assembled parts and shape positions.
- boxer - solves hyperrectangular puzzles. Prints assembled
parts and shape positions. Takes one command line argument, the
name of an input file; with no argument it reads standard input.
The input describes the puzzle.
Boxer Input File Format
The boxer program input describes the puzzle in a series of integers
and strings separated by whitespace: The number of dimensions
followed by the length in each dimension. Then the number of
excluded positions and for each excluded position, for each
dimension, the offset of that excluded position in that dimension.
Then a string with one character for each shape. Then for each
shape, a string with one character for each part with that shape
followed by the number of positions in that shape, followed by, for
each position, for each dimension, the offset of that position of
that shape in that dimension.
The doboxer and doboxer.bat
scripts runs the boxer program for a series of puzzles named on the
command line. For puzzle given on the command line as name,
the script reads an puzzle input file name.in.txt and writes
a solution output file name.out.txt.
One input file, sudoku.in.txt, is a
sample input to the sudoku program. Other input files are puzzle
descriptions for the boxer program:
Most, if not all, of these puzzles have been solved before.
Results running these programs follow. For the pentomino and
three-dimensional puzzles, results include the unique assemblies
of the parts and, for each part, their unique positions used
within the assemblies. Unique positions exclude rotations of the
whole. Unique assemblies exclude rotations and reflections.
- Sudoku - sudoku.out.txt gives one example
solution from running the sudoku program. Dots represent the
unfilled positions in the given puzzle, which are filled in the
on a Chessboard - queen.out.txt
gives the 12 solutions for an 8×8 board using the queen
program. Circles represent queens; dots represent unoccupied
Ya Nuts - nuts.out.txt gives
the single assembly of the original puzzle using the nuts
program. Asterisks indicate the centers of nuts; numbers are
located at the middle of flat edges of nut(s).
- Tangram - tangram.out.txt gives the single
assembly of the pieces into a square using the tangram program.
Letters indicate the locations of pieces.
- pent.3.out.txt gives the two
assemblies that form a 3 × 20 rectangle; pent.4.out.txt gives the 368
assemblies that form a 4 × 15 rectangle; pent.5.out.txt gives the 1010
assemblies that form a 5 × 12 rectangle; and pent.6.out.txt gives the 2339
assemblies that form a 6 × 10 rectangle, using the pent
- Y25 Cube - y25.out.txt
gives the 1264 assemblies that form a 5 × 5 × 5 cube
using the y25 program.
- Bedlam Cube
- bedlam.out.txt gives the 19186
assemblies that form a 4 × 4 × 4 cube using the
- Results from the boxer program
All the software hereabouts was written by Lawrence Leinweber,
Cleveland, Ohio, USA, and is copyrighted.
I wrote a Soma solver in high school, my first such program. It ran
on a Basic interpreter on a PDP-11 and printed results on a
teletype. The Y25 solver was my second, which ran on Apple II. It
swapped out the operating system and ran on the Z-page of the 6502
processor. I got the Google cube last year but my solvers could not
handle multiple parts with the same shape. This aps package handles
all that and more. It is a brute-force
solver, but smart enough not to insert parts that do not fit.
The aps package has five layers, print (lowest), aps, search,
puzzle, box (highest), as well as the puzzle application. A site is
a search cell. A location is puzzle cell. A position is a set of
sites or locations. A part has a position within a solution. Parts
with the same shape are interchangeable. A map transforms locations.
The space occupied by parts is represented as a series of bits so
bit-mapped operations can be used. There is a template for fixed
length spaces and ordinary code for variable length, when the size
of the puzzle space is not fixed at compile-time. During a search,
as the space is filled with parts, two things happen: the parts for
some shapes are used up and the number of unoccupied sites
diminishes. Rather than waste time searching through lots of
unusable parts and occupied sites, used-up shapes are taken off the
availability list and unoccupied sites are visited in order. Then
only the remained shapes are tried only in positions whose first
site is the next unoccupied site. Redundant solutions are
avoided through copious use of id numbers. Locations have id
numbers. A group of locations is part position. Part positions have
id numbers. A group of part positions is a solution. Solutions have
id numbers. The search and puzzle algorithms are abstracted
out as servers. Applications are clients. Puzzles and boxes have an
overall position occupied by parts, especially so that the number of
search cells can be small and the number of puzzle cells,
conveniently large. Other shapes composed of hypercubes can be
defined by an overall position within a box. But that position must
be symmetric within the box in order for symmetric redundancies to
be recognized and discarded.
The following describes the source code files. C++ file types are
(1) *.h - header, (2) *.hpp - template code, and (3) *.cpp -
- makefile.linux, makefile.win - Linux and Windows
makefiles; the build command for Linux is "make -B -f
makefile.linux"; the build command for Windows is "nmake /A /f
- print.h, print.hpp
- print layer. Lowest-level provides printing diagnostics on top
of standard template library.
- aps.h, aps.hpp, aps.cpp - utility layer. Lower-level
provides management and transforms for puzzles and solutions.
- search.h, search.hpp,
search.cpp - search layer. mid-level
- puzzle.h, puzzle.cpp
- solution management layer. higher-level used to avoid
- box.h, box.cpp -
box layer. high-level abstractions for hyperrectangular puzzles.
- sudoku.cpp - only uses the print, aps
and search layers. To represent a Sudoku puzzle as an assembly
puzzle, define 243 sites to be filled by 81 parts. Each part
represents a Sudoku grid location. Each part can occupy nine
positions, for each of the nine possible digits, or one
position, if the digit is given in the particular puzzle. A site
represents a row for a digit, a column for a digit, or a square
for a digit. Each part fills three sites. So a part position
represents a digit filled in the Sudoku grid and when all 81
parts are positioned, the puzzle is solved.
- queen.cpp - uses layers up to the
puzzle layer. To represent the position of a queen on an n ×
n chess board, define sites for each of n rows, n
columns and 4n-2 diagonals. Each queen occupies
one row, one column and two diagonals. All queens are
interchangeable, so there are n parts, but one shape.
Not all sites will be occupied but all parts will be used when a
solution is found.
- nuts.cpp - uses layers up to the puzzle
layer. The edge between two nuts is represented by four sites.
The number printed on the edge of nut is represented by a 2 of 4
code. The six directions around a nut are also numbered so that
each even numbered edge of a nut is adjacent to the odd numbered
edge of another nut. Even and odd numbered edges use
complementary codes in the 2 of 4 code. Thus the number printed
on the edge of a nut can only pair with the same number on the
edge of an adjacent nut. There are 12 such adjacent edges with
four sites each. The center nut has 6 such edges; the other six
- tangram.cpp - uses layers up to the
puzzle layer. The tangram square can be divided into a 4 ×
4 grid and then into the 64 right, isosceles triangles. Parts
are combinations of these triangles.
- pent.cpp - two-dimensional box puzzle.
The number of sites is fixed at 60 but the length and width of
the rectange is variable.
- y25.cpp - three-dimensional box puzzle.
Optimized for speed with fixed 125 search cells
- bedlam.cpp - three-dimension box
puzzle. Optimized for speed with fixed 64 search cells
- boxer.cpp - general hyperrectangular
puzzle with puzzle defined by input file
- doboxer, doboxer.bat
- as above, Linux and Windows scripts to run boxer program
- sudoku.in.txt, sg.in.txt, soma.in.txt,
conway.in.txt, diabolical.in.txt - as above,
input files for sudoku and doboxer
Return to Larry's Cerebral Snack Bar