mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2004-01-30, 13:26   #1
michael
 
Dec 2003
Belgium

5·13 Posts
Default 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
michael is offline   Reply With Quote
Old 2004-01-30, 20:03   #2
Starrise
 
Dec 2003

3 Posts
Default

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.
Starrise is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 04:25.

Mon Mar 8 04:25:11 UTC 2021 up 95 days, 36 mins, 0 users, load averages: 2.12, 2.22, 2.42

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.