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

Question

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.

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. — Trenin, Dec 05 '19 at 18:14
Yes the robot operator knows the grid layout. See the linked question. — Dmitry Kamenetsky, Dec 05 '19 at 21:33

score 6 · Accepted Answer · edited Dec 05 '19 at 12:55

6

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.)

edited Dec 05 '19 at 12:55

Peter LeFanu Lumsdaine

1,901
16
14

answered Dec 05 '19 at 07:52

trolley813

11,282
2
25
57

I can do it with DDDDRRULLUUUURRDD, which is 17 steps. This is still the best solution so far. – Dmitry Kamenetsky Dec 05 '19 at 09:03
4

@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). – trolley813 Dec 05 '19 at 10:01
2

Oops you are right – Dmitry Kamenetsky Dec 05 '19 at 11:51

JMP · Answer 2 · 2019-12-05T10:16:56.023

5

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.

edited Dec 05 '19 at 10:16

answered Dec 05 '19 at 10:00

JMP

35,612
7
78
151

score 3 · Answer 3 · answered Dec 05 '19 at 03:59

3

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).

answered Dec 05 '19 at 03:59

Avi

10,446
1
20
75

2

Good start, but you can find harder grids. – Dmitry Kamenetsky Dec 05 '19 at 04:08
UULLDDDDRRRRUUUU will reach the exit from any starting location. – Draco18s no longer trusts SE Dec 05 '19 at 21:02

The random guy · Answer 4 · 2019-12-05T08:55:44.483

1

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.

edited Dec 05 '19 at 08:55

answered Dec 05 '19 at 08:46

The random guy

1,209
8
21

Target must be reachable from any empty cell. – Dmitry Kamenetsky Dec 05 '19 at 08: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. – The random guy Dec 05 '19 at 08:53
How many steps would your first example require? – Dmitry Kamenetsky Dec 05 '19 at 09:01
With the worst start (ina corner of the top right column) and the perfect path, only 7 steps. But getting that perfect path is unlikely. – The random guy Dec 05 '19 at 09:14
4

@DmitryKamenetsky That first example takes 14 steps: ULUR UUU LLL DDR. – Jaap Scherphuis Dec 05 '19 at 09:53
Ok i missunderstood the question, my answer is out of course – The random guy Dec 05 '19 at 10:22
1

The second example can be solved from any starting location with UUUU LLLL DR – Draco18s no longer trusts SE Dec 05 '19 at 21:03

Dmitry Kamenetsky · Answer 5 · 2019-12-08T13:17:07.483

0

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.

edited Dec 08 '19 at 13:17

answered Dec 08 '19 at 10:30

Dmitry Kamenetsky

35,897
5
66
276

1

My computer found the 17 move LUUUDRDRDDDRUULLU for the first one the 14 move UUUDRRRLULUUUL for the second. – Jaap Scherphuis Dec 08 '19 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. – Dmitry Kamenetsky Dec 08 '19 at 13:16
1

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. – Jaap Scherphuis Dec 08 '19 at 13:54

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

5 Answers5