6
$\begingroup$

A perfect maze (a maze with a unique solution) can be seen as a tree, where each node corresponds to a cell in the maze, and where edges corresponds to passages (missing walls) between cells. Two special nodes in the tree $s,e$ corresponds to the start-cell and the end-cell of the maze. An example is the following

A Maze, and the corresponding tree.

If we restrict mazes to be quadratic ($n \times n$) mazes like the one shown above, we can also look at mazes as spanning trees of the $n \times n$ grid graph. There are a number of observations one can make about such trees immediately, for example:

  1. The number of vertices is $n^2$
  2. No vertex has degree more than 4

Another observation, is that the number of vertices of degree 2 has to be large. One way to observe this, is to consider the distance classes of the graph. If all vertices had degree 3 or more, the number of vertices in the distance classes would grow exponentially, which the number of cells in each distance class does not.

My question, which is rather open ended, is if there exists some kind of classification of these trees.

Edit: Thanks to a comment by @joriki, I now know the number of such trees, as given in OEIS sequence A007341.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.