26
$\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.

Improve this question
$\endgroup$
10
  • $\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
    Commented Jul 16, 2015 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
    Commented Jul 16, 2015 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
    Commented Jul 16, 2015 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
    Commented Jul 17, 2015 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
    Commented Jul 17, 2015 at 22:29

6 Answers 6

Reset to default
35
$\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.

Improve this answer
$\endgroup$
19
  • 3
    $\begingroup$ I wonder if there's a way to do this in polynomially many steps. $\endgroup$
    – xnor
    Commented Jul 16, 2015 at 3:55
  • 5
    $\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
    Commented Jul 16, 2015 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
    Commented Jul 16, 2015 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
    Commented Jul 16, 2015 at 9:56
  • 4
    $\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
    Commented Jul 16, 2015 at 10:14
11
$\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).

Improve this answer
$\endgroup$
8
  • 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
    Commented Jul 16, 2015 at 10:23
  • 1
    $\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
    Commented Jul 16, 2015 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
    Commented Jul 16, 2015 at 11:02
  • 2
    $\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ᵀᴹ
    Commented Jul 17, 2015 at 9:21
  • 1
    $\begingroup$ @ypercube Yes, that's the idea. $\endgroup$
    – kasperd
    Commented Jul 17, 2015 at 12:39
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!

Improve this answer
$\endgroup$
11
  • 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
    Commented Jul 16, 2015 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
    Commented Jul 16, 2015 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
    Commented Jul 16, 2015 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
    Commented Jul 16, 2015 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ᵀᴹ
    Commented Jul 16, 2015 at 16:48
1
$\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.

Improve this answer
$\endgroup$
1
$\begingroup$

The following is a simplified explanation of xnor's answer.

Let's say that there are only 2 possible maze configurations. Let's also assume that the initial orientation of the robot is known. For example, in the 3*3 case:

1 2 3 
4 5 6
7 8 9

we would have been told that the robot is dropped at position 7 and is facing north (i.e. it is facing 4).

Let's call the 2 configurations $C_1$ and $C_2$. Let's say that the robot was dropped with a sequence $S_1$. $S_1$ was written to make sure that if the maze is $C_1$, then the robot would have visited each and every square at least once.

Now, if the maze was indeed $C_1$, we would have visited the final square and we would be done. But if it was in $C_2$ instead then it is possible that by the end of $S_1$, not all the squares were visited and by extension, it is possible that we did not visit the final square by the end of $S_1$.

How do we remedy this? The remedy is to drop the robot with additional steps which are added after $S_1$.

The additional steps are generated as follows:

  1. Assume the maze is in $C_2$.
  2. Simulate what would happen if the robot followed $S_1$.
  3. Append additional steps after $S_1$ such that the robot visits every square in $C_2$.
  4. For brevity, denote this new sequence as $S_2$ (As in, $S_2$ is the entirety of $S_1$ plus any additional steps).

This sequence of moves is a solution for the case where the maze can only be in one of 2 possible configurations and where the orientation of the robot is known initially.

Let's now continue this logic to the case where there are 3 possible maze configurations and where the orientation of the robot is known to us initially. We will program the robot now with the sequence $S_2$. If following $S_2$ fails to make the robot visit the final square, then it would mean that the robot was in a third maze configuration all along ($C_3$). Since we know for a fact that the robot was in $C_3$ all along, we also would know which square and in which orientation the robot would be in after performing $S_2$. We can thus generate another sequence, $S_3$, by following the steps listed above, that will make the robot visit each and every square of $C_3$, from the square the robot is in after $S_2$ has ended.

This logic can be extended to the case where there are $n$ possible maze configurations, which is true for the case of a 20 by 20 grid. The orientation of the robot simply adds more possible configurations and is therefore not an obstacle. Of course, the value of $n$ in the original question is astronomically large and completely impractical to canvas, but the fact remains that the task is possible.

P.S.

The above puzzle reminds me of this puzzle : Why does this solution guarantee that the prince knocks on the right door to find the princess?

Improve this answer
$\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.

Improve this answer
$\endgroup$
5
  • 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
    Commented Jul 16, 2015 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
    Commented Jul 16, 2015 at 10:56
  • 1
    $\begingroup$ @Taemyr I know. That was my first sentence. (The second was an additional comment.) $\endgroup$
    – BmyGuest
    Commented Jul 16, 2015 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
    Commented Jul 16, 2015 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$
    – Mr Pie
    Commented Jul 31, 2018 at 2:31

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