18
$\begingroup$

Archie the archeologist has discovered an Egyptian temple, and plans to send in a robot to explore it. He uncovered the ancient engineers' papyruses which explain almost everything about the temple's layout. However, the engineers left out one crucial detail to stymie the efforts of thieves: the details of the maze room.

Here is all the papyrus said about the maze room:

  1. It is a $20$ meter by $20$ meter square, whose walls are aligned with the compass directions.
  2. The floor is colored like a $20\times 20$ checkerboard.
  3. Between each adjacent square, there either is a wall, or isn't.
  4. One square is the "start" square: the only entrance to the maze involves being dropped onto this square from a trap door
  5. Another square is the "finish" square: once you step on it, you immediately fall through a trap door to the throne room
  6. It is possible to get from start to finish

To program the robot, you give it a finite list of compass directions, either North, South, East or West. The robot then goes down the list, moving one meter in the current direction unless doing so would make it hit a wall, in which case it doesn't move.

Can Archie program the robot so that, starting from the start square, it will be guaranteed to eventually reach the finish square?

A note: you do not need to explicitly describe the program, only convince Archie whether this task is possible. The grad student will take care of creating/writing the actual program.

$\endgroup$
  • $\begingroup$ @JLee Recursion, for loops, conditionals, GOTO commands or anything like that are NOT allowed. Only a list of directions, which the robot will follow if able $\endgroup$ – Mike Earnest Jul 16 '15 at 3:25
  • 1
    $\begingroup$ @Bob The robot doesn't do any simulation. The grad student does the mentioned simulation when writing the program. This is just a mental tool the programmer is using to concoct the list of directions, which will guide the unintelligent robot through every possible maze without it having to think $\endgroup$ – Mike Earnest Jul 16 '15 at 16:20
  • 2
    $\begingroup$ Here's a hard variant (possibly too hard for this site?) You know that the finish square is the south-west corner of the maze. There's no trap door: instead, you must guarantee that at the end of the list of directions, the robot is standing on the finish square. Surprisingly, this is possible. $\endgroup$ – Lopsy Jul 16 '15 at 16:31
  • 1
    $\begingroup$ @Lopsy: For a general maze, with no restrictions on where the common exit square is placed, it's a simple matter to come up with even e.g. a pair of $3\times 3$ mazes that can't be synchronized. However, your "south-west corner" exit stipulation is curious. I quickly proved to myself that one can synchronize all legal $2\times 2$ mazes with this restriction. After a modest bit of experimentation, I was also unable to find any subset of legal $3\times 3$ mazes that couldn't be synchronized. It may be that a synchronizing word always exists subject to your exit condition. I just don't know. $\endgroup$ – COTO Jul 17 '15 at 16:40
  • 2
    $\begingroup$ FYI, this question has spawned another, which has an answer for the 3x3 grid in 91 moves: codegolf.stackexchange.com/q/53310/20198 $\endgroup$ – Nathan Merrill Jul 17 '15 at 22:29
28
$\begingroup$

Sure you can. There's finitely many possible mazes, so solve each one in sequence. To solve a maze, imagine you're in that maze. Figure out where you are in the maze by simulating starting on the start space and following the instructions corresponding to the sequence of steps you've taken so far. Then, make the moves that would take you from there to the exit.


Algorithm

  • Generate the ordered set of all potential legal mazes with all potential entry and exit squares. Call this set $M$.

  • Let the total list of moves executed up to but not including step $n$ be $H_n$. Let the list of moves executed during step $n$ be $h_n$.

  • For each model $\mathfrak{m} \in M$:

    • Assume $\mathfrak{m}$.
    • Compute the robot's presumptive location subject to executing $H_n$.
    • Compute $h_n$ such that the robot reaches the presumptive exit.
    • Execute $h_n$.
    • Append $h_n$ to $H_n$.

I had tried a different solution using synchronizing words to get to a fixed position in a given maze, but wasn't able to guarantee the DFA associated with the maze meets the conditions that guarantee one, like those in this result.

