2
$\begingroup$

Suppose that we have the following maze (_ = open, + = blocked), and we can move left,right,up,down:

+ + + + + + + + + + + + + + + + + + + + + + + + +
+ _ _ _ _ _ _ _ + _ _ _ _ _ _ _ + _ _ _ _ _ _ _ +
+ _ + + _ + + _ + _ + + _ + + _ + _ + + _ + + _ +
+ _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ _ _ + _ +
+ _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ _ _ + _ +
+ _ + + + + + _ + _ + + + + + _ + _ + + + + + _ +
+ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ +
+ + + + + + + _ + + + + + + + + + _ + + + + + + +
+ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ +
+ _ + + _ + + _ + _ + + _ + + _ + _ + + _ + + _ +
+ _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ S _ + _ +
+ _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ _ _ + _ +
+ _ + + + + + _ + _ + + + + + _ + _ + + + + + _ +
+ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ +
+ + + + + + + + + + + + + + + + + + + + + + + + +

Given that we start at a random open square in the maze, assuming there is no feedback as to if a move was successful (i.e. we encountered a blocked square) and not knowing where we started, what is a sequence of moves such that we will always end up in the square S.

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ "there is no feedback as to if a move was successful (i.e. we encountered a blocked square)". What happens if we indeed encounter a blocked square? Will we stay at the same block? "not knowing where we started". Do we know our absolute direction? That is, "we can move left,right,up,down" relative to the given maze, right? Otherwise, "up and down" should be "forward and backward". So $S$ is given and fixed. We should not care other mazes, should we? $\endgroup$
    – John L.
    May 7, 2019 at 18:54
  • 4
    $\begingroup$ Please edit the question to add a reference to the original problem. $\endgroup$
    – John L.
    May 7, 2019 at 19:11
  • $\begingroup$ Hint: For two sequences of moves beginning at different positions to end at the same position, what must happen during at least one of those sequences? $\endgroup$
    – j_random_hacker
    May 7, 2019 at 19:17
  • 3
    $\begingroup$ Consider equivalence classes of accessible squares under sequences of moves. Under the empty sequence all squares are in different classes. Applying successive moves cannot increase the number of classes. Our goal is to get all squares into the same class. How can you do that? For example, moving to the right 1000 times puts all squares in connected horizontal ranges into the same class. $\endgroup$
    – Reinstate Monica
    May 7, 2019 at 19:33
  • 1
    $\begingroup$ It's not hard at all to come up with a sequence where we're guaranteed to end at a certain square (of your choosing), after which you can hard-code the sequence to get to the end. Finding the shortest such sequence is an interesting CS problem, as would solving this problem for a general grid/graph. But as it stands this problem is just a semi-interesting puzzle that can easily be solved by hand. Flagging as off-topic. $\endgroup$
    – BlueRaja - Danny Pflughoeft
    May 7, 2019 at 19:34

1 Answer 1

Reset to default
1
$\begingroup$

This question is just a puzzle, so clearly off-topic here, but still it's funny to find answer :-)

For this specific maze there exists sequence of moves that we end up in S.

a) 12*D - and we can end up on top of any +:

 + + + + + + + + + + + + + + + + + + + + + + + + +
 + _ @ @ _ @ @ _ + _ @ @ _ @ @ _ + _ @ @ _ @ @ _ +
 + _ + + _ + + _ + _ + + _ + + _ + _ + + _ + + _ +
 + _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ _ _ + _ +
 + _ + @ @ @ + _ + _ + @ @ @ + _ + _ + @ @ @ + _ +
 + _ + + + + + _ + _ + + + + + _ + _ + + + + + _ +
 + @ @ @ @ @ @ _ @ @ @ @ @ @ @ @ @ _ @ @ @ @ @ @ +
 + + + + + + + _ + + + + + + + + + _ + + + + + + +
 + _ @ @ _ @ @ _ @ _ @ @ _ @ @ _ @ _ @ @ _ @ @ _ +
 + _ + + _ + + _ + _ + + _ + + _ + _ + + _ + + _ +
 + _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ S _ + _ +
 + _ + @ @ @ + _ + _ + @ @ @ + _ + _ + @ @ @ + _ +
 + _ + + + + + _ + _ + + + + + _ + _ + + + + + _ +
 + @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ +
 + + + + + + + + + + + + + + + + + + + + + + + + +

