0
$\begingroup$

How to efficiently exit from a maze where you know the initial position of the player (1,1), the exit (49,49)?

You don't know the maze configuration but you know where your player is, and which direction are opened from his position.

Another point, the player can move RIGHT/DOWN/LEFT/UP, and the exit is at the bottom right.

I tried to mainly follow RIGHT/DOWN and avoid dead ends, but I think we can do better!

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Do you know any Graph Search algorithms? $\endgroup$ – Pål GD Mar 18 at 9:17
  • 1
    $\begingroup$ (Imagine her loyal dog starting from the exit, ready to smell out her steps and lead her out.) $\endgroup$ – greybeard Mar 18 at 9:20
  • $\begingroup$ @PålGD I know common graph search algorithms but here I have 2 constraints: minimize numbers of steps and, I don't know the plan of the maze :/ $\endgroup$ – KKc Mar 19 at 13:54
  • $\begingroup$ Follow the wall? $\endgroup$ – Hendrik Jan Apr 17 at 13:35
0
$\begingroup$

The fact that the exit is in the bottom right and has coordinates $(49, 49)$, while the player has coordinates $(1,1)$ makes me think that the maze has a fixed size of $49 \times 49$. If that's the case the exit can be found in constant time.

In fact, there is a fixed strategy (i.e., a sequence of moves) that uses a constant number of moves and exits the maze, regardless of the maze layout!

You can construct this strategy as follows: enumerate all possible maze layouts $L_1, L_2, \dots$ (a crude upper bound on the number of mazes is $2^{49^2}$).

You can construct the sequence $S$ of moves iteratively. Initially $S$ is the empty sequence. Then, for each $L_i$ you can extend $S$ as follows:

  • Assume that the maze layout is $L_i$, and compute the position $p$ in which the player would end up by following the steps in $S$ from position $(1,1)$ in $L_i$.
  • Find a sequence $S_i$ of at most $49^2$ moves that make the player walk from $p$ to $(49,49)$ in $L_i$. This sequence always exists and can be found, e.g., with a breadth first search from $p$ in the graph induced by $L_i$.
  • Append $S_i$ to $S$.

The resulting sequence $S$ has length at most $2^{49^2} \cdot 49^2 < 2^{2413} = O(1)$.

Notice that the above algorithm is only needed to construct $S$ once and for all. An algorithm that solves your original problem can just output the hardcoded strategy $S$, without even looking at its input.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you Steven for your answer, however, it seems that, for finding each sequence Si, the player has to explore the maze, and the total number of step will be very high! at least more than just trying to follow the right hand for instance... $\endgroup$ – KKc Mar 19 at 14:00
  • $\begingroup$ There is no need to explore the maze. The whole point is that you are able to construct the sequence without even knowing what the maze will be. You are essentially building a sequence of moves that works regardless of the maze layout. by "trying all possible layouts". Of course the length of this sequence will be huge for practical purposes, but if we care about the asymptotic number of steps needed, this is just some big constant, i.e., it is in $O(1)$. $\endgroup$ – Steven Mar 19 at 14:34
  • $\begingroup$ For a practical algorithm you can just run a depth-first seach on the graph in which each vertex $(i,j)$ is a position and edge $(p_1,p_2)$ connects two positions $p_1=(i_1, j_1)$ and $p_2 = (i_2, j_2)$ such that $|i_1-i_2|+|j_1-j_2|=1$ and you can directly move from $p_1$ to $p_2$. Notice that you do not need to know the graph in advance as the DFS only needs to know the edges adjacent to the current vertex. Start from $(1,1)$ and stop whenever you encounter $(49, 49)$. The time complexity is $O(1)$, since the input maze has constant size. For general $n \times m$ mazes, it is $O(nm)$. $\endgroup$ – Steven Mar 19 at 14:40
  • $\begingroup$ given your first comment, my concern is not the number of steps in terms of complexity of the algorithm, but the numbers of steps that must be taken to exit the maze... and also, In the rule, I don't have the permission to do a map of the maze; with your solution, even if I obtain S, I should, for each new maze, identify what is the corresponding Li for finding the good Si $\endgroup$ – KKc Mar 19 at 14:53

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.