# Maximum Number of Moves to Kill All Pawns
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-number-of-moves-to-kill-all-pawns)
Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-moves-to-kill-all-pawns
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Game Theory](https://scaleengineer.com/dsa/patterns/game-theory), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array
---
## Problem
There is a `50 x 50` chessboard with **one** knight and some pawns on it. You are given two integers `kx` and `ky` where `(kx, ky)` denotes the position of the knight, and a 2D array `positions` where `positions[i] = [xi, yi]` denotes the position of the pawns on the chessboard.

Alice and Bob play a _turn-based_ game, where Alice goes first. In each player's turn:

* The player _selects_ a pawn that still exists on the board and captures it with the knight in the **fewest** possible **moves**. **Note** that the player can select **any** pawn, it **might not** be one that can be captured in the **least** number of moves.
* In the process of capturing the _selected_ pawn, the knight **may** pass other pawns **without** capturing them. **Only** the _selected_ pawn can be captured in _this_ turn.

Alice is trying to **maximize** the **sum** of the number of moves made by _both_ players until there are no more pawns on the board, whereas Bob tries to **minimize** them.

Return the **maximum** _total_ number of moves made during the game that Alice can achieve, assuming both players play **optimally**.

Note that in one **move,** a chess knight has eight possible positions it can move to, as illustrated below. Each move is two cells in a cardinal direction, then one cell in an orthogonal direction.

![](https://assets.glich.co/dsa/maximum-number-of-moves-to-kill-all-pawns/image0.jpg)

**Example 1:**

**Input:** kx = 1, ky = 1, positions = \[\[0,0\]\]

**Output:** 4

**Explanation:**

![](https://assets.glich.co/dsa/maximum-number-of-moves-to-kill-all-pawns/image1.gif)

The knight takes 4 moves to reach the pawn at `(0, 0)`.

**Example 2:**

**Input:** kx = 0, ky = 2, positions = \[\[1,1\],\[2,2\],\[3,3\]\]

**Output:** 8

**Explanation:**

**![](https://assets.glich.co/dsa/maximum-number-of-moves-to-kill-all-pawns/image2.gif)**

* Alice picks the pawn at `(2, 2)` and captures it in two moves: `(0, 2) -> (1, 4) -> (2, 2)`.
* Bob picks the pawn at `(3, 3)` and captures it in two moves: `(2, 2) -> (4, 1) -> (3, 3)`.
* Alice picks the pawn at `(1, 1)` and captures it in four moves: `(3, 3) -> (4, 1) -> (2, 2) -> (0, 3) -> (1, 1)`.

**Example 3:**

**Input:** kx = 0, ky = 0, positions = \[\[1,2\],\[2,4\]\]

**Output:** 3

**Explanation:**

* Alice picks the pawn at `(2, 4)` and captures it in two moves: `(0, 0) -> (1, 2) -> (2, 4)`. Note that the pawn at `(1, 2)` is not captured.
* Bob picks the pawn at `(1, 2)` and captures it in one move: `(2, 4) -> (1, 2)`.

**Constraints:**

* `0 <= kx, ky <= 49`
* `1 <= positions.length <= 15`
* `positions[i].length == 2`
* `0 <= positions[i][0], positions[i][1] <= 49`
* All `positions[i]` are unique.
* The input is generated such that `positions[i] != [kx, ky]` for all `0 <= i < positions.length`.

# Approaches
## Brute-Force Minimax Recursion
This approach directly translates the game's rules into a recursive function. The function explores all possible sequences of pawn captures. Since Alice wants to maximize the total moves and Bob wants to minimize it, this is a classic minimax problem. The recursive function calculates the score for every possible move (capturing any of the remaining pawns) and chooses the best one according to the current player's objective (max for Alice, min for Bob). However, it does not store the results of subproblems, leading to redundant calculations.
**Time:** O(N! * N * W * H), where N is the number of pawns, and W, H are the board dimensions. The recursion tree explores N! permutations of pawn captures. At each node, it iterates through remaining pawns and runs a BFS which takes O(W*H). This is computationally infeasible for N=15. · **Space:** O(N + W*H), where N is the number of pawns and W, H are the board dimensions. The recursion depth is N, and the BFS requires O(W*H) space for its visited set and queue.
**Pros:** Simple to understand and directly models the game logic.
**Cons:** Extremely inefficient due to massive re-computation of the same subproblems.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints as the complexity is factorial.
### Explanation
We define a recursive helper function, say `solve(current_kx, current_ky, remaining_pawns_mask, turn_count)`.

- `current_kx`, `current_ky`: The knight's current coordinates.
- `remaining_pawns_mask`: A bitmask representing the set of pawns still on the board.
- `turn_count`: The number of pawns already captured, used to determine whose turn it is.

This function works as follows:

1.  **Base Case:** If `remaining_pawns_mask` is 0 (all pawns captured), the game ends, and we return 0.
2.  **Recursive Step:**
    - Determine the current player. If `turn_count` is even, it's Alice's turn (maximizer). If odd, it's Bob's turn (minimizer).
    - Iterate through each pawn `i` that is still on the board (i-th bit in the mask is 1).
    - For each such pawn `i` at `(px, py)`:
        - Calculate the number of moves `m` for the knight to go from `(current_kx, current_ky)` to `(px, py)`. This is done using a Breadth-First Search (BFS) for each call.
        - Recursively call the function for the next state: `solve(px, py, new_mask, turn_count + 1)`, where `new_mask` has the i-th bit turned off.
        - The total score for this choice is `m + recursive_result`.
    - If it's Alice's turn, she will choose the pawn `i` that maximizes this total score.
    - If it's Bob's turn, he will choose the pawn `i` that minimizes this total score.

The initial call would be `solve(kx, ky, (1 << N) - 1, 0)`, where `N` is the number of pawns.

```java
class Solution {
    int[][] positions;
    int n;

    public int maxMoves(int kx, int ky, int[][] positions) {
        this.positions = positions;
        this.n = positions.length;
        return solve(kx, ky, (1 << n) - 1, 0);
    }

    private int solve(int r, int c, int mask, int turn) {
        if (mask == 0) {
            return 0;
        }

        if (turn % 2 == 0) { // Alice's turn (Maximizer)
            int maxVal = Integer.MIN_VALUE;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    int[] nextPos = positions[i];
                    int moves = bfs(r, c, nextPos[0], nextPos[1]);
                    int remainingScore = solve(nextPos[0], nextPos[1], mask ^ (1 << i), turn + 1);
                    maxVal = Math.max(maxVal, moves + remainingScore);
                }
            }
            return maxVal;
        } else { // Bob's turn (Minimizer)
            int minVal = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    int[] nextPos = positions[i];
                    int moves = bfs(r, c, nextPos[0], nextPos[1]);
                    int remainingScore = solve(nextPos[0], nextPos[1], mask ^ (1 << i), turn + 1);
                    minVal = Math.min(minVal, moves + remainingScore);
                }
            }
            return minVal;
        }
    }

    private int bfs(int startX, int startY, int endX, int endY) {
        if (startX == endX && startY == endY) return 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{startX, startY, 0});
        boolean[][] visited = new boolean[50][50];
        visited[startX][startY] = true;
        int[] dr = {-2, -2, -1, -1, 1, 1, 2, 2};
        int[] dc = {-1, 1, -2, 2, -2, 2, -1, 1};

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int r = curr[0], c = curr[1], dist = curr[2];

            if (r == endX && c == endY) {
                return dist;
            }

            for (int i = 0; i < 8; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                if (nr >= 0 && nr < 50 && nc >= 0 && nc < 50 && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    queue.offer(new int[]{nr, nc, dist + 1});
                }
            }
        }
        return -1; // Should not be reached
    }
}
```
### Algorithm
- Define a recursive function `solve(current_knight_pos, remaining_pawns_mask, turn_number)`.
- **Base Case:** If `remaining_pawns_mask` is zero (no pawns left), return 0.
- **Recursive Step:**
  - Determine if it's Alice's (maximizer) or Bob's (minimizer) turn based on `turn_number`.
  - Initialize a variable `best_score` to a very small value for Alice or a very large value for Bob.
  - Iterate through each pawn `p` that is still available in `remaining_pawns_mask`.
  - For each available pawn `p`:
    - Calculate the shortest distance `d` from the knight's current position to `p`'s position using a Breadth-First Search (BFS).
    - Recursively call `solve` for the next state: `solve(p's_pos, new_mask, turn_number + 1)`, where `new_mask` is the mask with `p` removed.
    - The total score for choosing `p` is `d + recursive_score`.
    - Update `best_score` by taking the maximum (for Alice) or minimum (for Bob) of the current `best_score` and the calculated total score.
- Return `best_score`.
- The initial call is made with the knight's starting position, a mask with all pawns present, and turn number 0.

## Minimax with Memoization (Top-Down DP)
This approach significantly optimizes the brute-force recursion by using memoization, a form of dynamic programming. The key observation is that the optimal score from a certain game state (defined by the knight's current position and the set of remaining pawns) is always the same, regardless of how that state was reached. By pre-calculating all required distances and storing the results of subproblems in a memoization table, we avoid redundant calculations and solve the problem efficiently.
**Time:** O((N+1) * W*H + (N+1) * 2^N * N). The pre-computation of distances takes `O((N+1) * W*H)`. The DP part has `(N+1) * 2^N` states, and each state computation involves a loop of size `N`. This is efficient enough for N=15. · **Space:** O((N+1)^2 + (N+1) * 2^N). This is dominated by the memoization table, where N is the number of pawns. `O((N+1)^2)` is for the distance matrix, and `O((N+1) * 2^N)` for the memoization table.
**Pros:** Highly efficient and guaranteed to pass within the given constraints.; It's the standard and optimal solution for this class of problems (game theory on a small set of nodes).
**Cons:** More complex to implement than the brute-force approach.; Requires understanding of dynamic programming, bitmasking, and pre-computation strategies.
### Explanation
The state of the game can be uniquely identified by `(last_captured_pawn_index, mask_of_remaining_pawns)`. The solution involves two main steps:

**1. Pre-computation of Distances:**
First, we create a unified list of all important locations: the knight's starting position and all pawn positions. Let's say this list has `N+1` locations. We then pre-calculate the shortest number of moves (distance) between every pair of these `N+1` locations by running a Breadth-First Search (BFS) starting from each location. The results are stored in a 2D array, `dist[i][j]`, which avoids running BFS repeatedly inside the recursive function.

**2. Memoized Recursion:**
We define a recursive function, `solve(prev_loc_idx, mask)`, where `prev_loc_idx` is the index of the knight's current location in our unified list (we use index `N` for the initial position), and `mask` is a bitmask representing the set of pawns yet to be captured. A 2D array `memo[prev_loc_idx][mask]` is used to store the computed results.

```java
class Solution {
    private int n;
    private int[][] dist;
    private Integer[][] memo;

    public int maxMoves(int kx, int ky, int[][] positions) {
        this.n = positions.length;
        int[][] allPos = new int[n + 1][2];
        for (int i = 0; i < n; i++) {
            allPos[i] = positions[i];
        }
        allPos[n] = new int[]{kx, ky};

        // Step 1: Pre-compute all-pairs shortest paths
        this.dist = new int[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            calculateDistancesFrom(i, allPos);
        }

        // Step 2: Minimax with memoization
        this.memo = new Integer[n + 1][1 << n];
        return solve(n, (1 << n) - 1);
    }

    private void calculateDistancesFrom(int startIdx, int[][] allPos) {
        int startX = allPos[startIdx][0];
        int startY = allPos[startIdx][1];
        
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{startX, startY, 0});
        
        int[][] d = new int[50][50];
        for (int[] row : d) Arrays.fill(row, -1);
        d[startX][startY] = 0;
        
        int[] dr = {-2, -2, -1, -1, 1, 1, 2, 2};
        int[] dc = {-1, 1, -2, 2, -2, 2, -1, 1};

        while(!queue.isEmpty()){
            int[] curr = queue.poll();
            int r = curr[0], c = curr[1], moves = curr[2];

            for(int i=0; i<8; ++i){
                int nr = r + dr[i];
                int nc = c + dc[i];
                if(nr >= 0 && nr < 50 && nc >= 0 && nc < 50 && d[nr][nc] == -1){
                    d[nr][nc] = moves + 1;
                    queue.offer(new int[]{nr, nc, moves + 1});
                }
            }
        }
        
        for(int i=0; i<=n; ++i){
            dist[startIdx][i] = d[allPos[i][0]][allPos[i][1]];
        }
    }

    private int solve(int prevIdx, int mask) {
        if (mask == 0) {
            return 0;
        }
        if (memo[prevIdx][mask] != null) {
            return memo[prevIdx][mask];
        }

        int numCaptured = n - Integer.bitCount(mask);
        boolean isAliceTurn = (numCaptured % 2 == 0);

        int result;
        if (isAliceTurn) { // Maximizer
            result = Integer.MIN_VALUE;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    int currentScore = dist[prevIdx][i] + solve(i, mask ^ (1 << i));
                    result = Math.max(result, currentScore);
                }
            }
        } else { // Minimizer
            result = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    int currentScore = dist[prevIdx][i] + solve(i, mask ^ (1 << i));
                    result = Math.min(result, currentScore);
                }
            }
        }

        return memo[prevIdx][mask] = result;
    }
}
```
### Algorithm
- **Step 1: Pre-computation of Distances**
  - Create a list of all `N+1` locations (initial knight position + `N` pawn positions).
  - Compute a distance matrix `dist[i][j]` storing the shortest knight moves between any two locations `i` and `j`. This is done by running a Breadth-First Search (BFS) from each of the `N+1` locations.
- **Step 2: Memoized Recursion (Top-Down DP)**
  - Define a recursive function `solve(prev_loc_idx, mask)`.
  - `prev_loc_idx`: The index of the knight's current location.
  - `mask`: A bitmask representing the set of available pawns.
  - Use a 2D array `memo[prev_loc_idx][mask]` to store results and avoid re-computation.
- **Algorithm for `solve(prev_loc_idx, mask)`:**
  1. **Base Case:** If `mask` is 0, return 0.
  2. **Memoization Check:** If `memo[prev_loc_idx][mask]` is already computed, return the stored value.
  3. **Determine Turn:** Calculate `num_captured = N - popcount(mask)`. If `num_captured` is even, it's Alice's turn (maximizer); otherwise, it's Bob's turn (minimizer).
  4. **Recursive Step:** Iterate through all available pawns `i` in the `mask`. Calculate the score for picking pawn `i` as `dist[prev_loc_idx][i] + solve(i, new_mask)`. Update the result based on whether the current player is a maximizer or a minimizer.
  5. Store the final result in `memo[prev_loc_idx][mask]` before returning.
- **Initial Call:** Start with `solve(N, (1 << N) - 1)`, where `N` is the index for the initial knight position.

# Solutions
### Java

```java
class Solution {
private
  Integer[][][] f;
private
  Integer[][][] dist;
private
  int[][] positions;
private
  final int[] dx = {1, 1, 2, 2, -1, -1, -2, -2};
private
  final int[] dy = {2, -2, 1, -1, 2, -2, 1, -1};
public
  int maxMoves(int kx, int ky, int[][] positions) {
    int n = positions.length;
    final int m = 50;
    dist = new Integer[n + 1][m][m];
    this.positions = positions;
    for (int i = 0; i <= n; ++i) {
      int x = i < n ? positions[i][0] : kx;
      int y = i < n ? positions[i][1] : ky;
      Deque<int[]> q = new ArrayDeque<>();
      q.offer(new int[]{x, y});
      for (int step = 1; !q.isEmpty(); ++step) {
        for (int k = q.size(); k > 0; --k) {
          var p = q.poll();
          int x1 = p[0], y1 = p[1];
          for (int j = 0; j < 8; ++j) {
            int x2 = x1 + dx[j], y2 = y1 + dy[j];
            if (x2 >= 0 && x2 < m && y2 >= 0 && y2 < m &&
                dist[i][x2][y2] == null) {
              dist[i][x2][y2] = step;
              q.offer(new int[]{x2, y2});
            }
          }
        }
      }
    }
    f = new Integer[n + 1][1 << n][2];
    return dfs(n, (1 << n) - 1, 1);
  }
private
  int dfs(int last, int state, int k) {
    if (state == 0) {
      return 0;
    }
    if (f[last][state][k] != null) {
      return f[last][state][k];
    }
    int res = k == 1 ? 0 : Integer.MAX_VALUE;
    for (int i = 0; i < positions.length; ++i) {
      int x = positions[i][0], y = positions[i][1];
      if ((state >> i & 1) == 1) {
        int t = dfs(i, state ^ (1 << i), k ^ 1) + dist[last][x][y];
        res = k == 1 ? Math.max(res, t) : Math.min(res, t);
      }
    }
    return f[last][state][k] = res;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxMoves(int kx, int ky, vector<vector<int>> &positions) {
    int n = positions.size();
    const int m = 50;
    const int dx[8] = {1, 1, 2, 2, -1, -1, -2, -2};
    const int dy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
    int dist[n + 1][m][m];
    memset(dist, -1, sizeof(dist));
    for (int i = 0; i <= n; ++i) {
      int x = (i < n) ? positions[i][0] : kx;
      int y = (i < n) ? positions[i][1] : ky;
      queue<pair<int, int>> q;
      q.push({x, y});
      dist[i][x][y] = 0;
      for (int step = 1; !q.empty(); ++step) {
        for (int k = q.size(); k > 0; --k) {
          auto [x1, y1] = q.front();
          q.pop();
          for (int j = 0; j < 8; ++j) {
            int x2 = x1 + dx[j], y2 = y1 + dy[j];
            if (x2 >= 0 && x2 < m && y2 >= 0 && y2 < m &&
                dist[i][x2][y2] == -1) {
              dist[i][x2][y2] = step;
              q.push({x2, y2});
            }
          }
        }
      }
    }
    int f[n + 1][1 << n][2];
    memset(f, -1, sizeof(f));
    auto dfs = [&](auto &&dfs, int last, int state, int k) -> int {
      if (state == 0) {
        return 0;
      }
      if (f[last][state][k] != -1) {
        return f[last][state][k];
      }
      int res = (k == 1) ? 0 : INT_MAX;
      for (int i = 0; i < positions.size(); ++i) {
        int x = positions[i][0], y = positions[i][1];
        if ((state >> i) & 1) {
          int t = dfs(dfs, i, state ^ (1 << i), k ^ 1) + dist[last][x][y];
          if (k == 1) {
            res = max(res, t);
          } else {
            res = min(res, t);
          }
        }
      }
      return f[last][state][k] = res;
    };
    return dfs(dfs, n, (1 << n) - 1, 1);
  }
};

```

### Python

```python
class Solution:
    def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int: @ cache def dfs(last: int, state: int, k: int) -> int: if state == 0: return 0 if k: res = 0 for i, (x, y) in enumerate(positions): if state >> i & 1: t = dfs(i, state ^ (1 << i), k ^ 1) + dist[last][x][y] if res < t: res = t return res else: res = inf for i, (x, y) in enumerate(positions): if state >> i & 1: t = dfs(i, state ^ (1 << i), k ^ 1) + dist[last][x][y] if res > t: res = t return res n = len(positions) m = 50 dist = [[[- 1] * m for _ in range(m)] for _ in range(n + 1)] dx = [1, 1, 2, 2, - 1, - 1, - 2, - 2] dy = [2, - 2, 1, - 1, 2, - 2, 1, - 1] positions . append([kx, ky]) for i, (x, y) in enumerate(positions): dist[i][x][y] = 0 q = deque([(x, y)]) step = 0 while q: step += 1 for _ in range(len(q)): x1, y1 = q . popleft() for j in range(8): x2, y2 = x1 + dx[j], y1 + dy[j] if 0 <= x2 < m and 0 <= y2 < m and dist[i][x2][y2] == - 1: dist[i][x2][y2] = step q . append((x2, y2)) ans = dfs(n, (1 << n) - 1, 1) dfs . cache_clear() return ans

```