b) 22*L

 + + + + + + + + + + + + + + + + + + + + + + + + +
 + @ _ _ _ _ _ _ + @ _ _ _ _ _ _ + @ _ _ _ _ _ _ +
 + _ + + _ + + _ + _ + + _ + + _ + _ + + _ + + _ +
 + _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ _ _ + _ +
 + _ + @ _ _ + _ + _ + @ _ _ + _ + _ + @ _ _ + _ +
 + _ + + + + + _ + _ + + + + + _ + _ + + + + + _ +
 + @ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ +
 + + + + + + + _ + + + + + + + + + _ + + + + + + +
 + @ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ +
 + _ + + _ + + _ + _ + + _ + + _ + _ + + _ + + _ +
 + _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ S _ + _ +
 + _ + @ _ _ + _ + _ + @ _ _ + _ + _ +@_ _ _ + _ +
 + _ + + + + + _ + _ + + + + + _ + _ + + + + + _ +
 + @ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ +
 + + + + + + + + + + + + + + + + + + + + + + + + +

c) 1*R

 + + + + + + + + + + + + + + + + + + + + + + + + +
 + _ @ _ _ _ _ _ + _ @ _ _ _ _ _ + _ @ _ _ _ _ _ +
 + _ + + _ + + _ + _ + + _ + + _ + _ + + _ + + _ +
 + _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ _ _ + _ +
 + _ + _ @ _ + _ + _ + _ @ _ + _ + _ + _ @ _ + _ +
 + _ + + + + + _ + _ + + + + + _ + _ + + + + + _ +
 + _ @ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ +
 + + + + + + + _ + + + + + + + + + _ + + + + + + +
 + _ @ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ +
 + _ + + _ + + _ + _ + + _ + + _ + _ + + _ + + _ +
 + _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ S _ + _ +
 + _ + _ @ _ + _ + _ + _ @ _ + _ + _ + _ @ _ + _ +
 + _ + + + + + _ + _ + + + + + _ + _ + + + + + _ +
 + _ @ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ +
 + + + + + + + + + + + + + + + + + + + + + + + + +

d) 3*U

 + + + + + + + + + + + + + + + + + + + + + + + + +
 + _ @ _ @ _ _ _ + _ @ _ @ _ _ _ + _ @ _ @ _ _ _ +
 + _ + + _ + + _ + _ + + _ + + _ + _ + + _ + + _ +
 + _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ _ _ + _ +
 + _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ _ _ + _ +
 + _ + + + + + _ + _ + + + + + _ + _ + + + + + _ +
 + _ @ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ +
 + + + + + + + _ + + + + + + + + + _ + + + + + + +
 + _ @ _ @ _ _ _ _ _ _ _ @ _ _ _ _ _ _ _ @ _ _ _ +
 + _ + + _ + + _ + _ + + _ + + _ + _ + + _ + + _ +
 + _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ S _ + _ +
 + _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ _ _ + _ +
 + _ + + + + + _ + _ + + + + + _ + _ + + + + + _ +
 + _ @ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ +
 + + + + + + + + + + + + + + + + + + + + + + + + +

e) 19*L

 + + + + + + + + + + + + + + + + + + + + + + + + +
 + @ _ _ _ _ _ _ + _ _ _ _ _ _ _ + _ _ _ _ _ _ _ +
 + _ + + _ + + _ + _ + + _ + + _ + _ + + _ + + _ +
 + _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ _ _ + _ +
 + _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ _ _ + _ +
 + _ + + + + + _ + _ + + + + + _ + _ + + + + + _ +
 + @ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ +
 + + + + + + + _ + + + + + + + + + _ + + + + + + +
 + @ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ +
 + _ + + _ + + _ + _ + + _ + + _ + _ + + _ + + _ +
 + _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ S _ + _ +
 + _ + _ _ _ + _ + _ + _ _ _ + _ + _ + _ _ _ + _ +
 + _ + + + + + _ + _ + + + + + _ + _ + + + + + _ +
 + @ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ +
 + + + + + + + + + + + + + + + + + + + + + + + + +

Now it's simple: 5*D, 16*R, 7*D, 5*U, 3*R, 2*D and finish

Improve this answer
$\endgroup$
4
  • $\begingroup$ Nice, and the spoilers are used. Could you give a general description, how you find the solution? Say I have a different maze and would like to solve it with your method then idea would be more handy than step trace. +1 from me. $\endgroup$
    – Evil
    May 8, 2019 at 13:50
  • $\begingroup$ @ufok, a faster way is L2,R1,U12,R13,D5,R16,L6,D7,R6,U5,L3,D2. What would be the fastest way? $\endgroup$
    – John L.
    May 8, 2019 at 21:24
  • 1
    $\begingroup$ @Evil, the general problem is called synchronizing word. "Given a DFA, the problem of determining if it has a synchronizing word can be solved in polynomial time using a theorem due to Ján Černý", "which shows that a synchronizing word exists if and only if every pair of states has a synchronizing word." $\endgroup$
    – John L.
    May 11, 2019 at 16:40
  • $\begingroup$ There is a simple algorithm that finds a synchronizing word in polynomial time. However, finding a synchronizing word of minimum length is NP-hard. $\endgroup$
    – John L.
    May 11, 2019 at 17:47

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.