All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 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?

•  See The Solution Submitted by levik Rating: 3.3333 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Going in Circles Comment 4 of 4 |
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

 Search: Search body:
Forums (0)