mazes

A maze is a tour puzzle in the form of a complex branching passage through which the solver must find a route. This is different from a labyrinth, which (strictly speaking) has an unambiguous through-route and is not designed to be difficult to navigate (despite the common uses of the word to indicate various complex, confusing structures). The pathways and walls in a maze or labyrinth are fixed (pre-determined). Maze-type puzzles where the given walls and paths may change during the game are covered under the main puzzle category of tour puzzles.

Mazes have been built with walls and rooms, with hedges, turf, or with paving stones of contrasting colors or designs, or in fields of crops such as corn or, indeed, maize. Maize mazes can be very large; they are usually only kept for one growing season, so they can be different every year, and are promoted as seasonal tourist attractions. One type of maze consists of a set of rooms linked by doors (so a passageway is just another room in this definition). Players enter at one spot, and exit at another, or the idea may be to reach a certain spot in the maze. Mazes can also be printed or drawn on paper to be followed by a pencil or fingertip. One of the short stories of Jorge Luis Borges featured a book that was a literary maze. Various maze generation algorithms exist for building mazes, either by hand or by computer.

Solving mazes

The mathematician Leonhard Euler was one of the first to analyse plane mazes mathematically, and in doing so founded the science of topology.

The following algorithms are designed to be used inside the maze by a traveler with no prior knowledge of the maze's layout. There are other algorithms that can be used for solving paper mazes, where the solver has an overview of the maze.

Wall follower

The wall follower, the best-known rule for traversing mazes, is also known as either the left-hand rule or the right-hand rule. If the maze is simply connected, that is, all its walls are connected together or to the maze's outer boundary, by keeping one hand in contact with one wall of the maze the player is guaranteed not to get lost and will reach a different exit if there is one; otherwise, he or she will return to the entrance. If the maze is not simply connected, this method will not help a player to find the disjoint parts of the maze.

Wall following can be done in 3D or higher dimensional mazes if its higher dimensional passages can be projected onto the 2D plane in a deterministic manner. For example, in a 3D maze up passages can be assumed to lead northwest, and down passages can be assumed to lead southeast; standard wall following rules can then be applied.

Pledge algorithm

Disjoint mazes can still be solved with the wall follower method, if the entrance and exit to the maze are on the outer walls of the maze. If however, the solver starts inside the maze, it might be on a section disjoint from the exit, and wall followers will continually go around their ring. The Pledge algorithm (named after Jon Pledge of Exeter) can solve this problem.

The Pledge algorithm, designed to circumvent obstacles, requires an arbitrarily chosen direction to go towards. When an obstacle is met, one hand (say the right hand) is kept along the obstacle while the angles turned are counted. When the solver is facing the original direction again, and the angular sum of the turns made is 0, the solver leaves the obstacle and continues moving in its original direction.

This algorithm allows a person with a compass to find his way from any point inside to an outer exit of any finite and fair 2 dimensional maze, regardless of the initial position of the solver. However, this algorithm will not work in doing the reverse, namely finding the way from an entrance on the outside of a maze to some end goal within it.

Random mouse

This is a trivial method that can be implemented by a very unintelligent robot or perhaps a mouse, but which is not guaranteed to work. It is simply to proceed in a straight line until an obstruction is reached, and then to make a random decision about the next direction to follow. This will of course fail if the exit is only reachable by an opening in the middle of a wall, not directly opposite an obstacle.

Tremaux's algorithm

Tremaux's algorithm is an efficient method that requires drawing a line on the floor to mark a path, and is guaranteed to work for all mazes that have well-defined passages. On arriving at an unmarked junction, the solver picks any direction. If the solver has visited the junction before, he can return the way he came. If revisiting a passage that is already marked, he draws a second line, and at the next junction takes any unmarked passage if possible, otherwise taking a marked one. He will never need to take any passage more than twice. If there is no exit, this method will take him back to the start.

See also [1]

Generating Mazes

There are many different approaches to automate the generation of mazes.

Stack based approach

This is also the simplest way to generate a maze using a computer. Consider the space for a maze being a large grid of cells (like a large chess board), each cell starting with 4 walls. Starting from a random cell, the computer then selects a random neighbouring cell that has not yet been visited. The computer removes the 'wall' between the two cells and adds the new cell to a stack (this is analogous to drawing the line on the floor). The computer continues this process, with a cell that has no unvisited neighbours being considered a dead-end. When at a dead-end it backtracks through the path until it reaches a cell with an unvisited neighbour, continuing the path generation by visiting this new, unvisited cell (creating a new junction). This process continues until every cell has been visited, causing the computer to backtrack all the way back to the beginning cell. This approach guarantees that the maze space is completely visited. As stated, the algorithm is very simple and does not produce overly complex mazes. More specific refinements to the algorithm can help to generate harder to solve mazes.

Mazes open to the public

Europe

