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.

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

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