How a computer might go about solving a wooden block puzzle

        ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
        ³                                                              ³
        ³                   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-

        ****************************************************************