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.

Assembly
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
puzzles.

- 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 character.
- 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 positions.
- 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.

One input file, sudoku.in.txt, is a
sample input to the sudoku program. Other input files are puzzle
descriptions for the boxer program:

- sg.in.txt - the Slothouber–Graatsma puzzle
- soma.in.txt - the Soma cube
- wwall.in.txt - the W-wall Soma puzzle
- zwall.in.txt - the Z-wall Soma puzzle
- google.in.txt - a Soma-like puzzle given by Google
- conway.in.txt - the Conway puzzle
- diabolical.in.txt - the Diabolical cube

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
solution.

- Queens
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
squares.

- Drive
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.

- Pentomino - 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 program.
- 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 bedlam program.
- Results from the boxer program

- Slothouber–Graatsma
Puzzle - sg.out.txt gives the
single assembly that form a 3 × 3 × 3 cube.

- Soma Cube
- soma.out.txt gives the 240
assemblies that form a 3 × 3 × 3 cube.

- W
Wall - wwall.out.txt
gives
*no*assemblies that form the Soma parts into a W-shaped wall.

- Z
Wall - zwall.out.txt
gives 23 assemblies that form the Soma parts into a Z-shaped
wall.

- Google Cube - google.out.txt gives the 282
assemblies that form the Soma-like cube.

- Conway
Puzzle - conway.out.txt
gives the 572 assemblies that form a 5 × 5 × 5
cube.

- Diabolical
Cube - diabolical.out.txt
gives the 13 assemblies that form a 3 × 3 × 3
cube.

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 - non-template code:

- 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 makefile.win"
- 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 search algorithm.
- puzzle.h, puzzle.cpp - solution management layer. higher-level used to avoid reporting redundancies
- 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 4*n*-2*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
nuts, 3.

- 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,
wwall.in.txt,
zwall.in.txt, google.in.txt,
conway.in.txt, diabolical.in.txt - as above,
input files for sudoku and doboxer

Larry Leinweber, Proprietor