Finding the shortest path for synchronized pawns in a maze

Question

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 2: Pawn starting position shown as blue square and red square

Answer 1

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.

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

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

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:

---

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.