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.

$\endgroup$
  • 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 '19 at 18:54
  • 4
    $\begingroup$ Please edit the question to add a reference to the original problem. $\endgroup$ – John L. May 7 '19 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 '19 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 '19 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 '19 at 19:34
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

| cite | improve this answer | |
$\endgroup$
  • $\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 '19 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 '19 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 '19 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 '19 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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