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?
Number of possible mazes
Moderators: Flumminator, Zomis
Number of possible mazes
Last edited by Zomis on Mon Apr 16, 2007 9:05 pm, edited 1 time in total.
> 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... :-(
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... :-(
Oh... yikes...
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...
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...