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

Home > Algorithms
The Mazing (Posted on 2003-10-02) Difficulty: 3 of 5
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 <pre> 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 (2)
    Unsolved Problems
    Top Rated Problems
    This month's top
    Most Commented On

    Chatterbox:
    Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information