Notes on Automated Wriggle Puzzle Generation (by Bob Henderson)

About 30 years ago I entered an annual nationwide puzzle competition in the USA. One of the challenges was to solve a simple sliding block puzzle in the fewest possible moves. Having taken a few computer programming classes and automated the solutions to various block-packing puzzles, I felt sure that sliding-block puzzles would yield to a similar approach. The method I used was a full-width search: finding first all of the positions that could be reached in one move from the initial state, then those that could be reached in two moves, etc. until the goal state was found. It sped up the process considerably to store only the states that had not already been reached, which was most easily handled by storing the new states for each generation in their own file for comparison with states found in later generations.

As it happened, I won that competition, which led to a deepening interest in slide puzzles. I read L. Edward Hordern's book Sliding Piece Puzzles, corresponded with David Singmaster (who wrote its foreword), visited Nick Baxter's Sliding Blocks site, and provided Nick with several shorter slide puzzle solutions. I collected the sliding block solver software available over the Internet and even had Rik van Grol send me a floppy disc with his own original program allowing human solvers to create and solve slide puzzles on-screen.

I soon became interested in creating as well as solving such puzzles. The movement rules for most slide puzzles (as well as many other sequential-movement puzzles) allow any legal move to also be made in reverse. It followed that a solver that could take all possible winning positions as its initial state and perform a full-width search to first find all new states one move from winning, then all new states two moves from winning, etc. would eventually reach some end states from which no new states could be reached. The other sliding block solvers all seemed to be limited to only one initial state, but my solver used an input file that could include any number of states within the computer's processing and memory limits. It was not difficult to write a block-packing program to generate a file containing all the winning states for any given board (grid) and set of block shapes. Running my solver program backward (without specifying a winning state), I was able to find those states the largest number of moves away from the goal and verify that they represented the most difficult possible slide puzzles (those requiring the most moves to solve) for a given grid, set of blocks and goal.

When I learned about Andrea's Big-Wriggle challenge, I thought that it could be solved using similar logic, specifying that only the ends of each wriggler could be moved, but that all remaining segments of the same wriggler would follow in order during each move. My revised slide puzzle solver succeeded in improving the best known Big-Wriggle solution from 51 wriggles to 34 wriggles. I also used it to verify the shortest solutions for many of the other Wriggle puzzles at Andrea's Clickmazes site.

Of course, the same program could also take a collection of goal states as its input and find those states that were the most wriggles or units of movement away from them. I wrote a packing program to list all of the goal states for a given grid and set of wrigglers and began using it with the reverse solver program to find good Wriggle puzzles. A third program was written to convert my puzzle encodings to Andrea's. As manual entries became tedious, I automated the generation of wriggler lengths and blocker positions into program loops and combined the goal generation, full-width search and encoding translation routines into a single program. This enabled the search of all possible Wriggle puzzles on the four-by-four grid within about 15 minutes of laptop runtime.

My current Wriggle puzzle-generating program shows all results on-screen as it runs and also saves the best results to a text file which I later convert into Excel format to save and share. Grid sizes of up to five-by-five have been analyzed rather thoroughly, with some additional results for a limited selection of blocker positions on the six-by-five and even the six-by-six grids. More complete analyses of these larger grids are in progress, taking advantage of blocker parity considerations that apply to wrigglers of odd lengths (more on these another time).

Bob Henderson - December 2010

Wriggle-count versus total-unit-drag

Bob has hinted that solution-length for a wriggle puzzle can be measured in one of two ways, total-unit-drag or wriggle-count. Bob's automated program can optimise for either, but on small grids it turns out that optimising to maximise total-unit-drag yields a richer mix of puzzles, better suited to a large collection. Maximising for wriggle-count results in a high percentage of puzzles with only a single blank square, requiring lots of very short wriggles to solve. There are several of these in the 4-wriggler set above, where they begin to dominate due to sheer lack of space on the grid. The larger the grid, the more worthwhile it is to maximise by wriggle-count at least for low-order wriggler grids (on 4x4 it tends to be beneficial for one-wriggler grids only).

The fact that there are competing ways to measure solution length (a natural base-line for complexity) is a strong indicator that there is more to these puzzles than meets the eye. What sort of wriggle puzzle is more entertaining? One which requires a lot of short separate wriggles, or one that requires fewer but longer wriggles? It is almost certainly the unexpected long wriggles that give these puzzles their unique appeal, setting them apart from their other sliding-block cousins. To illustrate, the puzzle on the right can be solved in just two separate wriggles (first red, then blue) but the first wriggle is an incredible 17 units long!

If you are interested in finding the optimum solution for the puzzles featured above, you will find it quoted in square brackets alongside the puzzle title. To be accurate, the number quoted is the minimum total drag required to position the blue wriggler with either its head or tail immediately above the blue exit door (which is two moves short of the congratulations message). As you play, your cumulative wriggle-count [and total-unit-drag] is displayed in the bottom left of the grid.