Math Is Fun Forum

fusilli_jerry89

Member

Registered: 2006-06-23

Posts: 86

Hard Maze Problem agh help!

An n by n maze is randomly generated with numbers from 1 to n. Fo example: a 5 by 5 maze might look like the following:

23125
55132
54214
13542
14341

In order to solve the maze, you have to start from one of the top numbers, and get to one of the bottom numbers in n-1 steps (4 in this case). (You can only move down, and diagonal downwards). In addition, you must visit each number from 1 to n once and only once. (You must visit 1,2,3,4,5 in the example above). For example, a solution in the example above might be 2,5,4,3,1 or 5,2,1,4,3.

What is the possibility of a maze with no solutions?

I know that in order to get the answer to this we have to take (1/n)^n² (probability for each maze) and multiply it by the total of number of mazes without solutions. I can see that we can add up all the mazes without a certain number (i.e. a maze with no 2's will yield no solutions), but how do I find out how many mazes there are with no solutions otherwise?

Thanks!

John E. Franklin

Member

Registered: 2005-08-29

Posts: 3,588

Re: Hard Maze Problem agh help!

Why not just stick with one number and go with it, it's more fun, and
get's the same answer probably.  Like follow the "1's" down a path.
Also, I think a larger matrix like a 8x8 and use only numbers from
1 to 3, so you have a chance of getting through it.

---

igloo myrtilles fourmis