26

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.

Quark
  • 6,077
  • 1
  • 20
  • 46
Mike Earnest
  • 32,336
  • 6
  • 92
  • 237
  • @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 – Mike Earnest Jul 16 '15 at 03:25
  • It sounds like you are saying the robot is only given a list of compass directions to follow which it will follows (where possible) without question or deviation the list, but the accepted answer talks about simulating mazes and figuring out where you are in the maze. – Bob Jul 16 '15 at 16:14
  • 1
    @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 – Mike Earnest Jul 16 '15 at 16:20
  • The answer doesn't really make clear the distinction between what is taking place before entering the maze and what is happening whilst in the maze. – Bob Jul 16 '15 at 16:27
  • 2
    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. – Lopsy Jul 16 '15 at 16:31
  • @Lopsy: This is the synchronizing word technique xnor mentions in his solution. The upper bound on the word length needed to synchronize all possible $20\times 20$ mazes would probably cause the grad student tasked with writing the program to soil himself. – COTO Jul 16 '15 at 21:57
  • Why can't the robot have a camera and complete the maze like that? :/ – Conor O'Brien Jul 16 '15 at 22:14
  • @COTO: Do you know there's a synchronizing word? – Lopsy Jul 16 '15 at 22:53
  • 1
    @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. – COTO Jul 17 '15 at 16:40
  • 2
    FYI, this question has spawned another, which has an answer for the 3x3 grid in 91 moves: http://codegolf.stackexchange.com/q/53310/20198 – Nathan Merrill Jul 17 '15 at 22:29

6 Answers6

35

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.

xnor
  • 26,756
  • 4
  • 85
  • 144
  • 3
    I wonder if there's a way to do this in polynomially many steps. – xnor Jul 16 '15 at 03:55
  • I had thought that one could use a reset sequence to get to a fixed square of a given maze, but am not sure if it is guaranteed to have one. – xnor Jul 16 '15 at 04:10
  • 5
    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? – BmyGuest Jul 16 '15 at 06:49
  • @BmyGuest: I had the same concern, but it's just that the explanation is vague. I've added some exposition to clarify what I believe xnor means. – COTO Jul 16 '15 at 07:55
  • 1
    @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' – frodoskywalker Jul 16 '15 at 08:11
  • @Coto: I still don't see it work. The problem I have is, that even if I consider "all finite" possibilities of moves (simulated or done), I don't see that it is indeed possible to return to the "original position" with certainty if you don't know the initial position and actual maze and don't get feedback on successful moves and/or any known position. I, however, wonder if one can prove the answer wrong by assuming the list of "possible" mazes is just very small and showing that one situation leeds to a non-inversible situation. – BmyGuest Jul 16 '15 at 09:39
  • @frodoskywalker It is exactly this step which I doubt being possible in the general case. I don't see any proof that this is generally possible. – BmyGuest Jul 16 '15 at 09:41
  • 5
    @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. – Taemyr Jul 16 '15 at 09:56
  • @Taemyr THANKS! That was the missing part for me. Clear words for a non-mathematical brain ;c) I'm convinced now. – BmyGuest Jul 16 '15 at 09:58
  • 1
    @Taemyr very nicely explained – frodoskywalker Jul 16 '15 at 10:00
  • @BmyGuest To take an example in a 3x3 grid; Lets assume we start at 2,1 and need to go to 2,3. Lets further assume a simple maze, actually a corridor and the correct path from start to finish would be nenw. However our robot starts with guessing a maze in which the correct path is nn. He executes this, which moves him to 2,2 and collides him into the wall once. He then guesses a maze that with correct path wnne. This guess is also a corridor, except that there is a cul-de-sac in the middle so it's possible to move n from the start. ... – Taemyr Jul 16 '15 at 10:05
  • ... The robot then considers where he would be in this maze. It knows that it has attempted nn. If it's guess where correct it would have moved one step north and no further. The path the robot would need to take would be swnne, so the robot tries that. This does not take the robot to the end. It then makes the correct guess about the maze. It considers where it would be in the correct maze after the sequence of moves it has made nnswnne. It sees that in the model this would be n(n)s(w)n(n)e so it guesses that it needs to move nw to get to the end. It tries it and finishes. – Taemyr Jul 16 '15 at 10:08
  • 4
    @xnor A refinement: When conputing the presumtive location see if the path intersects the presumtive exit. If it does then skip the current guess. – Taemyr Jul 16 '15 at 10:14
  • @Taemyr Like that. You've just made an "incredibly long" list of commands into a "incredibly long minus tiny" list of commands ;c) – BmyGuest Jul 16 '15 at 10:32
  • @BmyGuest Depending on what you mean by "tiny" I am not so sure. I would be very surprised if my proposed refinement reduces the problem by less than half. If I where to guess I would expect the reduction to be about the size of the number of squares in the maze, so a reduction of 99.75%. Of course while O((2^n)/n) is better than O(2^n), both are bad enough that the difference is usually discounted. - This is reduction of the worst case or total length of the sequence, reduction of average length traversed can not be redyced by my proposal with more than 50%, and would probably only be 25%. – Taemyr Jul 16 '15 at 10:58
  • @Taemyr By "tiny" I referred to the O() situation as you've commented. Still I +1ed your comment on the refinement. – BmyGuest Jul 16 '15 at 10:59
  • Signed up to upvote this... – trichoplax is on Codidact now Jul 16 '15 at 23:15
  • @taemyr based on your refinement and ypercube’s answer: first do a trillion random moves, then start the algorithm with your refinement :-) of course taking the random moves into account in the simulation. – Kris Van Bael Dec 31 '22 at 23:38
  • Why would you assumme a possible end location? You could also make sure that you have been on every spot of the maze once (taking Taemyr's suggestion into an account). – The_spider Sep 22 '23 at 18:07
11

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).

