Maze Equivalence

"Maze equivalence" is the simple observation that most Mazes are the same type of puzzle. The fundamental type, to which most every Maze can be reduced to, is the "arrow Maze". This is basically just a directed graph in mathematical terms. It can be represented by a set of points or vertices, with arrows connecting them. In solving the Maze you move from a start vertex, to an end vertex, following the direction of arrows from vertex to vertex. More specifically the Maze consists of a finite and easily enumerable set of states, where at each state there's a finite and easily enumerable number of choices you can take to change to a different state.

Many types of Mazes with rules have been invented, however they are all basically directed arrow Mazes. Three good sites for various rule Mazes are http://www.logicmazes.com by Robert Abbott, http://www.mazepuzzle.com by Adrian Fisher, and http://www.clickmazes.com by Andrea Gilbert. The creativity in rule Mazes comes from the conception of the rules, and the artistry of expressing the various links and potentially large number of states within a relatively simple diagram.

Simple cases: Some Mazes map directly to arrow Mazes. Examples are:

• Arrow Maze: Some Mazes are arrow Mazes to begin with, such as http://www.clickmazes.com/mazes/c_arrows.gif and http://www.astrolog.org/labyrnth/maze/arrow.gif. Note any Maze with multiple start positions can be expressed as one with a single start, by creating a new start vertex which has arrows pointing to all the old start positions, and any Maze with multiple end positions can be expressed as one with a single end, by creating a new end vertex which has arrows pointing to it from all the old end positions.
  
• Non-rule Maze: The simplest type of Maze, i.e. the standard Maze with normal passages that can be walked down, can be treated as an arrow Maze by having arrows go in both directions down each passage, with junctions as vertices. This covers standard Mazes in any dimension.
  
• Number Maze: A number Maze, such as the one seen at http://www.logicmazes.com/n1mz.html, maps directly to an arrow Maze. The 6x6 number Maze here has 36 vertices or states, where from each vertex there are arrows pointing to the vertices the given number of units away from it. Note with some Maze representations it's easy to follow an arrow, but much harder to backtrack, e.g. in a number Maze display it's easy to look at the number to know how many units to move, but it's harder to see which other vertices lead to the current one.
  
• Tilt Mazes: Tilt Mazes, such as those seen at http://www.logicmazes.com/tilt.html, map directly to arrow Mazes. From each cell, have four arrows leading to the cell you get to when tilting the Maze in that direction. Note not all cells here may be reachable from the start, such as a cell not next to any wall, but any Maze can have inaccessible locations.
  

State cases: Some rule Mazes involve state, where not only does the solving object have a position, but it can be in one or more states at each position. This type of Maze can be reduced to an arrow Maze that looks similar to the original too, by having multiple levels, one level for each state the solving object can be in. States often involve direction, i.e. the direction you're facing at any one point affects the choices available.

• Number Maze #2: The no U-turn number Maze at http://www.logicmazes.com/n4mz.html can be mapped to a four level arrow Maze. Each cell in the 8x8 number Maze covers four vertices, one vertex for each of the four directions you can face at that cell. The Maze has 8x8x4 or 256 possible total states, although again they're not all reachable.
  
• No left turns: A no left turn Maze, such as seen at http://www.clickmazes.com/noleft/ixnoleft.htm, is another Maze that has state indicating the direction you're facing, where your relative direction is what's used to determine a left turn, and hence what choices are and aren't available at a vertex. Since at any junction you can face in one of four directions, this can also be expressed as a four level arrow Maze.
  
• Alice Mazes: The Alice Maze at http://www.logicmazes.com/alice.html has state in that you have a "size" indicating how many squares you can move. For a 5x5 Alice Maze there are four possible states you can be in at any cell, for sizes 1 through 4 (technically sizes 0 and 5 are possible too, although they're effectively dead ends). The Alice Maze can be treated as a multi-level arrow Maze, with one level for each size. This Maze has 5x5x4 or 100 possible total states (again not all reachable).
  
• Color Mazes: The color Maze at http://www.mazepuzzle.com/ColourMazes_Rainbow.html has four possible states at each position, the state being which of the four colors you most recently navigated. There are nine cells, and four possible states, so this Maze has 9x4 or 36 possible total states. The Maze here is harder than it looks, where I actually first solved it by drawing it out as a four level 3D arrow Maze, and then treating that as a normal arrow Maze which was easier to follow. :)
  
