Overview of Analyses BCPI logo billcutlerpuzzles.com

Contents
previous: Acknowledgements next: The Pieces

Introduction

The analysis presented in this booklet is the natural culmination of several previous analyses of 6-piece burrs. It also combines two different interests of mine: computer programming and burrs.

When I was 12 years old, I saw a model of a 6-piece burr in a drugstore window, and became fascinated with it. Like many people before me, I attempted to catalog solid 6-piece burrs which used notchable or more limited sets of pieces, but gave up at the enormity of the project. After reading E.M.Wyatt's books "Puzzles in Wood" and "Wonders in Wood" [8] & [9], I started to design my own burrs. I was particularly intrigued with designing burrs which took many moves to remove the first piece. These designs typically had at least 18 pieces. The size of the 6-piece burr did not allow for implementing most of the "tricks" that I used in the designs.

In college I was exposed to computers, and became fascinated by the possibility of using computers to solve mechanical puzzles, in particular "box-packing" puzzles. However, I could only pursue this interest in theory because of the limited availability of computers.

Solid Analyses

In 1974 my interest in computers was rekindled, and I wrote the first programs to analyze 6-piece burrs. These programs did little more than count solid solutions. They included some rudimentary logic to check for symmetry so that rotations & reflections would be properly identified. The code used to throw out assemblies which did not come apart was specifically tailored for solid, 6-piece burrs; all it did was implement specific rules which had been developed by hand. The analysis of solid, notchable 6-piece burrs was done jointly with Tom O'Beirne and was published in the Journal of Recreational Mathematics [3] and is referred to as JRM in this booklet. A later analysis of all solid 6-piece burrs was done with the assistance of Arthur Cross. The results of this study were made available as a 1-inch stack of computer output [4] and was referenced in Martin Gardner's column in Scientific American [7]. Arthur Cross also wrote up the results in a booklet [2]. We will refer to this analysis as SCIAM.

Computers & Burr-Disassembly Programs

In the early 1980's, two events triggered an expanded analysis of 6-piece burrs:

  1. Following conversations with David Bruce, I was motivated to write a computer program which could disassemble interlocking puzzles made from cubes.
  2. Stewart Coffin, who had been toying with "holey" 6-piece burr designs, challenged his readers to design their own 6-piece burrs and offered to manufacture the design that he chose as best.

The result was BURR6, a powerful program for analyzing 6-piece burrs, and Bill's Baffling Burr. BBB is an example of a "computer-assisted design". The sequence of moves used to take out the first piece was chosen by hand along with an initial set of piece shapes to carry this out. The computer program was used to verify the take-apart steps and to search for alternate solutions using the same pieces ("uniqueness" check). Nine variations of the pieces were analyzed by the programs, and one of these which had a unique solution was chosen as Bill's Baffling Burr.

Thus began the investigation into "holey" 6-piece burrs. From the beginning, it has been required that all "holes" in a 6-piece burr are not visible from the outside when the burr is in its assembled state, and therefore are limited to the 32 internal cubes of Figure 2. After the initial success of Bill's Baffling Burr, I ran programs which analyzed thousands of assemblies constructed from limited piece sets looking for high-level solutions. The results were disappointing - the highest level discovered was only 4.

In June of 1986 I purchased an 8MHZ IBM PC AT for the express purpose of running puzzle analysis programs. The personal computer made available much more computer time to me than was previously possible. Although large, "mainframe" computers still ran about 40 times as fast as the AT, the PC could be run 24 hours a day, which equated to considerably more time than could be commandeered by an ordinary programmer on his work machine. In addition, puzzle problems are mostly combinatorial in nature, so deal with small integers rather than single or double-precision floating point numbers used by most "number-crunching" programs. Such combinatorial problems are ideally suited for running on PC's.

NOTC - Notchable, Holey Analysis

I continued to fine-tune the performance of the programs and in the spring and summer of 1987, I ran a complete analysis of all notchable, holey 6-piece burrs. I found many high-level burrs, including two level-10 assemblies. Unfortunately, the highest level for unique solutions in the notchable case was only 5. The method used to construct the notchable assemblies is described in Chapter III, except that the pieces were restricted to notchable ones.

HB6 - General, Holey Analysis

I then looked into the possibility of analyzing all 6-piece burr assemblies. My original estimate for computer time needed to do this analysis on my computer was 400 years. Obviously, I was going to need some help! I started with the low-hole assemblies, because I was mainly interested in unique solutions. Unique solutions are much more likely to occur when there are few holes, and low-hole assemblies had the additional advantage that they could be analyzed more quickly.

