FollowingThe following is a simple and detailedsimplified explanation of xnor's answer.
Let's say that there are a total of only 2 possible maze configurations. Let's also assume that we are given howthe initial orientation of the robot is oriented at the beginning known. So, forFor example, in the 3*3 case
1 2 3
4 5 6:
7 8 9
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(i.e. it is facing 4).
Let's call the 2 configurations , configuration 1$C_1$ and configuration 2$C_2$. Let's say that the robot was dropped with a sequence, sequence A$S_1$. Sequence A$S_1$ was written to make sure that if the maze is in configuration 1$C_1$, then the robot wouldwould have visited each and every square at least onceonce.
Now, if the maze was indeed in configuration 1$C_1$, we would have visited the final square and we would be done. But, if it was in configuration 2$C_2$ instead then it is possible that by the end of sequence A$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 sequence A$S_1$.
How do we remedy this ? The remedy is to drop the robot with sequence A+B instead of just Aadditional steps which are added after $S_1$.
This is how A+B helps. If after sequence A has finished and the robot has still not visited the final square then this means that the robot was in configuration 2 all along. Since we now know for sure that the robot has been in configuration 2 all along, we also very well know which square and in what orientation the robot is in, after sequence A has ended. Sequence B would now get executed and will make sure that the robot has visited each and every square by the time sequence B ends.The additional steps are generated as follows:
- Assume the maze is in $C_2$.
- Simulate what would happen if the robot followed $S_1$.
- Append additional steps after $S_1$ such that the robot visits every square in $C_2$.
- For brevity, denote this new sequence as $S_2$ (As in, $S_2$ is the entirety of $S_1$ plus any additional steps).
Thus, we have foundThis 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 sendprogram the robot now with the sequence A+B+C$S_2$. If the sequence A+Bfollowing $S_2$ fails to make the robot visit the final square, then it would mean that the robot was in a third maze configuration 3 all along ($C_3$). Since we know for aa fact that the robot was in configuration 3$C_3$ all along, we also would know which square and in which orientation the robot would be in after sequence A+Bperforming $S_2$. We can thus have agenerate another sequence C, $S_3$, by following the steps listed above, that will make the robot visit each and every square of configuration 3$C_3$, from the square the robot is in after the sequence A+B$S_2$ has ended. Hence solved.
This logic can be extended to the case where there are n$n$ possible maze configurations and where, which is true for the initialcase of a 20 by 20 grid. The orientation of the robot is known.
It is also easy to extend this logic to the case where there are nsimply adds more possible maze configurations and whereis therefore not an obstacle. Of course, the initial orientationvalue of $n$ in the robotoriginal question is not knownastronomically large and completely impractical to canvas, but the fact remains that the task is possible.
