45
$\begingroup$

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!

enter image description here

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ Just to give a lower bound for the minimum possible solution: A robot in the lower left corner needs at least 14 moves to reach the T (7 right and 7 up) a robot in the upper left corner would need at least an additional 3 moves down and a robot in the lower right corner would need at least 3 moves left. This means the absolute minimum is at least 20 moves. - I wonder if we can increase this lower bound? $\endgroup$
    – Falco
    Commented Dec 2, 2019 at 12:23
  • 2
    $\begingroup$ I think we need at least 2 more, because we need to collect the robots from different quadrants in the center, which means one robot needs to move to the 5. line, before the other robots can join him in the center, so he doesn't move back into is quadrant. But this move will cost the other robot at least one move, where it runs into the barrier. This would set the minimum solution at least to 22 moves. $\endgroup$
    – Falco
    Commented Dec 2, 2019 at 12:30
  • 11
    $\begingroup$ If you want to play the puzzle interactively, I've created a JSFiddle: jsfiddle.net/falco467/zmk0r46y/2/show $\endgroup$
    – Falco
    Commented Dec 2, 2019 at 17:12
  • 3
    $\begingroup$ Falco that's a brilliant little game! Love it. It makes solving this puzzle much easier. $\endgroup$
    – Dmitry Kamenetsky
    Commented Dec 2, 2019 at 21:53
  • 1
    $\begingroup$ I will be making a YouTube video about it with the solution ..will give you credit, of course and provide a link to this page. hope that it is okay . $\endgroup$
    – Hemant Agarwal
    Commented Feb 9, 2021 at 11:48

3 Answers 3

Reset to default
27
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • 3
    $\begingroup$ Great work Jaap and very well explained! I believe this is not optimal, but is close. Note after R step you are missing a O at row 4 and column 6, while O at row 6 and column 7 should be removed. Not sure how this affects final result and whether there are other errors. $\endgroup$
    – Dmitry Kamenetsky
    Commented Dec 2, 2019 at 8:04
  • 1
    $\begingroup$ @DmitryKamenetsky: I didn't do the effect of that R step at all well, only moving to the right the bits I was interested in. I have fixed that stage now, and the updated the later diagrams. I did not need to change the solution, and this fix doesn't seem to allow any new opportunities for improvements, so my answer is still the same as before. $\endgroup$
    – Jaap Scherphuis
    Commented Dec 2, 2019 at 8:45
  • 1
    $\begingroup$ I have now found optimal solutions by computer. $\endgroup$
    – Jaap Scherphuis
    Commented Dec 2, 2019 at 16:13
  • 4
    $\begingroup$ @DmitryKamenetsky The 180 solutions were all similar. 180=2*6*15 There is diagonal mirror symmetry for the factor of 2. There are 6 trivial reorderings of the last RRUU moves. The remaining 15 variations reorder the first LULULU moves (but never have three same moves in a row), and some of these reorderings also allow the first UR to be swapped to RU. $\endgroup$
    – Jaap Scherphuis
    Commented Dec 3, 2019 at 7:45
  • 5
    $\begingroup$ @justhalf Yes, it is A*, and with iterative deepening it is called IDA*. $\endgroup$
    – Jaap Scherphuis
    Commented Dec 3, 2019 at 8:03
13
$\begingroup$

I have a

25: LLL UUUU RRR UU RRR DDD RRRR UU L

Here are the details:

 LLL
 o . . . x o . . .
 o . . . x o . T .
 o . . . x o . . .
 o o o o o o . . .
 x x x o . . x x x
 o o o o o o . . .
 o . . . x o . . .
 o . . . x o . . .
 o . . . x o . . .
 
 UUUU
 o o o o x o . . .
 . . . o x o . T .
 . . . . x o . . .
 . . . . o o . . .
 x x x . . o x x x
 o o o . . . . . .
 . . . . x . . . .
 . . . . x . . . .
 . . . . x . . . .
 
 3
 RRR
 . . . o x . . . o
 . . . o x . . T .
 . . . . x . . . o
 . . . . . . . o o
 x x x . . o x x x
 . . . o o o . . .
 . . . . x . . . .
 . . . . x . . . .
 . . . . x . . . .
 
 UU
 
 . . . o x . . . o
 . . . . x . . T o
 . . . . x o . . .
 . . . o o o . . .
 x x x . . . x x x
 . . . . . . . . .
 . . . . x . . . .
 . . . . x . . . .
 . . . . x . . . .
 
 RRRDDD
 
 . . . . x . . . .
 . . . . x . . T .
 . . . . x . . . .
 . . . o . . o o o
 x x x . . . x x x
 . . . . . . . . .
 . . . . x . . . .
 . . . . x . . . .
 . . . . x . . . .

 RRRR
 
 . . . . x . . . .
 . . . . x . . T .
 . . . . x . . . .
 . . . . . . . o o
 x x x . . . x x x
 . . . . . . . . .
 . . . . x . . . .
 . . . . x . . . .
 . . . . x . . . .

