A maze is to be constructed on an X by Y grid of squares by creating "walls" between them.

The process starts with an enclosed rectangle X squares wide and Y squares tall, with walls on the outside edges of the outermost squares. Here's an example of a (6 x 2) rectangle:

       +--+--+--+--+--+--+
       |                 |
       +  +  +  +  +  +  +
       |                 |
       +--+--+--+--+--+--+

We then build additional walls in the following manner:

Pick an existing wall (A) at random.

Pick (also at random) a potential non-existent wall (W) that will be adjacent to (A). (W) must be a valid wall - it must be inside the maze.

Ensure that (W) will not connect wall (A) to any other wall - that is that there is no existing wall (B) that is is distinct from (A) and non-adjacent to (A) but that would be adjacent to (W).

Place wall (W) only if the above condition is satisfied.

By following in these steps, what is the theoretical maximum number of walls that can be placed? Is there a situation where walls can be placed in such a way that achieving this maximum will no longer be possible?

As I see it, the algorithm will keep adding walls to the maze until EVERY loop is broken. The algorithm will also never cut the maze into two sub-mazes. There are a total of x*(y-1)+y*(x-1)=2*x*y-x-y places to construct walls. Since there are x*y cells, there must be at least x*y-1 passages between cells for all the cells to be connected (with x*y-x-y+1 walls erected). If there are more than x*y-1 passages, then somewhere in the maze there is a loop, which means a wall can be added. So there must be exactly x*y-1 passages and exactly x*y-x-y+1 walls when the algorithm terminates.

Posted by Brian Smith on 2003-10-03 09:29:32