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.)
 why didn't my
work?  | 			Comment 3 of 4         |
I'll try again:
```
Height of grid:21

Width of grid:15

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |

+  +  +  +  +  +  +  +  +  +  +  +  +  +  +  +

|     |  |        |     |     |     |  |     |

+--+  +  +--+  +--+--+  +--+  +  +--+  +  +--+

|     |  |        |     |     |  |  |        |

+  +  +  +--+  +--+  +--+--+  +  +  +  +--+--+

|  |     |     |  |  |  |     |  |        |  |

+--+--+  +--+  +  +  +  +--+  +  +  +--+--+  +

|                 |  |     |     |           |

+--+--+  +  +--+  +  +--+  +  +--+  +--+--+--+

|        |  |        |                       |

+--+--+--+--+--+  +--+--+--+  +--+--+  +--+--+

|     |           |  |     |        |        |

+--+  +--+--+--+  +  +  +--+  +--+--+--+--+--+

|     |     |                                |

+--+  +--+  +--+--+  +--+--+  +--+--+--+  +--+

|     |  |  |     |     |  |           |     |

+  +  +  +  +--+  +  +--+  +--+--+--+--+--+--+

|  |                       |        |        |

+--+--+--+--+--+--+--+--+  +  +--+--+  +--+--+

|     |                          |        |  |

+--+  +--+--+--+--+  +--+--+--+--+  +  +--+  +

|                                   |        |

+--+--+--+--+--+  +--+--+  +--+--+--+--+--+--+

|     |                 |     |     |     |  |

+--+  +--+  +  +  +--+  +--+--+  +--+  +--+  +

|           |  |     |        |        |     |

+--+--+--+--+  +  +--+--+--+  +  +--+--+  +--+

|              |     |     |           |     |

+--+--+--+  +--+  +  +  +  +  +  +  +--+  +--+

|     |     |     |     |  |  |  |           |

+--+  +--+  +  +  +  +  +--+--+  +--+--+  +  +

|           |  |  |  |     |           |  |  |

+--+--+--+  +--+  +--+  +  +  +  +--+--+--+  +

|              |  |     |  |  |           |  |

+  +--+--+--+--+--+  +--+  +  +--+--+  +--+--+

|  |                    |  |  |              |

+--+--+--+  +  +  +  +  +  +  +  +--+--+  +  +

|  |        |  |  |  |  |  |  |        |  |  |

+  +  +  +--+  +  +  +  +  +  +  +  +  +--+--+

|     |     |  |  |  |  |  |  |  |  |        |

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

Enter for more; Esc to end.

```

-------------
Hopefully this maze will appear correctly above, given the appropriate pre and /pre value within angle brackets.
 Posted by Charlie on 2003-10-02 22:25:40
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:
Copyright © 2002 - 2020 by Animus Pactum Consulting. All rights reserved. Privacy Information