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.
This approach involves using Breadth-First Search (BFS) to determine the minimum number of moves to capture each pawn from the knight's current position. By leveraging BFS, we can efficiently compute the shortest path on a chessboard grid (an unweighted graph scenario).
We then simulate the game where Alice and Bob take turns capturing pawns with Alice aiming to maximize and Bob aiming to minimize the total moves. However, Alice should choose the pawns in such a way as to delay Bob's choices (maximizing the advantage).
The code implements a function `maxMovesToKillAllPawns` which uses BFS to find the shortest path from the knight's current location to a destination pawn.
Initially, BFS calculates minimum moves for each pawn in the positions array. Then Alice and Bob choose pawns alternately while updating a counter of total moves, respecting their respective strategies. This solution considers a positional queue, visited list, and iterates through possible knight moves.
Python
JavaScript
Time Complexity: O(n * m), where n is the number of pawns and m is the size of BFS exploration on a 50 x 50 board.
Space Complexity: O(m) for BFS queue and visited set.
This approach uses the Minimax algorithm with alpha-beta pruning to simulate a zero-sum game between Alice and Bob. Alice aims to maximize moves while Bob minimizes them. The Minimax tree explores possible game states, progressively building and evaluating the optimal paths.
Alpha-beta pruning reduces computational workload by skipping non-optimal branches, effectively optimizing the decision process.
In this C++ solution, we implement the Minimax algorithm with recursive traversal and alpha-beta pruning. The `bfs` helper function computes move requirements between pawns, whereas the `minimax` function simulates the decision-making process by considering all possible outcomes along game trees.
Time Complexity: Exponential in number of pawns, simplified by pruning.
Space Complexity: Depends on recursion depth and storage of move results.
First, we preprocess the shortest distance for each pawn to any position on the chessboard and record it in the array dist, where dist[i][x][y] represents the shortest distance for the i-th pawn to the position (x, y).
Next, we design a function dfs(last, state, k), where last represents the number of the last pawn eaten, state represents the current state of the remaining pawns, and k represents whether it is Alice's or Bob's turn. The function returns the maximum number of moves for the current turn. The answer is dfs(n, 2^n-1, 1). Here, initially, the number of the last pawn eaten is n, which is also the position of the knight.
The specific implementation of the function dfs is as follows:
state = 0, it means there are no pawns left, return 0;k = 1, it means it is Alice's turn. We need to find a pawn such that the number of moves after eating this pawn is maximized, i.e., dfs(i, state \oplus 2^i, k \oplus 1) + dist[last][x][y];k = 0, it means it is Bob's turn. We need to find a pawn such that the number of moves after eating this pawn is minimized, i.e., dfs(i, state \oplus 2^i, k \oplus 1) + dist[last][x][y].To avoid repeated calculations, we use memoization, i.e., using a hash table to record the states that have already been calculated.
The time complexity is O(n times m^2 + 2^n times n^2), and the space complexity is O(n times m^2 + 2^n times n). Here, n and m represent the number of pawns and the size of the chessboard, respectively.
| Approach | Complexity |
|---|---|
| Approach 1: BFS for Shortest Path | Time Complexity: O(n * m), where n is the number of pawns and m is the size of BFS exploration on a 50 x 50 board. Space Complexity: O(m) for BFS queue and visited set. |
| Approach 2: Minimax Algorithm with Pruning | Time Complexity: Exponential in number of pawns, simplified by pruning. Space Complexity: Depends on recursion depth and storage of move results. |
| BFS + State Compression + Memoization | — |
| 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 |
Maximum Number of Moves to Kill All Pawns | Step By Step Detailed | Leetcode 3283 | codestorywithMIK • codestorywithMIK • 5,084 views views
Watch 6 more video solutions →Practice Maximum Number of Moves to Kill All Pawns with our built-in code editor and test cases.
Practice on FleetCode