["Beyond Tetris" is a column from Tony "Tablesaw" Delgado about puzzle games that transcend mere abstract action and instead plunge deep into the heart of problem-solving. This installment looks at the multi-state maze Theseus and the Minotaur.]

Theseus and the Minotaur is a puzzle that has been trememndously popular across the internet. Like other popular puzzles, many people are unaware of its origins. But unlike many of the puzzles I've been writing about, the history of this particular maze is pretty well documented, from its creation by Robert Abbott as a pencil-and-paper maze, through its first appearance on the web, all the way up to its current incarnations as PopCap's Mummy Maze.

Logical Mazes

A set of possible moves in Robert Abbott's Theseus and the Minotaur, taken from the 1994 Games and PuzzlesRobert Abbott is the inventor of a particular type of maze called, variably, "mazes with rules," "logic mazes," and "multi-state mazes." The first one appeared in Martin Gardner's Scientific American column in 1962. What makes the mazes different from what you would generally find in a children's activity book is that there are any number of rules that apply to the puzzle. In a common maze, you have to simply move spatially from one point to another. In a logic maze, there are rules that restrict or modify how you move. For example, in The Farmer Goes to Market, the maze published in Scientific American forty-five years ago, there are arrows that limit which way you can move, and you are not allowed to make a U-turn. As a result, the location isn't the only thing that matters in the maze, you also have to keep track of a particular state of the game: which direction you just came from.

Over the years, Abbott refined the idea of these mazes. For example, in the Alice Mazes, (taken from his 1990 book Mad Mazes), you can see the state quite clearly. As you move through the maze, the definition "d=1" will change, indicating how many spaces each move is permitted to be. In the Sliding Door Maze (from the later SuperMazes), the state of the maze is incorporated into the maze; the doors that open and close define how you can move. What's most important about these puzzles from a puzzling perspective is that when a maze has multiple states, a relatively simple layout can be incredibly complex. If you don't believe me, you should take a look at Ed Pegg, Jr.'s "Multi-State Mazes" article at MAA Online. It shows a state diagram for a simplified version of The Farmer Goes to Market, and you can see how quickly a simple maze becomes a difficult one. (The article also has a fantastic list of interactive and static multi-state mazes that I adivse you to try.)

One day, while playing the 1980 arcade game Berzerk, Abbott imagined a maze where the solver would have to avoid a robotic opponent. To make the maze a puzzle, rather than an action game, Abbott made the process turn based. The player would move, then the robot would move. "It's like I took a frenzied video game and slowed it down to one thousandth of its normal speed," said Abbott in his notes. Combining the as-the-crow-flies pathfinding of Berzerk's robots with the speed and invincibility of robot gang leader Evil Otto, Abbot had what would become "Theseus and the Minotaur" in Mad Mazes. For every step you (Theseus) took, the Minotaur would move two spaces toward you (preferring to move horizontally before veritcally). With a framing story about a robotically programmed monster, a paper grid, and movable markers for Theseus and the Minotaur, the puzzle took six weeks to design.

Raised from the Dead

Puzzle 15 in Toby Nelson's Theseus and the Minotaur applet, hosted by Robert AbbottWhen Abbott moved online and started his own website in 1998, he asked another puzzler, Oriel Maxime, to turn the pencil-and-paper puzzle into an interactive one. It started picking up steam after getting spotted on rec.puzzles. The puzzle was much easier to solve translated into an actual computer game. Ed Pegg, Jr. noted that the maze typically took a week to solve on paper, but the internet puzzlers were finishing it off much quicker.

Then about a year later, a young programmer named Toby Nelson wrote his own Java version of Theseus and the Minotaur, but this time, he added fourteen more puzzles. Nelson had designed a program to generate mazes randomly, then it refines the best ones by testing various mutations. The puzzles are then ranked according to measures like solution length and the number of false paths. (A similar program, designed by James W. Stephens, provides the basis for the many wonderful puzzles at PuzzleBeast.) This new set of puzzles was generally easier than Abbott's original, though each still required several small leaps of logic. Nelson's first thirteen puzzles provided a steady ramp of difficulty for solvers before they reached Abbott's original. And Nelson added a final puzzle. Called The Dread Maze Fifteen, it was far more complex than Abbott's.

In an interview with Puzzle Monster, Abbott considered the pluses and minuses of computer versions of his mazes. "One advantage of programs is they make sure you follow the rules. A disadvantage of programs is you can avoid any thinking by just fiddling with the controls until you chance upon the solution." But it was the fiddling that made the mazes so popular. Instead of soberly thinking through the rules of the puzzle, players could quickly learn by doing. Trying random false leads rarely provided an answer, but it occasioinally provided insight into how the puzzle worked, leading a player closer to the solution. The puzzle had become a game, and friends passed the link along in chatrooms, newsgroups, and mailing lists whether or not they could complete all fifteen puzzles.

Raiding the Tomb

An early level in PopCap's Mummy Maze DeluxeIn 2002, PopCap Games put out a Java clone of Theseus and the Minotaur called Mummy Maze, followed by the downloadable Mummy Maze Deluxe. The game gave the puzzle a graphical update (no more dots and lines). It replaced Theseus with an explorer in an Egyptian tomb and replaced the Minotaur with a mummy. It also added new content. There are scorpions that think like mummies, but can only move one space per turn. There are red mummies and red scopions who will move vertically before they move horizontally. There can be multiple enemies in a maze; forcing two of them run into each other will cause one enemey to dispatch the other. There are also changes to the environment: traps can be stepped on by monsters, but not you, and key spaces will open and close gates (much like Abbott's Sliding Door Maze).

Mummy Maze Deluxe boasts thousands of mazes. It's tempting to accuse PopCap of sacrificing quality for quantity, but I don't think it's true. There are still several wonderfully difficult rooms (and I can't think of any truly terrible ones), but overall, the puzzles are just okay. It's not uncommon for a long string of puzzles to be relatively simple once you're used to the logic, or for added elements to have no use at all. But most importantly, I don't believe that any of that is actually a design flaw. Mummy Maze, like all of PopCap's oeuvre, is a casual game. The puzzles in Mummy Maze aren't meant to send you deep into thought; they're meant to be a pleasantly stimulating pastime. You solve a few mazes, you get the puzzling itch out of your system, and you go back to doing actual work on your PC (or Palm or phone or whatever platform you're playing on). And you know that there will be plenty more mazes the next time you need a quick break.

The credits screen from Mummy Maze DeluxePerhaps the most notable thing about Mummy Maze is that PopCap, who's been criticized for its clones in the past, belatedly licensed the game from Abbott. According to Ed Pegg, Jr., "PopCap inadvertantly copied the idea for their game Mummy Maze. Soon after realizing their error, the PopCap company apologized to Robert, paid him, and now are giving him credit." I considered probing deeper into this legal mystery, but since everyone seems happy, I thought it best to let sleeping dogs lie. Still, I sometimes wonder why Abbott gets his name in the loading screen while the creators of other cloned games are left anonymous. Was it because the puzzle was created by an individual? Or because the puzzle was first devised in a published book, rather than as a computer game?

Regardless, it's fantastic that he gets the credit he deserves and that he fights so hard to protect. In fact, part of the reason that it was so easy to find information about the puzzle is because of Abbott's own efforts to publicize its history (and his role in it). Instead of searching deep into the shadowy past to figure out who wrote what and where the inspiration from, Abbott works hard to keep the story and the challenge of Theseus and the Minotaur alive for anyone to enjoy.

[Tony Delgado is a member of the National Puzzlers' League, and a solver and creater of puzzles of all sorts. He also works as the copy chief of The Gamer's Quarter.]