If you can get hold of a copy of Robert Abbott’s books Mad Mazes and Super Mazes you should immediately buy them. Unfortunately, they are out of print now. These books really redefine what mazes are all about. They contain various ingenious variations on the multi-state theme: your position in the maze is actually different depending on how you got there. Although there are many ways to make such mazes (see for example my previous posts), Robert Abbott’s designs are as good as it can get. Now one of his multi-state maze designs (or ‘mazes with rules’ as he likes to call them) has hit the app store: Theseus (iTunes link).
In this puzzle, you are poor Theseus (the little blue globe in the screenshots) trapped in Ariadne’s Maze with the Minotaur on your heels (the big red globe in the screenshots) trying to block you from escaping through the exit (indicated by the staircase). The mazes actually seem pretty simply, because there are hardly walls! However, the trick is that the real maze is only partially directed by the walls: the most important restriction blocking your movements is the Minotaur, which is trying to crush you (it actually looks slightly bloody when this happens, which probably explains the 9+ rating in the app store).
The Minotaur is actually a quick, but rather stupid robot. He can do two steps for every step you take, but he will always first move horizontally in your direction (if possible), and then vertically. Because his movements are so strict, the trick of these puzzles is to trap the Minotaur, and then make a dash for the exit. The puzzle shown in the screenshot up right (Level 10) minimally needs 42 steps. A strongly reduced state-diagram is shown here to the left, from S(tart) to G(oal). I have left out various paths that lead to sudden death in just a few steps. Only the crucial positions are shown with the minimum number of steps in between them. As can be seen from the diagram, the puzzle is actually pretty simple. In general, as Bob Hearn commented, Theseus puzzles are computationally simple. However, the real genius of Robert Abbott is not the puzzle as such, but the design of the levels!
It is unfortunate that most puzzles that are available in the app store just try to add many levels, though mostly it turns out that after a few levels you will have understood ‘the trick’, and then the rest of the puzzles becomes boring. It is very easy to make puzzles difficult (simply pump up the number of decisions needed to get to the finish). The real problem is to make difficult puzzles that are not boring. A real good puzzle has levels that each have a (slightly) different ‘aha’ effect. This is were theseus really shines—and lifts itself above most other puzzles on the iPhone. Let me explain this on the basis of this Level 10.
From the starting position you first go two steps down (A in the diagram). Then the first major decision is needed: left or right? Now, notice the U-formed box in the center of the maze. This might be a good position to trap the Minotaur! So, let’s go right and try to trap the minotaur in that box. After some trickery you can get to the position shown to the right here (B in the diagram)). However, it doesn’t work out to get the Minotaur in the box. Well, let’s try for the exit anyway: it doesn’t look bad, but actually the minotaur gets you right on the staircase (C in the diagram). A dead end of the multi-state maze.
So, from state A in the diagram, let’s try to take a right. After a long path is is possible to trap the Minotaur near the staircase (D in the diagram). This position is shown to the left here. Now Theseus can start moving back right in the direction of the U-trap again, trying to lure the Minotaur in there from another direction. You can get all the way up as shown in the state below left (E in the diagram). Now the Minotaur is coming directly at you, but unfortunately going down won’t get him into the trap. It turns out that the best you can do is end up on exactly the same position as before (B in the diagram), which led nowhere eventually.
So what now? How do you get out of this maze? Here is the ‘aha’ effect: don’t use the U-formed box to trap the Minotaur! This is just a distractor—you don’t need it. From the state shown below left go up and right to end up in the position shown below right. From there you can dash to the exit, and just keep one step ahead of the Minotaur. The genius of this level is to hide the right route by adding a distractor. This is the crux of good maze design: make a particular path that is apparently the obvious one—only to hide the right path as a inconspicuous crossing off from the most obvious straightforward path.
As a final word, I find the visual appearance of this puzzle is a little odd, given the way how apps on the iPhone normally look like. Jason Fieldman, the developer of the iPhone version of Theseus, decided to use a fake windowing environment for the game (Apple explicitly does not use windows on the iPhone), with a close button in the apple-style on the upper left, and a reset button on the upper right. I would rather have seen regular buttons, but that is of course not important for the puzzle itself. There are directional buttons for movement (as can be seen in the screenshot at the top of this post), but fortunately swipes also work.
If you are not sure whether you should buy this puzzle (which I would really urge you to do), then you can try it out online before you buy.