11
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Can a wall be placed BETWEEN cells? $\endgroup$
    – AHKieran
    Commented Dec 5, 2019 at 8:58
  • 2
    $\begingroup$ No. Walls can only replace cells. $\endgroup$
    – Dmitry Kamenetsky
    Commented Dec 5, 2019 at 9:00
  • $\begingroup$ 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. $\endgroup$
    – Trenin
    Commented Dec 5, 2019 at 18:14
  • $\begingroup$ Yes the robot operator knows the grid layout. See the linked question. $\endgroup$
    – Dmitry Kamenetsky
    Commented Dec 5, 2019 at 21:33

5 Answers 5

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ I can do it with DDDDRRULLUUUURRDD, which is 17 steps. This is still the best solution so far. $\endgroup$
    – Dmitry Kamenetsky
    Commented Dec 5, 2019 at 9:03
  • 4
    $\begingroup$ @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). $\endgroup$
    – trolley813
    Commented Dec 5, 2019 at 10:01
  • 2
    $\begingroup$ Oops you are right $\endgroup$
    – Dmitry Kamenetsky
    Commented Dec 5, 2019 at 11:51
5
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Good start, but you can find harder grids. $\endgroup$
    – Dmitry Kamenetsky
    Commented Dec 5, 2019 at 4:08
  • $\begingroup$ UULLDDDDRRRRUUUU will reach the exit from any starting location. $\endgroup$
    – Draco18s no longer trusts SE
    Commented Dec 5, 2019 at 21:02
1
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Target must be reachable from any empty cell. $\endgroup$
    – Dmitry Kamenetsky
    Commented Dec 5, 2019 at 8:50
  • $\begingroup$ which must be reachable from any empty cell My bad, I accidentally skipped this part. The last answer wasn't a serious attempt anyway. $\endgroup$
    – The random guy
    Commented Dec 5, 2019 at 8:53
  • $\begingroup$ How many steps would your first example require? $\endgroup$
    – Dmitry Kamenetsky
    Commented Dec 5, 2019 at 9:01
  • 4
    $\begingroup$ @DmitryKamenetsky That first example takes 14 steps: ULUR UUU LLL DDR. $\endgroup$
    – Jaap Scherphuis
    Commented Dec 5, 2019 at 9:53
  • 1
    $\begingroup$ The second example can be solved from any starting location with UUUU LLLL DR $\endgroup$
    – Draco18s no longer trusts SE
    Commented Dec 5, 2019 at 21:03
0
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ My computer found the 17 move LUUUDRDRDDDRUULLU for the first one the 14 move UUUDRRRLULUUUL for the second. $\endgroup$
    – Jaap Scherphuis
    Commented Dec 8, 2019 at 12:42
  • $\begingroup$ 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. $\endgroup$
    – Dmitry Kamenetsky
    Commented Dec 8, 2019 at 13:16
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jaap Scherphuis
    Commented Dec 8, 2019 at 13:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.