Maximum Number of Moves to Kill All Pawns
HardPrompt
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.
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:
- 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 <= 491 <= positions.length <= 15positions[i].length == 20 <= positions[i][0], positions[i][1] <= 49- All
positions[i]are unique. - The input is generated such that
positions[i] != [kx, ky]for all0 <= i < positions.length.
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Define a recursive function
solve(current_knight_pos, remaining_pawns_mask, turn_number). - Base Case: If
remaining_pawns_maskis 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_scoreto a very small value for Alice or a very large value for Bob. - Iterate through each pawn
pthat is still available inremaining_pawns_mask. - For each available pawn
p:- Calculate the shortest distance
dfrom the knight's current position top's position using a Breadth-First Search (BFS). - Recursively call
solvefor the next state:solve(p's_pos, new_mask, turn_number + 1), wherenew_maskis the mask withpremoved. - The total score for choosing
pisd + recursive_score. - Update
best_scoreby taking the maximum (for Alice) or minimum (for Bob) of the currentbest_scoreand the calculated total score.
- Calculate the shortest distance
- Determine if it's Alice's (maximizer) or Bob's (minimizer) turn based on
- Return
best_score. - The initial call is made with the knight's starting position, a mask with all pawns present, and turn number 0.
Walkthrough
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:
- Base Case: If
remaining_pawns_maskis 0 (all pawns captured), the game ends, and we return 0. - Recursive Step:
- Determine the current player. If
turn_countis even, it's Alice's turn (maximizer). If odd, it's Bob's turn (minimizer). - Iterate through each pawn
ithat is still on the board (i-th bit in the mask is 1). - For each such pawn
iat(px, py):- Calculate the number of moves
mfor 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), wherenew_maskhas the i-th bit turned off. - The total score for this choice is
m + recursive_result.
- Calculate the number of moves
- If it's Alice's turn, she will choose the pawn
ithat maximizes this total score. - If it's Bob's turn, he will choose the pawn
ithat minimizes this total score.
- Determine the current player. If
The initial call would be solve(kx, ky, (1 << N) - 1, 0), where N is the number of pawns.
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 }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Step 1: Pre-computation of Distances
- Create a list of all
N+1locations (initial knight position +Npawn positions). - Compute a distance matrix
dist[i][j]storing the shortest knight moves between any two locationsiandj. This is done by running a Breadth-First Search (BFS) from each of theN+1locations.
- Create a list of all
- 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.
- Define a recursive function
- Algorithm for
solve(prev_loc_idx, mask):- Base Case: If
maskis 0, return 0. - Memoization Check: If
memo[prev_loc_idx][mask]is already computed, return the stored value. - Determine Turn: Calculate
num_captured = N - popcount(mask). Ifnum_capturedis even, it's Alice's turn (maximizer); otherwise, it's Bob's turn (minimizer). - Recursive Step: Iterate through all available pawns
iin themask. Calculate the score for picking pawniasdist[prev_loc_idx][i] + solve(i, new_mask). Update the result based on whether the current player is a maximizer or a minimizer. - Store the final result in
memo[prev_loc_idx][mask]before returning.
- Base Case: If
- Initial Call: Start with
solve(N, (1 << N) - 1), whereNis the index for the initial knight position.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}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); }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.