2004-01-30, 13:26 | #1 |
Dec 2003
Belgium
5·13 Posts |
Maze
You might wonder where i am with my thoughts but i was thinking of the following.
For any solutable square maze (nxn) with starting position top left corner and goal bottom right corner, does there exist a finite string of commands R(ight), L(eft), U(p), D(own) that solutes every possible maze of that board size. Soluting means that it reaches the goal position at least 1 time. I think that R,D,R,L,D,R solutes every 2x2 maze are there shorter solutions? what is the shortest? for nxn? -michael |
2004-01-30, 20:03 | #2 |
Dec 2003
3 Posts |
I noticed that if loops are allowed within a maze, there are 4^((n-1)^2) mazes of size n^2.
The number of commands is a function of this somehow, but since there are 4^(2^2) = 4^4 = 256 3x3 mazes, it is rather difficult and time consuming to do it by hand. I'm going to try to make a program to enumerate the minimal commands required for each maze. If an n by n maze is thought of as a grid of n by n dots, and walls are lines connecting the dots, then you are only allowed to draw one line for each dot not on the edge. If you drew more than one line, you would either have redundancies, or you would close off a section of the maze. Therefore, there are (n-1)^2 possible lines in an n by n maze. Each line has 4 possible directions: Up, Right, Left and Down. By the counting principle, there are 4x4x4x...x4 ((n-1)^2 times) possible mazes, or 4^((n-1)^2) mazes. The actual minimal number of commands to solve any 2x2 maze is RDLDR or DRURD. I noticed that the general solution is palindromic (either way), which hopefully continues as n gets larger. I am not sure at all how the string would be constructed, but if we knew the 256 3x3 mazes it might go a long way toward solving this problem. The way you phrased this, there are no useful symmetries that I can see yet, and the number of possibile mazes increases exponentially with n, so this is a very difficult problem to solve. |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Try a real Maze | THILLIAR | Puzzles | 19 | 2004-10-10 14:52 |