3
$\begingroup$

I have been trying to wrap my head around this problem, and I just can't get it.

  • We have an $a \times b$ matrix where every cell corresponds to either an empty space, denoted with a dot, or a wall, denoted with $X$.

  • There are two pawns in different locations within the maze, their movements are synchronized and they must leave the maze (it has multiple exits) in the same move.

  • If one moves and the other is up against a wall, it's a valid move and the other one stays in place.

  • The goal is to write an algorithm that finds the lowest possible moves to get both out of the maze at the same time, of time complexity $\mathcal O(a^2 b^2)$.

I got some advice to use BFS for this problem, but I don't get how it would deal with all of the backtracking that has to be done. I've included two visualizations with the correct paths labeled to help explain the problem.


Example 1: Pawn starting positions shown as blue squares

Example 1


Example 2: Pawn starting position shown as blue square and red square

Example 2

$\endgroup$
  • $\begingroup$ Can you please cite the source where you found this problem? I believe I have seen this on a past online coding challenge but cannot remember the name. $\endgroup$ – ryan Apr 19 at 16:14
  • 1
    $\begingroup$ With BFS you should not have to back track, each state can be uniquely identified by two pairs of coordinates (one for blue and one for red). You should BFS-ing these pairs. For instance in your lower example there are four children of the initial state $(\mathrm{blue}, \mathrm{red}) = ((1,1), (1,4))$. You just need to ensure that you don't terminate unless both players exit at the same time. You can analyze this by noting that there's at most $(n \times m)^2$ possible unique states that BFS would visit. $\endgroup$ – ryan Apr 19 at 16:17
  • $\begingroup$ @ryan This is a homework problem that my instructor came up with, I don't think its online or in any books. I just dont get what BFS will do, I would need each pawn to have the same move set. When I think of BFS this visualgo.net/en/dfsbfs is what comes to mind. If I have this graph imgur.com/a/wSMxyAG, what would my next step be? $\endgroup$ – mander39 Apr 19 at 18:06
  • $\begingroup$ You need to think of the game as a graph. Where a "state" of the game is a "node" in the graph we're searching. We can represent a state as described above with pairs of points. We then put an edge connecting one "state" to another "state" if a move would get you there. For instance $((1,1), (1,4))$ would have an edge to $((1,2),(1,5))$ for the move right. Then all you're trying to do is search this graph for a valid end node. $\endgroup$ – ryan Apr 19 at 18:09
3
$\begingroup$

I am going to take a guess that you are having trouble with understanding how BFS will work on this game. First, you may wonder "what is the graph we are searching on?" Let's first start with, you are not searching through the game board. This is not what you are doing at all.

How to represent Game State

You are search through game states. I am using game state to mean:

Game state - a full and unique description of all pieces/players in the game at the start of any "turn" during the duration of game play. A game state is final when pieces are in a position that satisfies the termination constraint.

Termination constraint as you have define is when two pawns are both able to leave the grid with the same move. You could alternatively define it as a state right after this move has been made.

Here are some examples of game states that can be uniquely describe by a $3 \times 8$ matrix $G$ where we make each entry either: Red, Blue, White, or Black.:

  1. We would have $G_{1,1} = \text{Blue}$ and $G_{1,4} = \text{Red}$ and assign the rest of $G_{i,j}$ appropriately.

g1

  1. We would have $G_{0,1} = \text{Blue}$ and $G_{1,3} = \text{Red}$ and assign the rest of $G_{i,j}$ appropriately.

g2

  1. We would have $G_{0,6} = \text{Blue}$ and $G_{1,1} = \text{Red}$ and assign the rest of $G_{i,j}$ appropriately.

g3

One important thing to note here is that the only thing changing in these game states is the location of Red and Blue, everything else stays the same. This should give you some indication that we only need to maintain the location of Red and Blue to get a unique description of the game state. With this idea, we can represent all three of the prior games states as:

  1. $\text{Blue} = (1,1)$ and $\text{Red} = (1,4)$
  2. $\text{Blue} = (0,1)$ and $\text{Red} = (1,3)$
  3. $\text{Blue} = (0,6)$ and $\text{Red} = (1,1)$

To be concise I will represent them as pairs of coordinates:

  1. State = $[(1,1), (1,4)]$.
  2. State = $[(0,1), (1,3)]$.
  3. State = $[(0,6), (1,1)]$.

Another important thing to note here, is that the states do not need to be "possible" in the sense that we can always reach them from our initial state. The purpose of using these states is so that we can create a graph to BFS.


Graph Representation of Game States

To be able to properly "search" through the game states, we will make each state a node in our abstract graph. We will add an edge from state $s_1$ to state $s_2$ if we can get from state $s_1$ to state $s_2$ by moving both players either Up, Down, Left, or Right. Using our first example:

State $[(1,1), (1,4)]$ can move to:

  1. State $[(0,1), (1,4)]$ via the Up move.
  2. State $[(1,0), (1,3)]$ via the Left move.
  3. State $[(1,1), (1,4)]$ via the Down move.
  4. State $[(1,2), (1,5)]$ via the Right move.

So in a graph it would look like this:

g4


How to BFS Game States

We will be looking for the shortest sequence of moves such that we reach a final state. For instance, $[(0,1), (0,6)]$ would be a final state because they can both move Up to leave the grid. One option would be to create the entire graph, then run the BFS from our start node. However, this can be costly. We can instead generate nodes adjacent to our current node on demand. We can also check if we reach a final state on demand. We need to also make sure we cannot visit "invalid" board states. For instance $[(-1,1),(1,4)]$ would be invalid because "-1" is outside our bounds. $[(0,0), (1,4)]$ would also be invalid because $G_{0,0}$ is a black square and we cannot move there.

This should be enough information to get you started. I will leave the analysis up to you. A hint on the analysis would be to consider how many game states are possible as we know in the worst cases we may visit each and all of them.

$\endgroup$
  • $\begingroup$ Thanks so much for the detailed response, I think I understand how to do it now. I was definitely stuck on the idea of BFSing the game board. $\endgroup$ – mander39 Apr 19 at 21:52
  • $\begingroup$ @mander39 yes that is where most people get stuck in these types of games. For a more difficult exercise, consider how you could BFS a Pacman game to eat all the dots as fast as possible (assume there's no ghosts). Again, you are not BFS-ing the game board. Think about how you represent a game state (pacman and the dots) with this setup. It's a little trickier than this, but it is a common exercise. $\endgroup$ – ryan Apr 19 at 22:46
  • 1
    $\begingroup$ Awesome response!!! $\endgroup$ – Carlos Linares López Apr 20 at 0:20

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.