Maze

michael · 2004-01-30, 13:26

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

Starrise · 2004-01-30, 20:03

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.

2004-01-30, 13:26	#1
michael 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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Try a real Maze	THILLIAR	Puzzles	19	2004-10-10 14:52

2004-01-30, 20:03	#2
Starrise 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.