perplexus.info :: Algorithms : The Mazing

The Mazing (Posted on 2003-10-02)

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?

Submitted by levik

Rating: 3.3333 (3 votes)

Solution: (Hide)

The maximum is (X-1) × (Y-1).
This means only one wall can be added to a 2×2 maze, 2 walls in a 3×2, 4 in 3×3, etc.
This is because the number of walls that can be added is exactly equal to the number of 'internal' points to the rectangle, as Charlie explains here.
Charlie also gave a program in BASIC that runs this algorithm, randomly picking walls and placing them to fill in a maze; that can be found here.

Comments: ( You must be logged in to post comments.)

Subject	Author	Date
Going in Circles	Brian Smith	2003-10-03 09:29:32
why didn't my <pre> work?	Charlie	2003-10-02 22:25:40
solution	Charlie	2003-10-02 22:16:07
For starters	Charlie	2003-10-02 15:45:16

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info