ypercubeᵀᴹ
  • 247
  • 2
  • 11
  • 3
    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. – kasperd Jul 16 '15 at 10:23
  • 1
    @kasperd For any initial condition any finite length of random steps will have a non-zero probability of not reaching the end. – Taemyr Jul 16 '15 at 10:54
  • @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. – kasperd Jul 16 '15 at 11:02
  • @Taemyr True. And a non-zero probability of reaching the end. With a long enough sequence, the probability will be high. – ypercubeᵀᴹ Jul 16 '15 at 11:19
  • @kasperd you can't compute how many random steps will be needed. For all we know the first trillion trillion trillion moves can be North, South, North, South, ... which will not get you from many mazes ;) – ypercubeᵀᴹ Jul 16 '15 at 16:57
  • @ypercube You are making the same erroneous assumption as Taemyr did. I proposed to look at the actual random values and use that to perform the calculation. Each time that algorithm is used it will produce a finite sequence of steps, which is long enough. If you execute that algorithm again it will produce a different sequence which most likely will be of a different length, but each sequence in itself is long enough. – kasperd Jul 16 '15 at 19:28
  • 2
    @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? – ypercubeᵀᴹ Jul 17 '15 at 09:21
  • 1
    @ypercube Yes, that's the idea. – kasperd Jul 17 '15 at 12:39
2

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!

JLee
  • 18,202
  • 2
  • 55
  • 172
  • 3
    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. – frodoskywalker Jul 16 '15 at 08:08
  • 1
    @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. – Taemyr Jul 16 '15 at 10:21
  • 1
    @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. – JLee Jul 16 '15 at 13:56
  • @JLee that's a good point; intellectual brilliance is very different from brilliance at teaching. I'll see if I can produce an example, though even the 4x4 one might be too large; the 20x20 solution is enormous. – frodoskywalker Jul 16 '15 at 14:14
  • 2
    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... – frodoskywalker Jul 16 '15 at 14:49
  • @frodoskywalker I understand there are many possible mazes, and I understand that you could start anywhere in the maze, and that you don't have any way of telling where you are, even after making a move. So, there are 20x20-1= 399 different cells that can be the start square. So, for each of the trillions of trillions of possibilities, we can append to a huge list 399 solutions, 1 from each cell. So, my confusion is, how do we know what order to execute these in? Not knowing where we are in the maze is messing up my ability to work out how this list is guaranteed to find the solution. – JLee Jul 16 '15 at 14:59
  • 1
    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 – ypercubeᵀᴹ Jul 16 '15 at 16:48
  • @ypercube Yes, that's right. I think frodo might have been factoring in the outer wall of the room too, but your figure is accurate. Although, this info doesn't help me much with my main question. – JLee Jul 16 '15 at 16:51
  • And I forgot to factor the finishing square so my numbers are lower. For 3x3, it should be 9 * 8 * 2^12 = 294912 and for 4x4 around 4 billion. So @frodoskywalker was correct! – ypercubeᵀᴹ Jul 16 '15 at 17:21
  • @ypercube The walls of the finishing square (aka the room) are always there and cannot be removed. So, aren't your original figures more accurate? – JLee Jul 16 '15 at 17:26
  • 1
    xnor's answer can be understood from the initial paragraph, without needing to worry about the symbolic notation in the proof. (1) Start with a list of every possible maze, including the same layout with a different starting position as a different maze. (2) For the first maze, write down the moves that will take you from start to exit. (3) For the next maze, you know that starting point, but you also have the list you wrote down of what you already tried. That list tells you where you would be if this was the correct maze, so write down how to get from there to the exit. (4) Repeat for all – trichoplax is on Codidact now Jun 11 '16 at 12:02
1

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?

ApexPolenta
  • 2,690
  • 10
  • 31
Hemant Agarwal
  • 2,912
  • 14
  • 31
1

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.

Nautilus
  • 6,534
  • 10
  • 32
-6

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.

Community
  • 1
Dolhescu Stefan
  • 1
  • 1
  • 6
    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... – BmyGuest Jul 16 '15 at 10:29
  • 1
    @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. – Taemyr Jul 16 '15 at 10:56
  • 1
    @Taemyr I know. That was my first sentence. (The second was an additional comment.) – BmyGuest Jul 16 '15 at 10:57
  • 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. – Adam Davis Jul 16 '15 at 15:38
  • (-1) This answer should be deleted. It just requires for the page to load up more (and unnecessary) matter, increasing the potential of lag. – Mr Pie Jul 31 '18 at 02:31