Watch 7 video solutions for Maximum Number of Moves to Kill All Pawns, a hard level problem involving Array, Math, Bit Manipulation. This walkthrough by codestorywithMIK has 5,084 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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.
Example 1:
Input: kx = 1, ky = 1, positions = [[0,0]]
Output: 4
Explanation:
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:
(2, 2) and captures it in two moves: (0, 2) -> (1, 4) -> (2, 2).(3, 3) and captures it in two moves: (2, 2) -> (4, 1) -> (3, 3).(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:
(2, 4) and captures it in two moves: (0, 0) -> (1, 2) -> (2, 4). Note that the pawn at (1, 2) is not captured.(1, 2) and captures it in one move: (2, 4) -> (1, 2).
Constraints:
0 <= kx, ky <= 491 <= positions.length <= 15positions[i].length == 20 <= positions[i][0], positions[i][1] <= 49positions[i] are unique.positions[i] != [kx, ky] for all 0 <= i < positions.length.Problem Overview: A knight starts on a chessboard with several pawns placed on different cells. Each capture requires moving the knight using standard chess knight moves. Two players alternately decide which pawn the knight captures next. Alice tries to maximize the total number of moves while Bob tries to minimize it. The task is to compute the final number of moves if both play optimally.
Approach 1: BFS for Shortest Path Precomputation (O((P+1) * N2) time, O(N2) space)
The knight can reach a square through many paths, but the shortest path is what determines the move cost between captures. Run Breadth-First Search from the starting position and from every pawn to compute the minimum knight distance to every other pawn. BFS works well because each knight move has equal cost and the board can be treated as an unweighted graph. After this step you have a distance matrix where dist[i][j] represents the minimum moves from position i to pawn j. This preprocessing converts the board navigation problem into a smaller graph problem involving only the pawns. BFS runs in O(N2) per source on an N×N board and is implemented using a queue from Breadth-First Search.
Approach 2: Minimax with Bitmask DP (O(P * 2P) time, O(P * 2P) space)
Once distances between all relevant positions are known, the problem becomes a turn-based game over subsets of pawns. Represent the remaining pawns using a bitmask. The state can be defined as (currentPosition, mask, turn). Alice chooses the next pawn that maximizes the total distance traveled, while Bob chooses the one that minimizes it. Use a recursive minimax search with memoization to avoid recomputing states. For each remaining pawn in the mask, add the precomputed BFS distance and recurse on the new state. Memoizing by (position, mask) dramatically reduces the search space because there are at most P * 2^P unique states. This technique combines Game Theory with Bitmask DP to efficiently simulate optimal play.
Recommended for interviews: The expected solution combines BFS preprocessing with a minimax + bitmask dynamic programming search. BFS alone shows you understand shortest path on a grid, but the key insight is reducing the game to a subset DP problem. Interviewers usually look for the transition from board navigation to a compressed state graph and the use of memoization to keep the exponential search manageable.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS Shortest Path Precomputation | O((P+1) * N^2) | O(N^2) | When converting the chessboard into shortest distances between the knight and all pawns |
| Minimax with Bitmask DP | O(P * 2^P) | O(P * 2^P) | Optimal strategy simulation when players alternately maximize and minimize total moves |