Mazes are a favorite kind of puzzles for many. Actually, I will argue below that all sequential movement puzzles are actually concealed mazes. However, one important distinction to be made first is that between a maze and a labyrinth. A labyrinth (like the famous one shown to the left here) is only a single twisted path without junctions. There is no possibility to get lost here, and consequently it cannot really considered to be a puzzle. Only when junctures and dead ends are introduced, the puzzling aspect becomes worthwhile, and then the puzzle is called a maze.
Basic options to make labyrinths more difficult is to add holes or obstacles that have to be evaded, or use multiple balls that have to be manipulated at once, like in the following apps (links redirect to iTunes): Labyrinth (shown to the left), iBall3D, Amazing Maze, and aMaze! Such labyrinths pose a nice dexterous challenge (and particularly Labyrinth is a gorgeous experience), but they are not really puzzles in an intellectual sense.
There are also many basic maze puzzles available in the app store, like (links redirect to iTunes): iMaze, Maze Central, Micro Labyrinth, FuguMaze, Matrix, Tilt Me, Maze and Marbles, and Labyrinth3D. Most of them use computer generated mazes, like the one from Maze Central shown to the right here. They get a bit more difficult than single-path labyrinths by adding junctures and dead ends. However, such mazes are easily solved by the right-hand rule (always follow the wall on your right).
Good maze designs trick people by using their automatic reactions. For example: people are more likely to take a straight path, so trick them by adding a juncture shortly after a corner, with a long straight path that will eventually lead to a dead end. Another central trick to make mazes more difficult is to add circles. The longer and more twisted circular paths are, the less likely people will notice them (and also the right-hand rule won’t work: more complex strategies are needed). Good mazes need a good maze designer. Simple algorithmic designs simply don’t make a nice puzzle. You want to see real good traditional maze design: check out the classic maze designs by Andrea Gilbert!
But now to the real important point: all sequential movement puzzles can be analyzed as mazes by considering the graph of their state diagram. For example, consider the simple Subway Shuffle puzzle, shown to the left. The corresponding state diagram is shown below. In the state diagram, the starting position is indicated with S and the finish position with F. All the smaller circles are possible positions of the complete set of subway cars in the puzzle. The lines connecting the states are the moves needed to get from one position to the other. The color of the lines correspond to the color of the subway car, with the red dotted line representing the main car. From the state diagram it is immediately obvious how to get directly from S(tart) to F(inish). Just as with all mazes, Subway Shuffle puzzles become more difficult the longer the paths are that lead to a dead ends in the state diagram, and the more large circles there are in the state diagram. Also note that the first two possibilities to move the main car both lead to dead ends. This is another typical characteristic of a good maze: fool the puzzler by offering an obvious move that leads to a dead end.
The real trick of making a good sequential movement puzzle is to conceal the state diagram from the puzzler (and of course to design the state diagram such that it is an interesting maze). A really interesting way to conceal the state diagram is to superimpose it onto itself and create so-called ‘multi-state mazes’. The idea is to have a basic maze to move through, though every position actually has different states in the state diagram. An example can explain this better. Consider the 1-2-3 Maze from Hiroshi Yamamoto shown to the left. It is of course trivial to get from S(tart) to F(inish) when you could just walk one tile after another. The trick of this maze is that you are only allowed to walk one tile, then you have to take two tiles straight, and then three tiles straight, and then start over again. Standing on a tile thus actually can be one of three states in the state diagram on this puzzle. The result is that it actually takes 39 moves to get from S to F.
More information on multi-state mazes can be found on Ed Pegg’s survey of them, or on the Web page of Robert Abbott, one of the great masters of multi-state maze design. And there are a few interesting multi-state maze-like puzzles in the app store that I will discuss in subsequent posts. Stay posted!
Puzzling iPhone 
1 December 2008 at 4:27
You hit the nail on the head with this post. I always study the game tree (state diagram) for candidate Subway Shuffle puzzles before adding them to the set. But you can only learn so much from the game tree; a lot of the play characteristics come from the perception of the embedding.
This simple-looking puzzle:
has a very simple game tree (start node at top; solution nodes have solid red circles):
And indeed, it’s not one of the harder Subway Shuffle puzzles… but many people seem to have a very hard time with it, with some convinced it’s impossible. Without the game tree in front of you, when you back out of a 3-long dead end, it’s all too easy to forget where you came from and start moving back up the tree.
Of course, many puzzles also have complicated game trees, with loops and crossings.