0
$\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. Once the robot reaches the target, the game will terminate immediately.

It turns out that any map (where the target is reachable) can be solved with a finite number of commands. Furthermore there exists a sequence of commands that will solve ANY 2x2 grid, no matter where the robot starts, or where the target cell is or where the walls are (including walls inside the grid). What is the shortest such sequence of commands?

Improve this question
$\endgroup$
11
  • 2
    $\begingroup$ I've downvoted because it seems to me like the best way to solve this is with a brute-force computer search - I would be very surprised if this had a clean logical solution, or any "aha moment". $\endgroup$
    – Deusovi ♦
    Dec 3, 2019 at 8:37
  • 4
    $\begingroup$ Are the walls located between two cells or do they replace a cell of a grid like in the 9x9 version? $\endgroup$
    – npkllr
    Dec 3, 2019 at 8:50
  • 1
    $\begingroup$ They replace a cell like in 9x9 version $\endgroup$
    – Dmitry Kamenetsky
    Dec 3, 2019 at 9:09
  • 4
    $\begingroup$ Hmm I wonder why the downvotes? Is it too hard? Too similar to previous question? Poorly written? Please tell me how I can improve it. Personally I found the puzzle quite interesting to solve by hand... $\endgroup$
    – Dmitry Kamenetsky
    Dec 3, 2019 at 15:09
  • 1
    $\begingroup$ Yay back to 0 votes! $\endgroup$
    – Dmitry Kamenetsky
    Dec 5, 2019 at 13:51

2 Answers 2

Reset to default
7
$\begingroup$

Assuming that the walls replace a cell of a grid like in the 9x9 version and are not located between two cells.

I found a solution with 9 moves: RDLURULDR

How I got there:

There are 14 possible grids: (black cells representing walls)

enter image description here

We can forget about the all black grid (not solvable) and grids with three walls (solved without a move).
To cover the grids with two walls our sequence must contain at least one Up(U), one Down(D), one Right(R) and one Left(L) move.

The most complicated grids are the ones containing a single wall.
Let's just focus on the grid with a wall in the top left. Starting in the top right, our robot can use the sequence DL to cover all cells. Starting in the bottom left, he can use the sequence RU.
Following this for all four possible grids, we get the following sequences: DL, RU, DR, LU, LD, UR, RD, UL.
One minimal sequence containing all these subsequence is RDLURULDR, our final solution.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Great work and nicely explained! $\endgroup$
    – Dmitry Kamenetsky
    Dec 10, 2019 at 6:58
1
$\begingroup$

Looks like we have

eight

mazes we need to solve simultaneously:

 +---+
 |o|T|
 |   |
 +---+

and

its mirror image, both in any rotation.

These are the difficult cases, so all the other configurations (that are solvable in the first place) should be automatically solved if we can get all of these.

So we need a move sequence that has

all possible "two left turns in a row" sequences, and all possible "two right turns in a row" sequences too.

Here's one:

DRULD-R-DLURD

Which has

11 commands.

Is it optimal? No idea. I'm going to need some more coffee if I'm to figure that out.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Sorry I didn't explain. Walls replace cells like in the 9x9 version. $\endgroup$
    – Dmitry Kamenetsky
    Dec 3, 2019 at 9:13

Your Answer

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

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