$\endgroup$
  • 3
    $\begingroup$ I wonder if there's a way to do this in polynomially many steps. $\endgroup$ – xnor Jul 16 '15 at 3:55
  • 4
    $\begingroup$ Figure out where you are in the maze by simulating making all the moves you've taken so far from the beginning. What exactly do you mean by that and how does this give you an idea of where you are? If I understood the puzzle correctly, the robot does not know the difference between doing and attempting a move (but not moving). So after any amount of steps, it could be anywhere and wouldn't be the wiser, wouldn't it? $\endgroup$ – BmyGuest Jul 16 '15 at 6:49
  • 1
    $\begingroup$ @BmyGuest I believe the intention is 'assume you are in the next maze on the list, then calculate your current position based on the moves made so far' $\endgroup$ – frodoskywalker Jul 16 '15 at 8:11
  • 5
    $\begingroup$ @BMYGuest you don't need to return to your initial position. You maintain a list of all the moves you have made. Then you select a maze that you assume you are in. Then you look at you model of that maze to see where you would be after making all the moves in the list. This puts tells you where you are in the maze if you have made the correct guess about the maze layout. You then find the path from your assumed location to the end, and follow it, adding the moves you make to your list. If you reach the end you are done, otherwise you move on the the next maze. $\endgroup$ – Taemyr Jul 16 '15 at 9:56
  • 2
    $\begingroup$ @xnor A refinement: When conputing the presumtive location see if the path intersects the presumtive exit. If it does then skip the current guess. $\endgroup$ – Taemyr Jul 16 '15 at 10:14
6
$\begingroup$

Randomness will be our friend.

It is known that a random walk will eventually get you out of any maze. See Random mouse algorithm.

We will provide a long enough list of random directions:

West, East, East, North, West, South, South, North, East, North, ...

The only problem is that the list has to be finite in this problem so the probability of getting out of the maze will not be 100% but will depend on the length of the list. The longest the list, the higher the probability will get (but a formula that connects length of list and probability is much harder to find).

$\endgroup$
  • 3
    $\begingroup$ Since there is only a finite set of initial conditions, you can compute how many of the random steps are needed to solve each initial condition. Taking the maximum of all these numbers will tell you how long the list needs to be. But I am thinking this will be less efficient than xnor's accepted solution. $\endgroup$ – kasperd Jul 16 '15 at 10:23
  • $\begingroup$ @kasperd For any initial condition any finite length of random steps will have a non-zero probability of not reaching the end. $\endgroup$ – Taemyr Jul 16 '15 at 10:54
  • $\begingroup$ @Taemyr Only if you assume the random choices are made after the length of the sequence has been decided. But that is not the case with the method I sketched, because it computes the length of the sequence based on the random choices being made. $\endgroup$ – kasperd Jul 16 '15 at 11:02
  • $\begingroup$ @Taemyr True. And a non-zero probability of reaching the end. With a long enough sequence, the probability will be high. $\endgroup$ – ypercubeᵀᴹ Jul 16 '15 at 11:19
  • 1
    $\begingroup$ @kasperd I have no idea what you are talking about. ("to perform what calculation")? Ah, ok, I think I understand what your point is. Create a (long enough) random list of directions, then check it against each configuration. If it solves all of them good. If it doesn't solve some them, extend the list and check again (until you have a long enough list that solves all.) Right? $\endgroup$ – ypercubeᵀᴹ Jul 17 '15 at 9:21
2
$\begingroup$

I'm gonna say

No, it's not possible.

Because

If you could be dropped back at the starting square after each failed attempt, then it would be easy. Simply go through the huge list of all possible moves (paths), one at a time.

However,

At first it seems that you could achieve this by just concatenating all of the individual "possible move" lists, each followed by its opposite, in order to get you back to the starting square, but the opposite move list does not necessarily lead you back to the starting square.

Therefore,

there is no way to be sure that you are back at the start square, and so it becomes impossible to iterate through the master list of moves.

Finally,

I hope that someone else figures out a way to overcome this seemingly impossible task, so that I may read it and learn something!

