Skip to main content
Talentd

Maximum Number of Moves to Kill All Pawns - Solution & Explanation

HardArrayMathBit ManipulationBreadth-First Search19 min readAsked at: Google
Practice this problem

Problem Statement

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 <= 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.

Approach Overview

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 1: Approach 1: BFS for Shortest Path

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Minimax Algorithm with Pruning

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.

Code

C++Java

C++

Java

Complexity

Time Complexity: Exponential in number of pawns, simplified by pruning.

Space Complexity: Depends on recursion depth and storage of move results.

Try this approach in the editor →

Approach 3: BFS + State Compression + Memoization

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:

  • If state = 0, it means there are no pawns left, return 0;
  • If 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];
  • If 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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
BFS Shortest Path PrecomputationO((P+1) * N^2)O(N^2)When converting the chessboard into shortest distances between the knight and all pawns
Minimax with Bitmask DPO(P * 2^P)O(P * 2^P)Optimal strategy simulation when players alternately maximize and minimize total moves

Video Solution

Maximum Number of Moves to Kill All Pawns | Step By Step Detailed | Leetcode 3283 | codestorywithMIK • codestorywithMIK • 5,358 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Maximum Number of Moves to Kill All Pawns easy or hard?
Maximum Number of Moves to Kill All Pawns is classified as a Hard problem. It combines multiple advanced techniques: BFS for shortest paths, bitmask dynamic programming for subset states, and minimax game theory for optimal decision making. Recognizing that the board movement can be precomputed with BFS is the key step that simplifies the problem.
Maximum Number of Moves to Kill All Pawns Python/Java solution
Python and Java implementations typically start by running BFS from each relevant position to compute knight distances. After building the distance matrix, a recursive minimax with memoization explores all subsets of pawns. Python often uses functools.lru_cache for DP, while Java implementations store results in a DP array indexed by position and bitmask.
How to solve Maximum Number of Moves to Kill All Pawns in O(P * 2^P)?
First run BFS from the knight's start position and from each pawn to compute all pairwise knight distances. Then represent the remaining pawns as a bitmask and run a minimax recursion. At each step choose a pawn to capture, add the BFS distance, and recurse on the new mask. Memoization ensures each (position, mask) state is computed once, giving O(P * 2^P) DP complexity.
What is the best approach for Maximum Number of Moves to Kill All Pawns?
The most effective solution combines BFS shortest-path preprocessing with a minimax search using bitmask dynamic programming. BFS computes the minimum knight distance between the start position and every pawn, and between each pair of pawns. Minimax with memoization then simulates optimal play where Alice maximizes total moves and Bob minimizes them. The DP state space is roughly O(P * 2^P).
Is Maximum Number of Moves to Kill All Pawns asked at Google/Amazon/Meta?
Problems combining BFS preprocessing with bitmask DP and minimax game strategy appear frequently in interviews at companies like Google, Amazon, and Meta. They test graph traversal, state compression, and game-theory reasoning in one problem. Candidates are expected to identify the BFS distance reduction and the DP over subsets.
What data structure is used in Maximum Number of Moves to Kill All Pawns?
The solution uses a queue for BFS traversal on the chessboard grid, arrays or matrices for storing pairwise distances, and a hash map or DP table for memoizing minimax states. Bitmasks represent subsets of remaining pawns efficiently, enabling fast state transitions in the dynamic programming search.
What is the time complexity of Maximum Number of Moves to Kill All Pawns?
The total complexity comes from two parts. BFS preprocessing takes O((P+1) * N^2) on an N×N board to compute knight distances from the start and each pawn. The minimax bitmask DP explores at most O(P * 2^P) states with memoization, making the overall solution feasible even when the number of pawns is around 15.

Ready to solve this problem?

Practice Maximum Number of Moves to Kill All Pawns with our built-in code editor and test cases.

Practice on FleetCode
Previous

Check Knight Tour Configuration

Next

Knight Probability in Chessboard