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.

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.

Programs

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.

Executable Programs

The executable programs are invoked from a console window and print solution(s) to standard output. The following are the included programs:

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.

Batch Scripts

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.

Input Files

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

Puzzle Results

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.

Source Code

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

Larry Leinweber, Proprietor

Return to Larry's Cerebral Snack Bar