The GENDA Program
The analysis presented in this booklet would not have been
possible without the development of a computer program to analyze the
disassembly of puzzles made of pieces "built-up" from cubes. Pieces
in the puzzle are allowed to move only in one of the three orthogonal
directions, and the distances they move must be a multiple of the cube
width. They may not be twisted or moved a fraction of a cube width.
Pieces may either move individually or in groups. The first such
program to be written is called GENDA (GENeral DisAssembly); it was
written in FORTRAN and has the most sophisticated logic of any of the
programs used in the 6-piece burr analysis.
The following is an outline of the procedure used by the program
for doing disassembly analysis:
- The program starts with the assembled puzzle. If the program
is successful in completely disassembling the puzzle, then the results
can be used 'backwards' to assemble the puzzle from its separate
pieces. An assembled puzzle is a 3-dimensional grid of cubes in which
each cube is part of a particular piece or is empty space. If there
are N pieces in the puzzle, this is represented in the computer by a
3-dimensional array containing integers from 0 to N. The value of a
particular array element indicates the piece number that occupies the
corresponding cube, or 0 if the cube is empty.
- The allowable movements in the physical puzzle correspond to
simple changes in the values of the array.
- During movement prior to disassembly, the puzzle will pass
through different 'states'. Each state is a different arrangement of
the pieces in the same grid of cubes. Within the computer program, a
state is represented by the amounts that each of the pieces have been
moved in each of the three directions from their starting position.
If one fixes piece #1 in its initial location, then each state is
uniquely represented by the offsets of the other N-1 pieces, or 3 x
(N-1) integers.
- The problem can thus be reduced to analyzing movement in a
single direction and determining which states can be reached from
another state by movement in this direction. The program must be able
to identify when one or more pieces may be separated from the rest of
the pieces by movement in a single direction. This is called a
partial solution, as the remaining groups of pieces may still not come
completely apart. Movement in a single direction will be described in
more depth in the next section.
- The logic for completely disassembling a puzzle is just
repeated applications of the same logic for disassembling the whole
puzzle. Each time a group of pieces is disassembled, the resulting
sets of pieces are cataloged as sub-assemblies. Any sub-assembly with
more than one piece is saved for later analysis.
The key to the analysis is keeping track of the states:
- At the beginning of the analysis, the list contains only one
state: the starting position, in which the offsets of all the pieces
are 0.
- Pick the next unanalyzed state in the list, and choose one of
the orthogonal directions. Determine how much movement of the pieces
relative to each other in this direction is possible. Use this
information to construct all states which can be reached from the
original state with one move. If the movement allows for complete
separation of two or more sets of pieces, then we have found a partial
solution and can stop.
- For each of these new states, determine if it has already been
recorded in the list of states. This is easily done by comparing the
offsets of the pieces of the new state with the offsets of the pieces
in each state in the list. (Recall that Piece #1 is not allowed to
move - its displacements are always 0). If it has not previously been
recorded, add it to the list; otherwise, discard it.
- Continue with the analysis until either:
- Some state leads to disassembly in one move or
- The state list has been completely analyzed; no new
other states can be reached from any of the states in the
list.
- Since there are only a finite number of states in which all
the pieces are still interlocked, the process must end at some time.
For some burrs with many pieces and independent movement of parallel
pieces (ex. Van der Poel's 18-piece burr), this may involve hundreds
of states and may take a significant amount of computer time; but the
process is still finite.
Analyzing Movement in One Direction
This section is more technical than the rest of the booklet. It
is included because it contains the single most interesting piece of
logic or mathematics used by the programs.
How is movement in one direction analyzed?
Let N be the number of pieces in the puzzle.
Let GRID(x,y,z) be the array containing the piece numbers which
occupy each cube, and assume that the dimensions of GRID are less than
100 in each direction. We will analyze movement in the first
orthogonal direction, that is the first supscript (x) of GRID.
We will construct an N by N matrix, MOVE(i,j), which will show
how each pair of pieces may move in relation to each other in the
fixed direction. MOVE(i,j) is a non-negative integer which is the
number of cubic widths piece # i can be moved in the positive
direction while keeping piece # j fixed. If there is no limit to how
far piece # i can be moved in this direction without moving piece # j,
then this value is set to 100.
The following steps are used to construct the matrix MOVE:
- Initialize the main diagonal of MOVE to 0 and all other entries to 100.
- Determine simple piece interactions (compute values for
MOVE(i,j) by ignoring pieces except for i and j) as follows:
For each i from 1 to N;
For each j from 1 to N except j=i;
For each (x1,y1,z1) for which GRID(x1,y1,z1)=i;
For each (x2,y2,z2) for which GRID(x2,y2,z2)=j;
If y2=y1 and z2=z1 and x2>x1, then
let k=x2-x1-1; if MOVE(i,j) > k, then MOVE(i,j)=k.
(The actually programming of the above step can be done
more efficiently, but it is easier to explain this way).
- Introduce interactions of other pieces. It is geometrically
evident that the final MOVE matrix must satisfy the following
transitive relationship:
For all pieces i,j,k,
MOVE(i,j) <= MOVE(i,k)+MOVE(k,j)
What is not so immediately apparent is that this is the only
additional change that must be made to get the desired result.
Loop through all values of i,j,k and compare
MOVE(i,j) with MOVE(i,j)+MOVE(j,k)
If MOVE(i,j) is larger, replace it with the value on the
right.
Continue doing this over and over until no further changes are
required for any values of i,j,k.
If any MOVE(i,j)=100, a partial solution has been found.
If all values of MOVE are 0, then there is no movement.
Otherwise, there is some movement in the chosen direction.
The FDA Program
When the project to analyze all 6-piece burr assemblies was
started, it was clear that a faster, more efficient program would be
needed in order to have any hope of completing the project in a
reasonable time. To this end, the following modifications were made
to the GENDA program:
- Only do partial disassembly analysis. In other words, only
determine the first separation of the pieces and how many moves it
took to achieve this. Assemblies which took a lot of moves for the
first disassembly would be saved for a later, more thorough, analysis.
Since the goal of the program was to find 6-piece burrs which took as
many moves as possible to remove the first piece, all candidates for
this honor would be identified.
- Rewrite all routines with a fixed number of 6 pieces, and take
advantage of this where possible to make the code more efficient.
- Rewrite the most time-consuming routines in 8086 Assembler (PC
machine language) to get the most speed possible.
An additional complication was also added to the routines -
varying piece lengths. Early on, it was realized that a thorough
investigation of 6-piece burr assemblies must be sensitive to the
lengths of the pieces. Lengths of 6, 8, 10 and 12 may produce
different results, although it is rare for there to be a difference
between lengths 10 and 12. Even though the original intention of the
analysis was only to identify high-level solutions, no short cuts on
piece length are possible - an assembly which is level-8 with length
10 pieces may be only level-3 with length 6 pieces; and, conversely,
an assembly which is level-8 with length 6 pieces may have no solution
with length 8 pieces.
The result was a new program for 6-piece burr analysis called FDA
(Fast Disassembly Analysis). For each assembly analyzed, the
resulting output is a group of 4 numbers called the 'level-type'.
These are the number of moves required for the first disassembly with
length 6, 8, 10 and 12 pieces.
The FDA routines handle the multiple length analysis as follows:
- Movement of the initial position is analyzed - this movement
is independent of piece length. If no movement is found, then the
level type is 0-0-0-0. If a level-1 solution is found, then the
level-type is 1-1-1-1.
- If there is movement, but no level-1 solution, save all states
created.
- Continue the analysis with length 6 pieces. During the
analysis, each movement and resulting state is analyzed as to whether
it can be "generalized" using unlimited length pieces. If a solution
is found, and all movements leading to the solution can generalize,
then the assembly has the same level solution for all longer pieces
also. If no solution is found, then there is no solution with longer
pieces either.
- If a length-6 solution is found which does not generalize,
then redo the analysis with length 8 pieces, again checking for
generalization possibilities.
- Repeat with length 10 and 12 pieces if necessary.
- Save the solution level found at each length.
Note: Level-type 0-0-0-1 is used to indicate that there is movement in
the assembly, but no solution at any length.
After the FDA analysis for an assembly is completed, the program
does the following:
- Record the results by level-type, number of holes, whether
notchable or general, and any symmetry of the assembly.
- If the assembly is deemed to be 'special', write out the
assembly to a separate file so that it can be analyzed in more detail
later. An assembly was deemed to be 'special' if either:
- The level of solution with some length of pieces was 8 or more
- The level-type was a new combination not seen before.
The format used to print out 'special' assemblies is called the "LL
Format".
D. The LL Format
The following are LL listings for 3 assemblies:
LL-Format E H S 6 8 A C Name
-------------------------------- - - - - - - - ---------------
35350030443000251130143320220666 0 9 012 0 0 0 Love's Dozen
55555530043022551131642000220636 0 7 0 5 0 0 0 Bill's Baffling Burr
05550110503004001116603664226666 0 9 0 4 61010 L46AA Notchable
The most important information is the first 32 numbers under the
heading "LL-Format". These represent the internal cube arrangements
of the assembly. Compare these numbers with Figure 2 (below).
Each of the 32 numbers represents the allocation of one of the unassigned cubes in
Figure 2. A '0' in the listing indicates
that the cube is empty. A number from 1-6 indicates the number of the
piece to which the cube belongs.
The additional entries in the LL listing are less important, and
can be recomputed if necessary:
- The 'E' column is an error return which was used during the
program run to indicate non-critical problems which occurred
when that assembly was run, such as too much movement within
the assembly or a new level-type.
- The 'H' column is the number of holes in the assembly (same as
the number of 0's in the LL-format).
- The 'S' column was used for an analysis variable which will not
be discussed here.
- The '6', '8', 'A' and 'C' columns give the levels at lengths 6,
8, 10 and 12, respectively. Together, these 4 numbers are
the level-type.
See Love's Dozen or Computer's Choice Unique-10 in the examples
for demonstrations of the use of the LL-Format.
Love's Dozen LL Format to Assembly
Computer's Choice Unique 10 LL Format to Assembly
Copyright 2000-2016 Bill Cutler Puzzles, Inc.