• Christmas Tree Maze: The Maze at http://www.puzzlebeast.com/christmastree/index.html seems to involve moving a line segment through the Maze, although it's still easily reducible to an arrow Maze. Treat the center of the line segment as the vertex where you're at, where the segment can be in one of two states, i.e. horizontal or vertical. The arrow Maze for this would hence have two levels, each level being a rough image of the Christmas tree.
  

Complex cases: Things get more complicated when there are multiple things in a Maze that can have state, because each combination of states of those things would need to have its own "level" in the arrow Maze.

• Sliding door Maze: The Maze at http://home.att.net/~robtabbott/sliding.html has four gates, each of which can be in two states. That makes 2^4 or 16 combinations total, so an arrow Maze of this would have 16 levels. Moving over a button amounts to taking a one way arrow to the appropriate level.
  
• Theseus and the Minotaur: The Maze puzzle at http://www.logicmazes.com/theseus.html has a deterministically moving object chasing you through the Maze. For this 6x6 Maze, there are 36 total locations you can be in, where the Maze itself can be in 36 possible states corresponding to the 6x6 possible locations the Minotaur can be in. That results in 36x36 or 1296 possible total states, where the arrow Maze for this would have that many vertices. This could be represented as a 36 level 6x6 Maze, with each level being the game board and the 36 levels corresponding to the 36 possible positions of the Minotaur.
  
• Set of goals: A Maze puzzle where you have to visit multiple goals has state, which is the set of goals reached so far. Note a Maze like this is more complicated, where it's likely only solvable if you visit the goals in a certain order. The Tilt Maze with multiple goals at http://www.clickmazes.com/newtilt/m6a.htm has six goals total, each of which can be found or not found, where the Maze can therefore be in 2^6 or 64 states total, and hence the arrow Maze of this would have 64 levels.
  
• Sokoban: The arrow Maze model starts becoming impractical for puzzles having a very large number of states, although expressing them as an arrow Maze can still be done, where it will just require a huge number of levels. In the game Sokoban, as pictured at http://www.geocities.com/karakusk/img/sok_pic.gif, you have to push a set of boxes to a set of finish squares. The level pictured is on a 17x14 grid with 25 boxes. As each box can potentially be at any location, the total number of states that Maze puzzle can be in, is potentially (17x14)^25, where an arrow Maze of this large Sokoban game would have to have that many levels.
  
• Solitaire: In general, any deterministic single player game or situation, with a finite number of states and a finite number of choices at any state, can be expressed as an arrow Maze. For example, a game of solitaire from a given deck shuffling forms a "Maze", where your goal is to get to a winning card configuration. Each reachable layout of cards is a vertex, where the number of things you can do at any point are the arrows leading to adjacent vertices. A losing position where you can't move anymore is a dead end.
  

Non-cases: Maze equivalence isn't a new type of Maze in itself, but it does help in understanding existing types of Mazes, and hence can be good to consider when inventing new types. We've seen how most things can be expressed as an arrow Maze, however what puzzles don't fit this model?

• Non-determinism: A non-deterministic Maze such as http://www.mazemaker.com/Projects_EdinburghZoo.htm can't really be expressed as a static arrow Maze, since the choices you have available aren't known ahead of time, and may depend on timing, how tall you are, etc.
  
• Opponents: A game with a human opponent such as chess can't be expressed as a static arrow Maze, since the choices you have at any position depend on what your opponent does on their turn. You can at least assume the opponent will make their best possible move, however you define "best", when deciding what move to take yourself, where that roughly maps to an arrow Maze. Computer chess programs search over game trees like this when deciding what move to make.
• Fractal Mazes: Infinite recursive fractal Mazes such as http://www.astrolog.org/labyrnth/maze/fractal2.gif have an infinite number of states, although there's still always a finite number of choices you can make at each state. Such Maze tend to have an infinite number of solutions, where the goal is finding the shortest solution or at least one that can be expressed in a finite number of moves.
  
• Hypermazes: A hypermaze doesn't really fit the model of an arrow Maze either, since there's no solving point to be mapped to a vertex, but rather a solving line, where there's a virtually infinite number of configurations and things you can do in any situation, and the solution is expressed more as a 2D figure than a 1D sequence of moves. A hypermaze such as http://www.astrolog.org/labyrnth/maze/hyper.gif is where the solving object is of a higher dimension than just a point. In a standard non-hypermaze you move a point through whatever dimension environment, where the path behind you forms an line. In a hypermaze you move a line through a 3D or higher dimension environment, where your path forms a surface.