# Finding the hardest 5x5 grid for a blindfolded robot to solve

This puzzle is based on the framework described here: Controlling a robot blindfolded on a 9x9 grid

Here is a quick summary. A robot is located somewhere on a grid, but you cannot see it. You can send commands to the robot to make it move one cell left, right, up or down. Some cells can be walls. If a robot hits a wall it stays in its current cell. Your task is to guide the robot to the target cell T. Once the robot reaches the target, the game will terminate immediately.

Can you find a 5x5 grid that will require the most commands to be solved from any starting position of the robot? The grid must include the terminal cell T, which must be reachable from any empty cell. Some of the grid's cells can be walls. Good luck!

P.S. My previous puzzle on this topic received some downvotes, which I still don't understand. Hopefully people will enjoy this puzzle more.

• Can a wall be placed BETWEEN cells? Commented Dec 5, 2019 at 8:58
• No. Walls can only replace cells. Commented Dec 5, 2019 at 9:00
• Does the robot operator know the gird layout? I assume so from the answers, but if not, it becomes a much harder problem to solve. Commented Dec 5, 2019 at 18:14
• Yes the robot operator knows the grid layout. See the linked question. Commented Dec 5, 2019 at 21:33

This grid


_X___
_X_X_
_X_XT
_X_XX
_____


requires 18 steps:

DDDDRRRRLLUUUURRDD

Explanation

The terminal e3* cell can be reached only via c1. To reach c1 from any given cell, one has to use DDDD (to move onto the 1st rank) and RRRRLL (or LLLLRR, to fix on the c-file). Now use UUUURRDD to move from c1 via c5 and e5 to e3.
*cells are designated as in chess (i.e. a1=lower left corner, a5=upper left corner etc.)

• I can do it with DDDDRRULLUUUURRDD, which is 17 steps. This is still the best solution so far. Commented Dec 5, 2019 at 9:03
• @DmitryKamenetsky I may be wrong, but your 17-step solution won't work if the robot initially was on b1 (2nd cell from the left in the bottom row, i.e. under the left 4-cell wall). Commented Dec 5, 2019 at 10:01
• Oops you are right Commented Dec 5, 2019 at 11:51

18:

 .X...
.X.X.
...X.
.XXX.
...XT

Worst case C5: LL UUUU DD RR UU LL DDDD. It's 8 from C3, and at least LL UU RR and DD from C5.

Intuitively, it seems like

a spiral, like so:


___xT
_x_x_
_x_x_
_xxx_
_____

However, I'd be hard pressed to come up with an actual explanation, beyond the fact that you must go exactly UULLDDDDRRRRUUUU to reach the exit from the worst possible position (the center).

• Good start, but you can find harder grids. Commented Dec 5, 2019 at 4:08
• UULLDDDDRRRRUUUU will reach the exit from any starting location. Commented Dec 5, 2019 at 21:02

I thought about something here :


_ _ _ _ _
_ X _ _ _
_ T X _ _
_ X _ _ _
_ _ _ _ _

There is almost half a zone where the robot can move freely, and whenever it reaches the top left column, it can only go up or down (unless the robot turns right at the rigt moment). It might be improved by filling the blank space on the right, but i thought the more empty spaces you have, the more moves you can waste on. Ultimately it would not take long if you take the perfect path, but finding the perfect path blindly with that configuration is very unlikely.

There is another answer I thought of first, and I wanted to share.


_ _ _ _ _
_ _ _ _ _
_ T _ _ _
_ _ _ _ _
_ _ _ _ _

Same mentality as the last one, but the targer is not protected to random guesses

And last but not least, the ultimate move :

 _ _ _ _ _
_ _ X _ _
_ X T X _
_ _ X _ _
_ _ _ _ _

It was never said that the target has to be reachable ! From any point, it will take approximatey ∞ moves to get to the target. Good luck, robot. Missread the question, this answer is not valid.

• Target must be reachable from any empty cell. Commented Dec 5, 2019 at 8:50
• which must be reachable from any empty cell My bad, I accidentally skipped this part. The last answer wasn't a serious attempt anyway. Commented Dec 5, 2019 at 8:53
• How many steps would your first example require? Commented Dec 5, 2019 at 9:01
• @DmitryKamenetsky That first example takes 14 steps: ULUR UUU LLL DDR. Commented Dec 5, 2019 at 9:53
• The second example can be solved from any starting location with UUUU LLLL DR Commented Dec 5, 2019 at 21:03

I believe I found a grid that requires 19 steps to solve, but I cannot prove it. The grid is

..X..
.XTX.
.....
.X.X.
..X..


The steps I found are

LDDDDRDDDDUULLUURRU

Also I have found another grid, which may require even more steps to solve, but I am not sure how many exactly:

XT..X
.X.X.
.....
.X.X.
X...X


It would be great if someone could confirm/verify my answers.

Edit: these grids are not that hard after all. See comments below.

• My computer found the 17 move LUUUDRDRDDDRUULLU for the first one the 14 move UUUDRRRLULUUUL for the second. Commented Dec 8, 2019 at 12:42
• Jaap thank you so much! Looks like these grids are not hard after all. What would happen if you generated random grids (and target cell) and then check them with your program? This would be a good way to find hard grids. Commented Dec 8, 2019 at 13:16
• I tried that (i.e. adding a random wall square, see if the solution is longer, keep the wall only if it is; and repeat) but it almost always only reached 15 or 16 moves, and very rarely maxed out at 17 moves. Commented Dec 8, 2019 at 13:54