A maze, also known as a labyrinth, is a set of passages (with impermeable walls). The goal of the maze is to start at one given point and find a path through the passages that reaches a second given point.
The illustration pairs a perfect maze with its passage graph. For a finite collection of cells, form a graph
with one vertex for each cell and an edge
for each possible passage between neighboring cells. A perfect maze connects
all cells and has a uniquegraph
path between every pair of cells. Its open passages therefore form a spanning
tree of the cell-adjacency graph (Buck 2011). A perfect
maze with cells has open passages. Choosing different spanning
trees gives different perfect mazes.
The back of a clay accounting tablet from Pylos, Greece is illustrated above (Wolfram 2002, p. 43).
Legend has it that it was the plan for the labyrinth housing the minotaur in the
palace at Knossos, Crete, and that it was designed by Daedalus. It is also said that
it was a logo for the city of Troy-or perhaps the plan of some of its walls (Wolfram
2002, p. 873).
The above pattern (in either its square or rounded form) has appeared with remarkably little variation in a large variety of places all over the world-from Cretan coins, to graffiti at Pompeii, to the floor of the cathedral at Chartres, to carvings in Peru, to logos for aboriginal tribes. For probably three thousand years, it has been the single most common design used for mazes (Wolfram 2003, p. 873).
cells has 
open passages. Choosing different spanning
trees gives different perfect mazes.