These first programs were run on 0, 1, 2 and 3-hole assemblies, and were called GB6 programs. The assembly-construction logic for these programs was more complicated then that used in the NOTC analysis.

Two things happened to speed up the project immensely:

  1. Harry Nelson, who had access to a number of Cray computers at Lawrence Livermore Labs, offered his services. He was able to run the programs on these machines when they had nothing better to do.
  2. The introduction of the 80386 chip and the proliferation of PC's with these chips gave me access to much more power through work and puzzle friends.

After the runs were completed on the 0-3 hole assemblies, and the 4 and 5-hole analyses were well under way, the HB6 programs were written to analyze assemblies with from 6 to 15 holes. These programs were not used to analyze assemblies with 16-20 holes because there are so few of these assemblies, and allowing for these would increase the size of the program and datasets. The high hole assemblies were run in a short time using a different set of programs called IB6.

The assembly-construction logic from the HB6 programs was used to COUNT all assemblies. These results were later used to check the validity of the counts from the NOTC, GB6 and IB6 programs. These counts were also used to make a better prediction of the computer time needed to complete the analysis. The new time estimate was reduced to 62.5 years on one PC AT, due mainly to the fact that notchable assemblies are likely to have more holes than un-notchable assemblies.

The result was that it took only two and one-half years to complete the analysis of all 35.5 billion 6-piece burr assemblies.

The tables in the Appendix give examples and summary results of the analysis. Tables 9, 13 and 14 were used to keep track of the status of the project as it progressed.

Computer Usage and the Four-Color Problem Analysis

The amount of computer time used in the project was enormous.

The unit of computer time used throughout the analysis and in the tables in this booklet is the 'AT-hour', or 1 hour on an 8 MHZ IBM PC AT. Although only a small part of the analysis was run on this machine (and similar machines have been obsolete for years), it was convenient to keep this unit of measure for the duration of the project. The table below is a rough comparison of the speeds of several old and current machines. Some of the numbers are more accurate than others - comparisons of PC's were easily made by running identical programs; PC - mainframe/workstation comparisons were made running comparable FORTRAN programs; and the factor for the IBM 360 mainframes is a guess. The numbers are supposed to represent a comparison when running combinatorial (or small integer) problems. Floating point power ('math co-processor' chips on PC's) is unused. The numbers assume a comparable level of programming efficiency on each machine (optimized FORTRAN on both, or assembly-language on both, written for performance).

Computer/Maker Chip/Speed Year Speed Factor Time for HB6
Complete Run
IBM PC AT 8MHZ 80286 1986 1.0 62.5 years
IBM PC 8086 1984 0.25 250 years
IBM PC w. Intel 16MHZ 80386 1988 3.0 21 years
Gateway 2000 33MHZ 80486 1992 14.0 4.5 years
IBM 3083 mainframe   1988 40.0 1.5 years
IBM 3090-600E - single processor   1993 85.0 9 months
IBM 3090-600E - all six processors   1993 500.0 6.5 weeks
IBM 360 mainframe   1975 6.0 10 years
IBM RS6000 workstation - model 250T   1993 200. 4 months

By comparison, the best-known (and earliest) use of computers for solving mathematical problems was the proof of the Four-Color Map Theorem completed by Kenneth Appel and Wolfgang Haken at the University of Illinois in 1978 [1]. They used a total of about 2,000 hours of computer time on 3 IBM 360 mainframe machines. Using the factor of 6 above, this is equivalent to about 1.4 AT-years, so the HB6 project took about 45 times as much computer power to complete.

I am currently the System Administrator for a network of 8 RS6000 workstations at CR Industries. These machines are left running at all times. If I scheduled the HB6 programs to run on these machines at a low priority, the project would be completed in a little over 2 weeks. Within a year, the number of workstations is expected to climb to over 30, and the runtime would reduce to 4 days!

Availability of Computer Results

The amount of data generated by the computer runs was considerable. The main summary of the results counted the assemblies by:

  1. Notchable or General
  2. Number of Holes
  3. Level-Type
  4. Symmetry Type

Tables 4, 5, and 6 in the Appendix give sub-totals of this larger table, but the entire table is too large to include in this booklet. The table is available on computer diskette and is called SUMDSN.txt.

About 70,000 high-level solutions were saved. These are available in either LL Format (4 diskettes) or AF Format (10 diskettes).

If you are interested in obtaining any of the computer results on diskette, write to Bill Cutler Puzzles, Inc., 405 Balsam Lane, Palatine, IL 60067 for more information.

Contents
previous: Acknowledgements next: The Pieces
  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.