A maze is a complex 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 has an actual 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.

Maze construction

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. Indoors, Mirror Mazes are another form of maze, where many of the apparent pathways are imaginary routes seen through multiple reflections in mirrors. Another 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, called The Garden of Forking Paths, that was a literary maze. Various maze generation algorithms exist for building mazes, either by hand or by computer.

Generating mazes

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

Stack-based approach

The stack-based approach is one of the simplest ways 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 four 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 mazes that are harder to solve.