Samwise Gamgee: "Mordor. The one place in Middle Earth we don't want to see any closer. The one place we're trying to get to. Just where we can't get. Let's face it Mr. Frodo. We're lost." After more trekking through the Emyn Muil, Sam comments, "This looks strangely familiar." Frodo provides an explanation. "Because we've been here before. We're going in circles."

Suppose they were in a layout like the below set of cards, and that going from card to card required the magic elvish rope. In addition, suppose that the rope could never go up twice in a row, or down twice in a row. Up and down have to alternate. Warning: the solution will be shown after the next paragraph.

Figure 1. With alternate ups and downs, go from Start to Finish. By Ed Pegg Jr.

The travelers would start by going Up to plateau A, then Down to B, Up to C, Down to D, then Up to E. From there, they would need to go Down to C ... a place strangely familiar. It might seem as if they had wandered in a circle back to where they had been moments before. However, the state of the magic rope is different. The first time, they climbed up to C. This time, they rappelled down to C.

Frodo and Sam could have avoided a lot of wandering around by using programming techniques. The state of the magic rope matters a lot, so a listing of each possible state and position is helpful. AU (A up), AD (A down), BU, BD, and so on. BD is connected to AU and CU. BU is connected to JD and LD. Card B can be visited with the rope in differing states. It is thus a Multistate maze. By linking together the 35 possible states, the solution becomes easy. The map of positions is called a state diagram. You are strongly urged to solve the maze before looking closely at the answer!

 START-AU-BD-CU-DD-EU-CD-LU-ED-TU-MD-OU-RD-MU-KD-JU-LD-KU-GD-IU-OD-PU-SD-RU-TD-UU-FINISH
                                           |        |                                   
                                           ID-FU    BU-JD-GU-FD-HU-PD                   

Robert Abbott is the inventor of multistate mazes. He calls them logic mazes (his site name), or mazes with rules. His first such maze appeared in Martin Gardner's Mathematical Games column in the October 1962 Scientific American. Also in 1962, his program for the game of owari defeated a program by Gerald Weinberg (Forty years later, John Romein completely solved owari). Mazes, program flowcharts, and state diagrams all have similarities, so it makes sense that a skilled programmer invented this puzzle genre. For this column, Robert created a simplified version of the 1962 "The Farmer Goes to Market", along with its state diagram. For a non-simplified version, see his Mad Mazes page.

Figure 2. Farmer Goes to Market maze. By Robert Abbott.

Robert Abbott has created many more mazes since his first one. His puzzles have appeared in Games, Scientific American, Discover, and the Mensa Bulletin. He has published two books about mazes. Two of my all time favorite puzzles, Arrow Hockey and Meteor Storm, are in these books. As of November 2003, he has about twenty copies of each book left, should you desire to purchase them. I highly recommended perusing everything at his site -- especially Eyeball Mazes, Alice mazes, Theseus and the Minotaur, Sliding Door maze, Tilt mazes, and Rolling Block mazes. His creations frequently show up in programming competitions. They are the subject of Michael Madden's recent paper on progressive learning.

Inspired by Robert, many others have started creating good mazes with rules.

Robert's foremost protégé is Andrea Gilbert, the creator of clickmazes.com. Her Plank puzzles were recently selected by the Games 100 as the Puzzle of the Year, as River Crossing. (Robert Hearn recently proved that her plank puzzles are PSPACE-complete.) 2D Tilt mazes,Colour-zone, and Orientation Mazes are all worth a look. The original Orientation Maze is well suited to a walk-through -- all you need is 18 sheet of paper and a small patch of floor. My favorite Andrea creation is the Maze of Life, which adds an intelligent cell to Conway's Game of Life. The cell can move one space, each turn. After a step, the universe is updated in accordance with Life rules. As such, the intelligent cell will die if it isn't touching 2 or 3 other cells. Knowledge and movement turn out to be very powerful -- William Paulsen has shown that an intelligent cell starting in a loaf can build a glider gun in 247 moves. (If that maze isn't tough enough for you, try going from a loaf to a Switch Engine.)

Oskar van Deventer is best known for Oskar's Maze. Oskar has developed many more mechanical maze mechanisms, and maybe one day most will be available for sale. At the moment, most of his puzzles are available only from Hanayama Toys, in Japan. Andrea is hosting many of Oskar's mazes, including 4D maze, Hexaroll, Four bit, and Hysteresis.

Adrian Fisher is the master of building large walk-through mazes. His 1986 Scientific American article was the first to cover multi-state mazes in depth. He often installs multi-state mazes near the entrances to his larger creations. Frequently, the multi-state maze that fits in a small room will be more difficult and more bewildering than the 16 acre, 8 mile maize maze nearby. You can see his current world listing of mazes at his site.

Scott Kim is a gifted puzzle creator, and has developed many new maze types. Scott Kim's Boggler column on multi-state mazes is currently at the Discover magazine site, and will eventually wind up at Scott Kim's site.

James Stephens wrote one of the early programs to study Andrea's Plank puzzle, and wound up creating a lot of new puzzles on the side. His discoveries and creations are viewable at his PuzzleBeast website.

Erich Friedman develops more puzzles than anyone else I know. In addition to his Rolling Block Mazes, the rest of his site covers almost all aspects of recreational mathematics. Here is an extremely popular puzzle maze he created for me, the 12345 Maze. You start on S. You can move 1 square in any direction, followed by 2 squares in any direction, then 3, then 4, then 5, and back to 1 again until you land on F.

Figure 3. The 12345 Maze. By Erich Friedman.

I'll close with the Small Fractal Maze, by Mark J. P. Wolf. A Fractal maze is fractal because it has identical copies of itself embedded within itself, which can be entered. In the maze below, you must enter them to solve the maze. Begin at the MINUS and make your way to the PLUS. When you enter a smaller copy of the maze, be sure to record the letter name of that copy, as you will have to leave this copy on the way out. You must exit out of each nested copy of the maze that you have entered into, leaving in the reverse order that you entered them in (for example: enter A, enter B, enter C, exit C, exit B, exit A). Think of it as a series of nested boxes. If there is no exit path leaving the nested copy, you have reached a dead end. Color has been added to make the pathways clearer, but it is only decorative.

Figure 4. The Small Fractal Maze. By Mark J. P. Wolf

References:

Abbott, Robert: Mad Mazes. Bob Adams, Inc, 1990.

Abbott, Robert: SuperMazes. Prima Publishing, 1997.

Hearn, Robert A. The Complexity of Sliding-Block Puzzles and Plank Puzzles. http://www.swiss.ai.mit.edu/~bob/sliding-blocks.pdf

Weisstein, Eric W. State Diagram. Eric Weisstein's World of Mathematics. http://mathworld.wolfram.com/.

Math Games archives.

Comments are welcome. Please send comments to Ed Pegg Jr. at ed@mathpuzzle.com.

Ed Pegg Jr. is the webmaster for mathpuzzle.com. He works at Wolfram Research, Inc. as the administrator of the Mathematica Information Center.