|
|
| Contents |
|
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.
In the early 1980's, two events triggered an expanded analysis of 6-piece burrs:
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.
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:
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.
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!
The amount of data generated by the computer runs was considerable. The main summary of the results counted the assemblies by:
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 |
|
| |||||||||||||||||||||||||||
