mathematics - Controlling a robot blindfolded on a 9x9 grid

A robot is located somewhere inside a 9x9 grid shown below, but you don't know where it is. You can send commands to the robot to make it move one cell left, right, up or down. Shaded areas and edges of the grid are walls that cannot be traversed. If a robot hits a wall it stays in its current cell. Your task is to guide the robot to the target cell (shown as T). Once the robot reaches the target, the game will terminate immediately. What is the fewest number of commands you need to send to the robot to guarantee that it reaches the target cell?

This is my favourite puzzle that I have created. Good luck!

Answer

My first attempt was done by hand. It used 28 commands:

RRR UUU R DDD RR UUU RR LLL UUUUU RRD

but this was not optimal. I have now done a computer search to find optimal solutions.

It found 180 solutions of length

24 commands

No shorter solutions exist.

I'll illustrate the following solution:

LU LU LU UU RRR UU L DDD RRRRRUU

To see how it works, start with a robot on every available square, and send the commands. The robots should all reach the target square at some point.

o o o o x o o o o 
o o o o x o o t o 
o o o o x o o o o 
o o o o o o o o o 
x x x o o o x x x 
o o o o o o o o o 
o o o o x o o o o 

o o o o x o o o o 
o o o o x o o o o 

LU

o o o . x o o o . 
o o o . x o o t . 
o o o o x o o o . 
. . . o o . . . . 
x x x o o o x x x 

o o o . . o o o . 
o o o . x o o o . 
o o o . x o o o . 
. . . . x . . . . 

LU

o o . . x o o . . 
o o o . x o o t . 
. . o o x . . . . 

. . . o o . . . . 
x x x . o o x x x 
o o . . . o o . . 
o o . . x o o . . 
. . . . x . . . . 
. . . . x . . . . 

LU

o o . . x o . . . 

. o o . x . . t . 
. . o o x . . . . 
. . . o o . . . . 
x x x . o o x x x 
o . . . . o . . . 
. . . . x . . . . 
. . . . x . . . . 
. . . . x . . . . 

UU 


o o o o x o . . . 
. . . o x . . t . 
. . . . x o . . . 
. . . . o o . . . 
x x x . . . x x x 
o . . . . . . . . 
. . . . x . . . . 
. . . . x . . . . 
. . . . x . . . . 


RRR

. . . o x . . . o 
. . . o x . . t . 
. . . . x . . . o 
. . . . . . . o o 
x x x . . . x x x 
. . . o . . . . . 
. . . . x . . . . 

. . . . x . . . . 
. . . . x . . . . 

UU

. . . o x . . . o 
. . . . x . . t o 
. . . . x . . . . 
. . . o . . . . . 
x x x . . . x x x 

. . . . . . . . . 
. . . . x . . . . 
. . . . x . . . . 
. . . . x . . . . 

L 
. . o . x . . o . 
. . . . x . . t . 
. . . . x . . . . 
. . o . . . . . . 

x x x . . . x x x 
. . . . . . . . . 
. . . . x . . . . 
. . . . x . . . . 
. . . . x . . . . 

DDD

. . . . x . . . . 
. . . . x . . t . 

. . . . x . . . . 
. . o . . . . . . 
x x x . . . x x x 
. . . . . . . . . 
. . . . x . . . . 
. . . . x . . . . 
. . . . x . . . . 

RRRRRUU 

My computer program used a technique called iterative deepening. Essentially it first tried all command sequences of length 20, didn't find any solutions, then tried all of lenth 21, then length 22, etc. For each length it tried all sequences, essentially a depth first search, but backtracked as soon as a simple heuristic showed that the current position could not be done in the number of moves remaining.

The heuristic I used was simply to count how many U/D/L/R moves were needed for each remaining robot to get to the target, for each of the four move types take the maximum number of times it was used by any robot, and then add those four maxima together.