Number of possible mazes

[Zomis]

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?

[Holger]

> 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... :-(

[Zomis]

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...

[Jannik]

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: