Proper Mazes

I had always considered solving mazes with a pencil to be boring and pointless. However, programming a computer to generate mazes has been a rewarding pastime.

My first programming job was at Purdue. My boss was a mathematician. He would tell me interesting things in an off-handed way. Sometimes he would say things about mazes:

• In a proper maze, all squares are reachable but there is only one path from start to finish. This implies no loops. The network of paths must be a tree.

• You solve any proper maze (and many improper mazes) by following the left hand wall. (A depth-first traversal of the tree.)

• You can generate a proper maze by knocking down walls, always from a visited square to a non-visited square, extending a path.

This is a sound algorithm because it won't get stuck: as long as there are unvisited squares, there will be at least one unvisited square next to a visited square.

I have written the knocking down walls algorithm in several languages. I found that the visual effect was highly influenced by how one chose to knock down walls.

My most interesting maze generator/solver was on the Imlac PDS-1 where walls were represented as bits in a display processor program. While the central processor ran, the display processor visualized the progress of the generator and then solver.

My most successful mazes, called Pebeliths, were both aesthetically pleasing and had interesting solutions. This came from my biasing of the random wall selection to look right at the top of the maze, down on the right side, left on the bottom, and back up on the left side. The result was swirly mazes with long solutions that went round and round the center.