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.)
 For starters | Comment 1 of 4
As each new wall must go to a previously isolated point (vertex), and there are (x-1)(y-1) such isolated vertices, the maximum number of walls that can be so placed is (x-1)(y-1).

At each stage, when less than this many have been placed, at least some must be adjacent to points that are already the endpoints of an existing wall, so those are eligible for building a new wall. This continues until all (x-1)(y-1) are no longer isolated, so there's no way that this maximum will be unreachable.
 Posted by Charlie on 2003-10-02 15:45:16

 Search: Search body:
Forums (0)