|
|
1965 - I wrote my first puzzle program while an undergraduate at Brown University. The program was supposed to find solutions to a 10-piece packing puzzle called `TenYen'. Computers were not generally available in those days (Brown did have one IBM 360 used in some courses), and so the program was never run on a computer.
1974 - I wrote my earliest computer program dealing with 6-piece burrs, which calculated all the solid, notchable solutions. The program had to address both the assembly-creation and disassembly problems, although neither was done in any general way. The logic that determined which assemblies could come apart was specifically tailored to solid, notchable 6-piece burrs. The program was run on a computer at Louisiana State University.
early 1980's - Prompted by some conversations with David Bruce, I wrote the first version of the disassembly program. This program, which is now called GENDA (GENeral DisAssembly), could be used to determine how to disassemble interlocking puzzles that follow a regular cubic grid. The logic of the current GENDA program has essentially not changed from that earliest program.
Program BURR6 was also created at about the same time. This allowed the user to input 6 pieces used in standard 6-piece burrs, and the program would determine all the different `assemblies' which could be created with the pieces. Each of these assemblies was submitted to the GENDA analysis routines, which determined if the pieces could be physically taken apart and put together, and the number of moves required to remove the first piece. BURR6 was then used to design Bill's Baffling Burr. The design process could be called `computer-assisted design'. I manually created a 6-piece burr which had 5 moves to remove the first piece; however there were a number of alternate ways to assemble the pieces into a 6-piece burr; but these were all much easier. I then looked at a number of ways in which the pieces could be altered without affecting the 5-move disassembly sequence. BURR6 allowed me to quickly and accurately determine if there were alternate, easy solutions, as well as to verify that the 5-move solution was still valid. After checking a number of modifications of the original design, I found a set of pieces which had 24 different `assemblies', or ways to imagine the pieces forming a 6-piece burr, but only one solution. This design was named `Bill's Baffling Burr', and was subsequently published in Scientific American.
late 1980's - Highly specialized versions of these programs were created in order to search for high-level 6-piece burrs. The GENDA routines were recoded to improve their speed for 6-piece burrs, with some of the routines being coded in 8086 Assembler. The initial goal was to find high-level 6-piece burrs by creating and analyzing large numbers of assemblies. The results were disappointing as only a few level-4 solutions were found. Code was then written to create all the different assemblies and to eliminate those which were identical to another assembly by rotation and reflection. The project to analyze all 6-piece burrs was started in 1987. By 1990 the analysis of all 35.5 billion assemblies had been completed, thanks in large part to a number of puzzle friends and co-workers, who ran the programs on their computers overnight and on weekends.
1990 - After some conversations with Trevor Wood, I was motivated to write a general box-packing program. By this time, I had written a number of programs to solve box-packing problems. The program outline was usually the same: (1) lots of setup code, executed for the most part only at the beginning of the program, to do such things as piece rotation & reflection, and (2) the solver, which did the backtrack, or tree analysis portion of the work. Depending on the type of puzzle and number of pieces, the solver could run quickly, or it could run for hours or days, or essentially forever. I had written the solver so many times that the logic was stamped into my brain. At that time Trevor Wood specialized in making box-packing puzzles with pieces made from cubes. Many of his designs used a 4x4x4 size box. I knew I could write a program that would be very useful for analyzing these types of puzzles.
And so the earliest version of BCPBOX was born. A lot of time was spent writing the solver portion in 8086 Assembler. Everything that could possibly be moved from the solver to the setup area (such as address calculations) was done. In that earliest program version I was able to achieve an 8-to-1 performance improvement in the Assembler version over FORTRAN. A major reason for this was the unusual `segmented addressing' used by DOS. Nowadays, with the advent of 32-bit Windows systems, and with the use of highly sophisticated optimizer compilers, I am lucky to see a 2-to-1 improvement in writing the solver in Assembler rather then FORTRAN.
The philosophy in adding enhancements to BCPBOX is very simple: If it fits into the framework of the program and can be included without negatively affecting the performance of the solver, add it in!
2000 - A GUI version of the programs is being developed. This is particularly useful for packing puzzles which do not use squares and cubes.
| |||||||||||||||||||||||||||
