Analyzing Assemblies BCPI logo billcutlerpuzzles.com

Contents
previous: Constructing Assemblies next: Uniqueness and Disassembly

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:

  1. 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.
  2. The allowable movements in the physical puzzle correspond to simple changes in the values of the array.
  3. 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.
  4. 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.
  5. 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:

  1. 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.
  2. 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.
  3. 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.
  4. Continue with the analysis until either:
  5. 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:

  1. Initialize the main diagonal of MOVE to 0 and all other entries to 100.
  2. 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).
    
  3. 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:

  1. 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.
  2. Rewrite all routines with a fixed number of 6 pieces, and take advantage of this where possible to make the code more efficient.
  3. 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:

  1. 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.
  2. If there is movement, but no level-1 solution, save all states created.
  3. 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.
  4. If a length-6 solution is found which does not generalize, then redo the analysis with length 8 pieces, again checking for generalization possibilities.
  5. Repeat with length 10 and 12 pieces if necessary.
  6. 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:

  1. Record the results by level-type, number of holes, whether notchable or general, and any symmetry of the assembly.
  2. 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 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:

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

Contents
previous: Constructing Assemblies next: Uniqueness and Disassembly
  Home Six Piece Burrs Box-Filling Puzzles Booklets  
About our Puzzles Rectilinear Burrs Miscellaneous Puzzles References
How to Order Non-Rectilinear Burrs Computer Programs Other Websites

Copyright 2000-2002 Bill Cutler Puzzles, Inc.