And the final UUL makes sure every path has touched the T.

Improve this answer
$\endgroup$
5
$\begingroup$

Taking the basics of Jaap Scherphuis solution, I made some changes.

For my solution I used 27 moves: RRR UUU R DDD RR UUU RR LLL UU RR UU D

"Once the robot reaches the target, the game will terminate immediately."
If I understood this rule correctly, not all robots have to end up on the target square after the same number of moves. Once a robot reaches the target, he has completed the game and we don't have to care about him anymore.

 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
 
 RRR (3)
 
 . . . o x . . . o
 . . . o x . . T o
 . . . o x . . . o
 . . . o o o o o o
 x x x . . o x x x
 . . . o o o o o o
 . . . o x . . . o
 . . . o x . . . o
 . . . o x . . . o
 
 UUU (6)
 
 . . . o x o o . o
 . . . . x o . T .
 . . . o x o . . .
 . . . o o . . . .
 x x x o . . x x x
 . . . o . . o o o
 . . . . x . . . .
 . . . . x . . . .
 . . . . x . . . .
 
 R (7)
 
 . . . o x . o o o
 . . . . x . o T .
 . . . o x . o . .
 . . . . o o . . .
 x x x . o . x x x
 . . . . o . . o o
 . . . . x . . . .
 . . . . x . . . .
 . . . . x . . . .
 
 DDD (10)
 
 . . . . x . . . .
 . . . . x . . T .
 . . . . x . . . .
 . . . o . . o . o
 x x x . . . x x x
 . . . o o o . . .
 . . . . x . . . .
 . . . . x . . . .
 . . . . x . . o o
 
 RR (12)
 
 . . . . x . . . .
 . . . . x . . T .
 . . . . x . . . .
 . . . . . o . . o
 x x x . . . x x x
 . . . . . o o o .
 . . . . x . . . .
 . . . . x . . . .
 . . . . x . . . o
 
 UUU (15)
 
 . . . . x o . . o
 . . . . x . . T .
 . . . . x o . . .
 . . . . . . . . .
 x x x . . . x x x
 . . . . . . o o o
 . . . . x . . . .
 . . . . x . . . .
 . . . . x . . . .
 
 RR (17)
 
 . . . . x . . o o
 . . . . x . . T .
 . . . . x . . o .
 . . . . . . . . .
 x x x . . . x x x
 . . . . . . . . o
 . . . . x . . . .
 . . . . x . . . .
 . . . . x . . . .
 
 LLL (20)
 
 . . . . x o . . .
 . . . . x . . T .
 . . . . x o . . .
 . . . . . . . . .
 x x x . . . x x x
 . . . . . o . . .
 . . . . x . . . .
 . . . . x . . . .
 . . . . x . . . .
 
 UU (22)
 
 . . . . x o . . .
 . . . . x . . T .
 . . . . x . . . .
 . . . . . o . . .
 x x x . . . x x x
 . . . . . . . . .
 . . . . x . . . .
 . . . . x . . . .
 . . . . x . . . .
 
 RR (24)
 
 . . . . x . . o .
 . . . . x . . T .
 . . . . x . . . .
 . . . . . . . o .
 x x x . . . x x x
 . . . . . . . . .
 . . . . x . . . .
 . . . . x . . . .
 . . . . x . . . .
 
 UU (26)
 
 . . . . x . . o .
 . . . . x . . T .
 . . . . x . . . .
 . . . . . . . . .
 x x x . . . x x x
 . . . . . . . . .
 . . . . x . . . .
 . . . . x . . . .
 . . . . x . . . .
 
 D (27)
 
 . . . . x . . . .
 . . . . x . . T .
 . . . . x . . . .
 . . . . . . . . .
 x x x . . . x x x
 . . . . . . . . .
 . . . . x . . . .
 . . . . x . . . .
 . . . . x . . . .

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ I didn't even consider that. Very nice! $\endgroup$
    – Jaap Scherphuis
    Commented Dec 2, 2019 at 9:13
  • 1
    $\begingroup$ Great trick there! $\endgroup$
    – Dmitry Kamenetsky
    Commented Dec 2, 2019 at 9:52
  • 1
    $\begingroup$ @JanusBahsJacquet Yes, you're right. Changed it :) $\endgroup$
    – npkllr
    Commented Dec 4, 2019 at 8:07

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.