algorithm - Maze Solving Robot

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.

Answer

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.