"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
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
- 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://www.logicmazes.com/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
- 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
- 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 Mazes 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.
This site produced by Walter D. Pullen
(see Astrolog homepage), hosted on astrolog.org and Magitech, created using Microsoft FrontPage, page last updated
April 20, 2013.