Number of possible mazes

Discussion around programming R'n'D, its source code and its tools.

Moderators: Zomis, Flumminator

Post Reply
User avatar
Zomis
Posts: 1501
Joined: Mon Jun 21, 2004 1:27 pm
Location: Sweden
Contact:

Number of possible mazes

Post by Zomis » Mon Apr 16, 2007 5:08 pm

Problem:
How many different combinations of mazes exits with x width and y height?

Conditions:
- Each maze must have one solution only
- Player starts at top left position
- Exit is at bottom right position
- No loops
- No isolations

Examples:
x=2 and y=2 equals 2 combinations:
(The style with a wall in the center is just to visualize the mazes better, so they don't count as real "spots". Therefore, x=2 and y=2 in the below maze)



Or




x=3 and y=2 equals 8 (or have I missed some?) combinations:



Or



Or



Or



Or



Or



Or



Or




So, how many maze combinations can be made with x width and y height?
Last edited by Zomis on Mon Apr 16, 2007 9:05 pm, edited 1 time in total.

User avatar
Holger
Site Admin
Posts: 2977
Joined: Fri Jun 18, 2004 4:13 pm
Location: Germany
Contact:

Post by Holger » Mon Apr 16, 2007 6:59 pm

> So, how many maze combinations can be made with x width and y height?

My first thought on this was that it is NP-complete, thinking of possible transformations into the "traveling salesman problem". Then I thought that these X x Y mazes may be split into smaller mazes which are subsets of the larger X x Y maze, but I think this won't work at all.

BTW: Somebody who writes a little program or algorithm that can answer Zomis' question and that can be implemented on a normal (non-quantum) computer can win $1,000,000 (only if it's really NP-complete, of course):

http://en.wikipedia.org/wiki/Complexity ... s_P_and_NP

Oh, well, my last lectures on theoretical computer science date back more than ten years, so my conclusions may well be all nonsense... :-(

User avatar
Zomis
Posts: 1501
Joined: Mon Jun 21, 2004 1:27 pm
Location: Sweden
Contact:

Post by Zomis » Tue Apr 17, 2007 9:50 am

Oh... yikes... :shock:

Just thinking, maybe it's like this:
a=(x-1)*(y-1)
Result (the number of possible mazes) = (4^(a-1))*2
x=2 y=2 --> a=1 --> Result = (4^(1-1))*2 = (4^0)*2 = 1 * 2 = 2
x=3 y=2 --> a=2 --> Resut = (4^(2-1))*2 = (4^1)*2 = 4 * 2 = 8

Explanation of this theory: The bottom left "center wall" can only have two possibilities, either it's a wall to the left or a wall to the bottom. Because the exit needs to be in the lower right and you can't fly over the exit.
Each other "center wall" can have 4 possible combinations, left-right-up-down.
"center wall" = a position on the map where x%2=1 and y%2=1 if the map ranges from 0..x-1 and 0..y-1, that is - all positions where there's always placed normal wall on the level sketches.

I wonder if it can really be so simple...

User avatar
Jannik
Posts: 135
Joined: Fri Jan 27, 2006 2:55 pm
Location: Germany

Post by Jannik » Tue Apr 17, 2007 10:21 am

Maybe you should replace the center walls with to make it more obvious that these ones are no valid solution:









and you should keep the even positions (next to the center walls) free, because these lines are just for visualization, so it would look like this:





representing this 3x2 maze:



Post Reply