• Blake House Craft Centre, Braintree, Essex, UK (Open July-Sept)[2]
• Chatsworth House, England (hedge maze)
• Hampton Court Palace, England (hedge maze)
• Hoo Hill Maze, Shefford, Bedfordshire, UK.
• Noah's Ark Zoo Farm, Bristol, England (longest hedge maze in the world, planted 2003) [3]
• Leeds Castle, Maidstone, Kent, England. Designed by Adrian Fisher
• Longleat, England (hedge maze)
• The Crystal Palace, England. A tiny maze in the park.
• Saffron Walden, Essex, England, UK (hedge maze)
• Samsø, Denmark [4]
• Altjeßnitz, Germany, Sachsen-Anhalt, nr Dessau (hedge maze, c.1750)
• Schönbrunn Palace, Austria (small entrance fee, tower at the center to overlook the hedge maze)
• Castlewellan, Northern Ireland, world's largest permanent hedge maze.[5]
• Richings Park Amazing Maize Maze, Richings Park, nr Heathrow, UK (Open July-Sept) [6]

North America

• Maize Quest Fun Park Maize Quest is the "Largest Collection of People-Sized Mazes in the World" with mazes made of Fence, Rope, Stone, Turf, Corn, Invisible Dog Fencing, Straw Bales, Tiles, Living Bamboo, and Earthen Mounds. New Park, Pennsylvania, USA
• Sever's Corn Maze (America's Largest Corn Maze) Shakopee, Minnesota, USA
• The Maze on Centre Island, Toronto, was a Centennial gift to the city by its Dutch-Canadian community in 1967. This topiary maze is open to public for free year-round
• Labyrinthe du Hangar 16, Montreal, Canada. [7]
• Davis' Mega Maze, Sterling Mass USA (3-D adventure corn maze). Designed by Adrian Fisher. [8]
• Magnolia Plantation, Charleston, South Carolina, USA
• Children's maze (made out of packs of hay), Ashland Berry Farm, Ashland, Virginia, USA.

Africa

• Serendipity Maze, Mouille Point, Cape Town, South Africa. Hedge maze by the sea.
• Soekershof Walkabout Mazes and Botanical Gardens in Robertson, Western Cape, South Africa. 13870 m² net area. [9]

Mazes in science experiments

Mazes are often used in science experiments to study spatial navigation and learning. Such experiments typically use rats or mice. Examples are

• the Barnes maze
• the Morris water maze
• the radial arm maze.

Other types of mazes

Logic mazes

These mazes use some rule other than "don't cross the lines" to restrict motion. Examples are

• Area-mazes or A-mazes, which the area of the tile stepped on must alternatingly increase and decrease with every step.
• Dice mazes, in which a die is rolled onto cells based on various rules.
• Number Mazes, in which a grid of numbers is navigated by traveling the number shown on the current square.
• Multi State mazes, in which the rules for navigation change depending on how the maze has been navigated.

Mazes in higher dimensions

It is possible for a maze to have three or more dimensions. A maze with bridges is three dimensional, and some natural cave systems are three dimensional mazes. The computer game Descent utilized fully three- and four-dimensional mazes. Any maze can be topologically mapped onto a three-dimensional maze.

Picture maze

A maze that forms a picture when solved. See picture maze

Dead end maze

A maze game where the route creates the dead ends.

See also

• Maze (book)

Further reading

• Adrian Fisher & Georg Gerster, The Art of the Maze, Weidenfeld & Nicolson (1990) ISBN 0-297-83027-9
• Jeff Saward, Magical Paths, Mitchell Beazley (2002) ISBN 1-84000-573-4
• W.H. Matthews, Mazes and Labyrinths: Their History and Development (1927). Includes Bibliography. Dover Publications (1970) ISBN 0-486-22614-X

External links

• A Wiki of Hundreds of Mazes available to the general domain
• Flash Maze Generator
• Picturemaze game
• Hoo Hill Maze: Shefford, Bedfordshire, UK.
• Mazes: Construction and Solution with Java illustration
• Maze Algorithms: This site explains the different types of mazes and how to generate and solve them
• Make a Maze: This site has a maze generating program
• Printable Maze Games - from 20x20 to 100x100
• Some thoughts on the uses of “Infinite Mazes”
• Topology and navigation
• Corn mazes in Illinois from the Chicagoland Vibary Network
• Corn Maze Directory for MD, DC, VA, & PA from BethesdaLiving
• http://www.geocities.com/tabtaco/mazeofdoom.html
• Emptystare: exploring the depths of the maze metaphor
• W.H. Matthews, Mazes and Labyrinths (1922) online version of W.H. Matthew's classic book
• Labyrinthos Jeff Saward's website
• Labyrinth Society
• Java code to create a "weave" maze and a circular maze
• cornmazedir.com Directory of hundreds of mazes in the USA and Canada}
• An online PDF maze generator which demonstrates the use of DFS, Prim and Kruskal algorithms