旼컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴커 � � � Steve Gibson's InfoWorld � � Magazine TechTalk Column � � for InfoWorld Issue #41 � � � 읕컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴켸 �袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴敲 � Beyond Accounting: How a computer might � � go about solving a wooden block puzzle. � 훤袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴� This week marks the end of my fifth consecutive year writing this TechTalk column for you every week. Somehow, despite the generation of 255 separate columns, I've never missed a week nor run out of ideas and discoveries to share. I remember worrying, many years ago, that I might soon exhaust the supply of worthwhile topics. But as this TechTalk column begins its sixth year, I see no such end in sight. I suppose that it won't come as news to any of you that I'm a total technology junkie who just can't get enough. Although many people regard the culture, lore, and details surrounding computers as boring, incomprehensible, and "nerdy", you're reading this right now because you haven't shut yourself down with such thoughts. So let's glide forward together into the sixth year of the TechTalk column, seeing what new amazing applied miracles our technologies will enable for us tomorrow. I recently ran across a gifted machinist who has a penchant for puzzles. The first thing Bob handed me was an assembly of wooden pieces which were keeping a 5 cent nickel captive. A hidden "gravity lock" required a subtle twist of the wrist at just the right moment in order to free the nickel. Well, luck must have been smiling upon me when I stumbled upon the solution for this first puzzle almost immediately. Bob quickly determined that he'd found a fellow puzzler, and so pulled a slightly bowed stick of wood from another pocket. My eyebrows peaked when I saw that this solid and almost featureless stick would only spin in one direction. When given a hard spin in the "wrong" direction, the stick would slow down and stop, then resume spinning in the "correct" direction. Looking carefully at the stick I saw that the specific shape of Bob's stick transferred the energy from spinning in the "wrong" direction spin into a vibration along the stick's long axis, this allowing the stick to store the energy of the spin in another form (vibration), and then to turn this vibrational energy back into a resumed spin in the "correct" direction. Over the course of the next several months I was able to solve the various puzzles Bob presented. Then Wednesday before last he handed me nine blocky pieces of wood with the instructions to assemble them into a 3 by 3 by 3 checkerboard cube. He had a sample cube rubberbanded together as a demonstration of the objective. After struggling without result for a few minutes (to Bob's extreme delight), it became clear that no solution lay near. So I took the nine loose pieces home with me. Just as I was leaving Bob made my day by mentioning that it had taken him over a month to assemble the cube. Great. Later that evening, as I was messing around with the nine separate pieces that refused to assemble themselves into anything even remotely resembling a cube, let alone a checkerboard, I began imagining a month of my life slipping away. Not long afterward I decided to write a computer program to solve Bob's wooden block puzzle. It's obvious that computers can do things such as manage accounting data, compute interest rates, and recalculate spreadsheets, but it's not nearly as obvious how a computer, which fundamentally adds and subtracts numbers, might be used to solve a puzzle as abstract as this one. The key to applying a computer to a problem that lies outside the domain of numerics is to represent the problem within the domain of numbers. In other words, we must first invent a representation system that can be used to contain and describe the problem numerically. Once we have established a means of representing the reality of the problem numerically, a computer can be programmed to meaningfully manipulate the result. The puzzle pieces consisted of simple light and dark blocks of wood glued together into complex shapes. Since some of the wooden blocks consisted of half cubes, I needed a way of describing where there was wood and where there wasn't within each cube-space. Conveniently, a complete cube has eight corners, just as a computer's data byte has eight bits, so the multiple-block configuration of the various pieces could be described by a collection of data bytes where the individual bits in each byte represented which corners of their corresponding cubes contained wood. Are you with me so far? Since the final assembled 3 by 3 by 3 checkerboard "master cube" would be built up from an array of 27 smaller cubes (3x3x3=27), I decided to use a 27 byte data array to describe the current composition of the master cube as the computer worked toward its solution. The first nine data bytes would represent the 3 by 3 pattern of wood in the top layer of the assembled master cube, the next nine bytes would represent the wood in the middle layer, and the last nine would represent the wood in the bottom layer. This 27-byte data array would thus serve as a master template for modelling the 3 dimensional space occupied by the master cube. Sliding wooden pieces around within this 3 dimensional space would simply consist of copying data bytes from one location to another. Computers excel at performing repetitive tasks, and they can be quite fast at doing so if they're programmed correctly. So my brute force "strategy" for solving this puzzle would be to explore all possible arrangements of all of the pieces. Somewhere among all of the possible combinations of the individual pieces there would be one combination where none of the pieces collide within the 3 by 3 by 3 master cube space. This combination would be the solution to the puzzle. Since this meant that each of the nine wooden pieces needed to be placed into every possible location and orientation within the 3 by 3 by 3 master cube, I decided I decided to begin by having the computer generate every possible position for each piece within the space of the master cube. For each of the nine puzzle pieces the computer would create a set of 27-byte arrays with each 27-byte array representing one piece floating within the 3 dimensional space of the 3 by 3 by 3 master cube. Each of the possibilities was created by describing the way the wood would move within the master cube when it was rotated about, and translated along, each of its three axis. By exploring all possible "translations" for every possible "rotation", and eliminating duplications, tables representing all possible piece locations were created. Written in pure assembly language (as is still my preference) the computer required less than a second to build the images of each piece occupying every possible position. It turned out that eight of the nine pieces could occupy 72 different locations within a 3 by 3 by 3 cube, and that the remaining piece could occupy any of 96 locations. This meant that the total number of possible piece configurations for the puzzle would be 72 x 72 x 72 x 72 x 72 x 72 x 72 x 72 x 96 since each piece could be in any of its possible locations when all of the remaining pieces were in any of their possible locations ... all at once! When I multiplied this out I was a bit daunted to see that there were a little more than 69,331 million million possible combinations of pieces! Although the universe would still be intact when the computer had finished exploring them all, Bob and I would be ancient history. Salvation lay in the fact that the computer did not need to consider nearly this many total combinations. If the positions of the first two pieces collided within the master cube, there's no reason to worry about any of the 13 million million arrangements of the remaining 7 pieces and if the first three pieces were in collision then the 185,752 million combinations of the remaining 6 piece's could be safely ignored. This process of successive refinement serves to radically lower the total number of possibilities which must be examined. In computer parlance, an exhaustive search through a domain of such possibilities is called a "tree search" and making the decision to limit the search down a particular "branch" of the tree is known as "pruning the search tree." When the program was completed I fired it up and watched the screen flicker with a dazzling display of spinning pieces. (I'd given the program a nifty user interface too.) After about eight minutes and over 252,000 calculated moves the computer came to a grinding halt proudly displaying the correct solution to the puzzle. If you'd like to watch your own computer solve this puzzle it's available for downloading, with my complete source code, from the Gibson Research BBS at (714) 830-3300. It's amazing what computers can do! -30- ****************************************************************