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:
- It is a $20$ meter by $20$ meter square, whose walls are aligned with the compass directions.
- The floor is colored like a $20\times 20$ checkerboard.
- Between each adjacent square, there either is a wall, or isn't.
- One square is the "start" square: the only entrance to the maze involves being dropped onto this square from a trap door
- Another square is the "finish" square: once you step on it, you immediately fall through a trap door to the throne room
- 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.