Welcome to extreme TJ-wriggle! The sample puzzles on this page are a small taste of a large collection of new TJ-wriggle puzzles uncovered by Bob Henderson (USA) using automated computer search. Bob has explored many grid sizes from 3x3 upwards, but the 4x4 grid turns out to be the smallest grid where the results start to get exciting, with puzzles exhibiting the depth and variety that we have come to expect from the wriggle-rule.
About 20 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).
puzzle set © Bob Henderson 2010
puzzle concept © Andrea Gilbert & Tom Jolly 2006-10
applet © Andrea Gilbert 2006-2010
hosted with permission from Bob Henderson