10
$\begingroup$

You are trying to design a maze solving robot, capable of solving "valid" mazes. A valid maze is an 8 by 8 checkerboard, surrounded by walls, where

  • Between each pair of orthogonally adjacent squares, there either is a wall, or isn't.
  • The northwest square is marked "start", the southeast square is marked "finish".
  • It is possible to get from "start" to "finish."

You program the robot by giving it a finite list of compass directions (N,S,E,W). It goes through the list, moving one square in the current direction unless doing so would make it hit a wall, in which case it stays put. Once it exhausts the list, it stops moving.

The goal is to design a program so that the robot, when placed on the "start" square of any valid maze, will always end up on the "finish" square when it has stopped moving.

Prove that there exists a program which accomplishes this.

This is a harder version of this puzzle. There, the robot was only required to visit the "finish" square on some point of its journey. Here, the robot must end on the finish square.

As far as I know, the solution requires some advanced mathematics, but I would still consider this a puzzle instead of a rote math problem.

$\endgroup$
  • $\begingroup$ To clarify: The difference to the other puzzle is, that here the 'arbitrary' list do commands must be such, that when the last command is executed, the robot is exactly at the finish-position. It may have visited the space before, but the robot still 'goes on'. Correct? $\endgroup$ – BmyGuest Jul 18 '15 at 7:32
  • $\begingroup$ @BmyGuest That is correct, though there is one other difference, namely, the "start" square is always at NW corner, and "finish" always at SE corner. Previously, "start" and "finish" could be anywhere. $\endgroup$ – Mike Earnest Jul 18 '15 at 18:16
  • $\begingroup$ The first thing that comes to my mind when I read this is the flood fill algorithm. It's one of the most popular algorithms in micromouse competitions ;) Sadly this won't work due to the restraints that you've put into this problem. $\endgroup$ – Allan Jul 19 '15 at 5:02
  • 2
    $\begingroup$ Quite a challenging problem. I look forward to see the solutions. $\endgroup$ – Sam Weaver Jul 19 '15 at 11:44
  • 1
    $\begingroup$ A tempting approach is, for general enough definition of "maze" define some way to combine two mazes into one maze such that any solution to the new maze is a simultaneous solution to the last two. (I'm not having much luck with it though - and it would give a construction probably running in double exponential time in $n^2$. I'm also feeling like investigating the monoid $$\langle f,f^*,g,g^* | ff^*f=f, f^*ff^*=f^*, gg^*g=g, g^*gg^*=g\rangle$$ might be good, where the $(f,f^*)$ pair represents moving north and south and $g$ and $g^*$ are east and west) $\endgroup$ – Milo Brandt Jul 25 '15 at 22:30
8
$\begingroup$

This solution is entirely due to zeb, and is paraphrased from this xkcd thread post.

Let $\epsilon>0$ be a small number. Take a particular maze, and imagine a robot who starts on the starting northwest square, then moves in a random direction once per minute according to the below probabilities:

     ^ e
     |
e <--+--> 1/2 - e
     |
     v 1/2 - e

Notice that the robot will tend to the southeast over time, but still work its way around obstacles.

The robot's position will be a Markov chain, whose states are the squares reachable from the start square. Using Markov chain theory, you can show the probability distribution of the robot's location will approach a unique stationary distribution as the number of steps increases. Let $p(i,j)$ be this limit distribution, where $(1,1)$ is the starting square, and $(8,8)$ is the finish.

An amazing fact is this: no matter how the maze is structured, the limit distribution $p(i,j)$ will be of the form $$p(i,j)=K\left(\frac{\frac12-\epsilon}{\epsilon}\right)^{i+j},$$where $K$ is a normalizing constant. This is quite surprising: no matter how snakey the maze is, over time, the probability this robot will be on a square only depends on which diagonal that square is on. To check this, you need only show that this distribution is a fixed point of the Markov process. Namely, show that if the robot has this distribution, then one minute later, it will still have this distribution. I omit the proof.

In this distribution, $p(8,8)$ has the largest probability, and every other probability is at most $\frac{\epsilon}{\frac12-\epsilon}\cdot p(8,8)\le 4\epsilon$, implying that $p(8,8)\ge 1-63\cdot 4\epsilon$. Thus, if we choose $\epsilon$ small enough, we can make $p(8,8)$ as close to $1$ as we want.

Finally, imagine if we set up every possible maze, choose a random program in this fashion of length $L$, then run the same program on a robot placed on the start square of each maze. By the previous discussion, we can choose $\epsilon$ small enough, and $L$ large enough, so that each robot has a less than $\frac1{2^{112}}$ probability of not ending on $(8,8)$. Since there are less than $2^{112}$ mazes, we have that $$ \begin{align} P(\text{all robots end on finish}) &=1-P(\text{at least one robot doesn't})\\ &\ge 1-\sum_{m=1}^{\text{# of mazes}} P(\text{robot on maze m doesn't end on finish})\\ &>1-2^{112}\cdot\frac1{2^{112}}=0 \\ \end{align} $$ Thus, there is a nonzero probability of a random program succeeding on all mazes, so there must exist a particular, determistic program which succeeds for all mazes.

$\endgroup$
  • 3
    $\begingroup$ It's interesting that this relies on the exit being in a corner. Is the problem still solvable if the exit square is some other fixed location in the maze? $\endgroup$ – xnor Jul 28 '15 at 21:52
  • 4
    $\begingroup$ @xnor If one maze has an exit only accessible from the left and another has an exit only accessible from the right, it's impossible for both to be solved at the same time. $\endgroup$ – f'' Jul 29 '15 at 0:04
1
$\begingroup$

I have a general idea but rather than try to explain it perfectly mathematically, I'll try to explain it in layman's terms:

First, come up with a list of every possible 8 by 8 map (a total of $N$ maps). Secondly, simulate every map's solution on each of all of the other map's squares. This will result in a total of $N*(N-1)*64$ "position changes".

An example of a position change if there were two possible maps: first run the simulation on the first map, then pretend the correct map was actually the second map and navigate to the finish line. The position change is the current position if the first map was the correct map all along.

The goal will be to arrange the $N$ map solutions in order so that the position changes for all future maps will allow the previous one to end on the southeast square. Due to symmetry, I think there should be an equal number of position changes going both directions, and also a generally even distribution for distance and direction of the position changes. (by direction, I mean the opposite change for a position change such as going down two instead of going up two). Therefore, there should logically be a sequence to arrange the attempt of the $N$ maps so that no matter which one is the correct solution, the robot will end up on the southeast square.

$\endgroup$

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.