$\endgroup$
  • 3
    $\begingroup$ See xnor's answer; it is certainly possible (in principle) to create a list of moves which would move you through any maze to the end. This list would, however, be ridiculously long. $\endgroup$ – frodoskywalker Jul 16 '15 at 8:08
  • 1
    $\begingroup$ @JLee The point you are missing is that it's not really a problem if you guess wrong about where you are in the maze, if you already have guessed wrong about the layout of the maze. $\endgroup$ – Taemyr Jul 16 '15 at 10:21
  • 1
    $\begingroup$ @frodoskywalker xnor is no doubt brilliant, but most of his answers sound like Greek to me, and my eyes quickly glaze over, and this one is no exception. He reminds me of many of the college professors I had- super smart, but without the ability to put it into terms that less smart people (me) can understand. A small example or two (say, with a 4x4 maze?) would work wonders for my brain, but theoretical answers never provide those. $\endgroup$ – JLee Jul 16 '15 at 13:56
  • 2
    $\begingroup$ A 4x4 maze has approximately 4 billion arrangements, not excluding invalid (blocked) mazes. The solution would have to give a route for each (group of) arrangements. Maybe I'll try 3x3. That only has 300,000 arrangements... $\endgroup$ – frodoskywalker Jul 16 '15 at 14:49
  • 1
    $\begingroup$ 3x3 has 12 places where a wall can be placed so we have 2^12 configurations. Multiply this by 8 (or 9?) places where the robot can be placed and we have no more than 8 * 2^12 = 32768 different mazes+starting positions. For 4x4 it would be 15 * 2^24 = 251658240. For 20x20 it's around 2.4e+231 $\endgroup$ – ypercubeᵀᴹ Jul 16 '15 at 16:48
2
$\begingroup$

You first assume the walls are placed in a certain way. Then you start making assumptions about where you are and make sure the robot can travel through all the squares based on these assumptions. If you can't reach the end on the very first try (after this list of moves), you assume you were on a different square from what you chose at first and calculate your current "starting" pos based on that. After every failed attempt, you assume you were on a different square at the very beginning and calculate your new starting position based on that. If this scenario (assumed combination of walls, not the starting position) never succeeds, start anew in another scenario. Eventually the robot will succeed.

$\endgroup$
-6
$\begingroup$

Actually, there is a theory that if you always keep on the left side of the wall of a maze, you will eventually find the exit.

So try writing an algorithm that will keep your robot on the left side of the wall of a maze (or on the right side, the important thing is to keep moving on the same side of a wall).

You can find more details here: https://en.wikipedia.org/wiki/Maze_solving_algorithm

EDIT:

The algorithm that I previously posted, was indeed wrong as BmyGuest suggested.

$\endgroup$
  • 6
    $\begingroup$ You can not do an "algorithm", just a (very long) list of directions. Oh, and I think the theory only works for labyrinths without loops. Just imaging a loop and you're dropped onto it. You can go "left" and in circles forever... $\endgroup$ – BmyGuest Jul 16 '15 at 10:29
  • 1
    $\begingroup$ @BmyGuest That's not the chief problem, there are refinements to handle those cases. The problem is that in this case your algorithm needs to work without any feedback from the labyrinth. Meaning it's imposible to know if you have a wall on your left or not. $\endgroup$ – Taemyr Jul 16 '15 at 10:56
  • 1
    $\begingroup$ @Taemyr I know. That was my first sentence. (The second was an additional comment.) $\endgroup$ – BmyGuest Jul 16 '15 at 10:57
  • $\begingroup$ Also note that this only works for mazes without loops or islands. If the maze consists of no walls except the outside wall, and the target square is in the middle nowhere near a wall, then following the wall will do no good. $\endgroup$ – Adam Davis Jul 16 '15 at 15:38
  • $\begingroup$ (-1) This answer should be deleted. It just requires for the page to load up more (and unnecessary) matter, increasing the potential of lag. $\endgroup$ – Feeds Jul 31 '18 at 2:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.