Extreme TJ-wriggle puzzles
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.
Below is a collection of the very best of Bob's 4x4 results, the top-20 puzzles for one to four wrigglers giving a total of 80 puzzles to explore. I particularly recommend the 2-wriggler & 3-wriggler sets. Note that the puzzles in each set are in descending order of solution-length, so the trickiest puzzles tend to be found at the the top of each list, however there are plenty of surprises as you work down each set. To read more about Bob's search engine see below.
Please start by visiting the TJ-wriggle page if not familiar with the rules.
Sorry - these applets are currently unavailable
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.
puzzle set © Bob Henderson 2010
puzzle concept © Tom Jolly & Andrea Gilbert 2006
applet © Andrea Gilbert 2006-2010
hosted with permission from Tom Jolly & Bob Henderson