8
$\begingroup$

Given a 2-dimensional maze where you can give 4 commands "move up/down/right/left". Knowing the maze but not where the person is, how to find the minimum sequence of commands that guarantees exiting the maze? I'm looking for a single sequence of commands that will work no matter where in the maze you start from.

Assume that if the person is given the "move right" command when there's a wall on the right, he will simply stay where he is.

Yuval Filmus mentions this is a special case of a synchronizing word problem, and might be related to universal traversal sequences. I also found a paper that seems relevant:

The Simultaneous Maze Solving Problem. Stefan Funke, André Nusser, Sabine Storandt. AAAI 2017.

Unfortunately for general graphs this appears to be a unsolved problem, but I'm wondering if there might be a good algorithm for this specific case. I came up with a candidate approach: Label every position with the number of minimum steps it requires to exit, and keep track of every agent in the maze. It might be possible to do a A* search this way.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Discrete lizard Feb 11 at 19:53
  • 2
    $\begingroup$ What does the maze-explorer know? For example, if they attempt to "move right", and then it fails, do they know that it's failed? $\endgroup$ – Nat Feb 12 at 1:34

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.