Maximum Number of Moves to Kill All Pawns
HardUpdated: Aug 2, 2025
Practice on:
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.
Examples
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.
Solution
Method 1 – Minimax + BFS (Game Theory)
Intuition
This is a two-player minimax game where Alice tries to maximize and Bob tries to minimize the total number of moves. For each state (knight position, remaining pawns, turn), recursively try all possible pawn captures, using BFS to compute the minimum moves to each pawn, and alternate turns. Memoize states for efficiency.
Approach
- Use BFS to compute the minimum number of knight moves from the current position to each pawn.
- Use bitmask to represent the set of remaining pawns.
- Use minimax recursion: if it's Alice's turn, maximize the total moves; if Bob's, minimize.
- Memoize the result for each (knight position, remaining pawns, turn).
- Try all possible next pawn captures for the current player.
- Return the optimal total moves.
Code
C++
#include <vector>
#include <queue>
#include <tuple>
#include <unordered_map>
using namespace std;
class Solution {
public:
int maxMoves(int kx, int ky, vector<vector<int>>& positions) {
int n = positions.size();
vector<pair<int, int>> pawns;
for (auto& p : positions) pawns.emplace_back(p[0], p[1]);
vector<vector<int>> dist(n+1, vector<int>(n, 0));
auto bfs = [&](int sx, int sy) -> vector<int> {
vector<vector<int>> d(50, vector<int>(50, -1));
queue<pair<int, int>> q;
q.emplace(sx, sy);
d[sx][sy] = 0;
vector<int> res(n);
int dx[8] = {-2,-2,-1,-1,1,1,2,2}, dy[8] = {-1,1,-2,2,-2,2,-1,1};
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
for (int k = 0; k < 8; ++k) {
int nx = x + dx[k], ny = y + dy[k];
if (nx >= 0 && nx < 50 && ny >= 0 && ny < 50 && d[nx][ny] == -1) {
d[nx][ny] = d[x][y] + 1;
q.emplace(nx, ny);
}
}
}
for (int i = 0; i < n; ++i) res[i] = d[pawns[i].first][pawns[i].second];
return res;
};
dist[0] = bfs(kx, ky);
for (int i = 0; i < n; ++i) dist[i+1] = bfs(pawns[i].first, pawns[i].second);
unordered_map<long long, int> memo;
function<int(int, int, int, bool)> dfs = [&](int pos, int mask, int turn, bool alice) -> int {
long long key = ((long long)pos << 16) | (mask << 1) | alice;
if (memo.count(key)) return memo[key];
int best = alice ? -1e9 : 1e9;
bool any = false;
for (int i = 0; i < n; ++i) {
if (!(mask & (1 << i))) continue;
int d = dist[pos][i];
if (d < 0) continue;
any = true;
int next = dfs(i+1, mask ^ (1 << i), turn+1, !alice) + d;
if (alice) best = max(best, next);
else best = min(best, next);
}
if (!any) return 0;
return memo[key] = best;
};
return dfs(0, (1<<n)-1, 0, true);
}
};
Go
func maxMoves(kx int, ky int, positions [][]int) int {
n := len(positions)
pawns := make([][2]int, n)
for i, p := range positions {
pawns[i] = [2]int{p[0], p[1]}
}
// Distance matrix: dist[i][j] = distance from position i to pawn j
dist := make([][]int, n+1)
for i := range dist {
dist[i] = make([]int, n)
}
// BFS to compute minimum knight moves
bfs := func(sx, sy int) []int {
d := make([][]int, 50)
for i := range d {
d[i] = make([]int, 50)
for j := range d[i] {
d[i][j] = -1
}
}
queue := [][2]int{{sx, sy}}
d[sx][sy] = 0
res := make([]int, n)
dx := []int{-2, -2, -1, -1, 1, 1, 2, 2}
dy := []int{-1, 1, -2, 2, -2, 2, -1, 1}
for len(queue) > 0 {
curr := queue[0]
queue = queue[1:]
x, y := curr[0], curr[1]
for k := 0; k < 8; k++ {
nx, ny := x+dx[k], y+dy[k]
if nx >= 0 && nx < 50 && ny >= 0 && ny < 50 && d[nx][ny] == -1 {
d[nx][ny] = d[x][y] + 1
queue = append(queue, [2]int{nx, ny})
}
}
}
for i := 0; i < n; i++ {
res[i] = d[pawns[i][0]][pawns[i][1]]
}
return res
}
// Compute distances from initial knight position and each pawn position
dist[0] = bfs(kx, ky)
for i := 0; i < n; i++ {
dist[i+1] = bfs(pawns[i][0], pawns[i][1])
}
// Memoization map
memo := make(map[int64]int)
// DFS with memoization
var dfs func(int, int, bool) int
dfs = func(pos, mask int, alice bool) int {
key := int64(pos)<<16 | int64(mask)<<1
if alice {
key |= 1
}
if val, exists := memo[key]; exists {
return val
}
var best int
if alice {
best = -1e9
} else {
best = 1e9
}
anyMove := false
for i := 0; i < n; i++ {
if (mask & (1 << i)) == 0 {
continue
}
d := dist[pos][i]
if d < 0 {
continue
}
anyMove = true
nextVal := dfs(i+1, mask^(1<<i), !alice) + d
if alice {
best = max(best, nextVal)
} else {
best = min(best, nextVal)
}
}
if !anyMove {
memo[key] = 0
return 0
}
memo[key] = best
return best
}
return dfs(0, (1<<n)-1, true)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
Java
import java.util.*;
class Solution {
public int maxMoves(int kx, int ky, int[][] positions) {
int n = positions.length;
int[][] pawns = new int[n][2];
for (int i = 0; i < n; i++) {
pawns[i][0] = positions[i][0];
pawns[i][1] = positions[i][1];
}
// Distance matrix: dist[i][j] = distance from position i to pawn j
int[][] dist = new int[n + 1][n];
// BFS to compute minimum knight moves
int[] bfs(int sx, int sy) {
int[][] d = new int[50][50];
for (int i = 0; i < 50; i++) {
Arrays.fill(d[i], -1);
}
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{sx, sy});
d[sx][sy] = 0;
int[] res = new int[n];
int[] dx = {-2, -2, -1, -1, 1, 1, 2, 2};
int[] dy = {-1, 1, -2, 2, -2, 2, -1, 1};
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int x = curr[0], y = curr[1];
for (int k = 0; k < 8; k++) {
int nx = x + dx[k], ny = y + dy[k];
if (nx >= 0 && nx < 50 && ny >= 0 && ny < 50 && d[nx][ny] == -1) {
d[nx][ny] = d[x][y] + 1;
queue.offer(new int[]{nx, ny});
}
}
}
for (int i = 0; i < n; i++) {
res[i] = d[pawns[i][0]][pawns[i][1]];
}
return res;
}
// Compute distances from initial knight position and each pawn position
dist[0] = bfs(kx, ky);
for (int i = 0; i < n; i++) {
dist[i + 1] = bfs(pawns[i][0], pawns[i][1]);
}
// Memoization map
Map<Long, Integer> memo = new HashMap<>();
return dfs(0, (1 << n) - 1, true, dist, memo, n);
}
private int dfs(int pos, int mask, boolean alice, int[][] dist, Map<Long, Integer> memo, int n) {
long key = ((long) pos << 16) | (mask << 1L) | (alice ? 1L : 0L);
if (memo.containsKey(key)) {
return memo.get(key);
}
int best = alice ? Integer.MIN_VALUE : Integer.MAX_VALUE;
boolean anyMove = false;
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) == 0) continue;
int d = dist[pos][i];
if (d < 0) continue;
anyMove = true;
int nextVal = dfs(i + 1, mask ^ (1 << i), !alice, dist, memo, n) + d;
if (alice) {
best = Math.max(best, nextVal);
} else {
best = Math.min(best, nextVal);
}
}
if (!anyMove) {
memo.put(key, 0);
return 0;
}
memo.put(key, best);
return best;
}
}
Kotlin
import java.util.*
import kotlin.math.*
class Solution {
fun maxMoves(kx: Int, ky: Int, positions: Array<IntArray>): Int {
val n = positions.size
val pawns = Array(n) { i -> intArrayOf(positions[i][0], positions[i][1]) }
// Distance matrix: dist[i][j] = distance from position i to pawn j
val dist = Array(n + 1) { IntArray(n) }
// BFS to compute minimum knight moves
fun bfs(sx: Int, sy: Int): IntArray {
val d = Array(50) { IntArray(50) { -1 } }
val queue: Queue<Pair<Int, Int>> = LinkedList()
queue.offer(Pair(sx, sy))
d[sx][sy] = 0
val res = IntArray(n)
val dx = intArrayOf(-2, -2, -1, -1, 1, 1, 2, 2)
val dy = intArrayOf(-1, 1, -2, 2, -2, 2, -1, 1)
while (queue.isNotEmpty()) {
val (x, y) = queue.poll()
for (k in 0 until 8) {
val nx = x + dx[k]
val ny = y + dy[k]
if (nx in 0 until 50 && ny in 0 until 50 && d[nx][ny] == -1) {
d[nx][ny] = d[x][y] + 1
queue.offer(Pair(nx, ny))
}
}
}
for (i in 0 until n) {
res[i] = d[pawns[i][0]][pawns[i][1]]
}
return res
}
// Compute distances from initial knight position and each pawn position
dist[0] = bfs(kx, ky)
for (i in 0 until n) {
dist[i + 1] = bfs(pawns[i][0], pawns[i][1])
}
// Memoization map
val memo = mutableMapOf<Long, Int>()
fun dfs(pos: Int, mask: Int, alice: Boolean): Int {
val key = (pos.toLong() shl 16) or (mask.toLong() shl 1) or if (alice) 1L else 0L
if (key in memo) {
return memo[key]!!
}
var best = if (alice) Int.MIN_VALUE else Int.MAX_VALUE
var anyMove = false
for (i in 0 until n) {
if ((mask and (1 shl i)) == 0) continue
val d = dist[pos][i]
if (d < 0) continue
anyMove = true
val nextVal = dfs(i + 1, mask xor (1 shl i), !alice) + d
if (alice) {
best = max(best, nextVal)
} else {
best = min(best, nextVal)
}
}
if (!anyMove) {
memo[key] = 0
return 0
}
memo[key] = best
return best
}
return dfs(0, (1 shl n) - 1, true)
}
}
Python
from collections import deque
from functools import cache
class Solution:
def maxMoves(self, kx: int, ky: int, positions: list[list[int]]) -> int:
n = len(positions)
pawns = positions
def bfs(sx, sy):
d = [[-1]*50 for _ in range(50)]
q = deque([(sx, sy)])
d[sx][sy] = 0
res = [0]*n
dx = [-2,-2,-1,-1,1,1,2,2]
dy = [-1,1,-2,2,-2,2,-1,1]
while q:
x, y = q.popleft()
for k in range(8):
nx, ny = x+dx[k], y+dy[k]
if 0<=nx<50 and 0<=ny<50 and d[nx][ny]==-1:
d[nx][ny] = d[x][y]+1
q.append((nx, ny))
for i in range(n):
res[i] = d[pawns[i][0]][pawns[i][1]]
return res
dist = [bfs(kx, ky)] + [bfs(p[0], p[1]) for p in pawns]
@cache
def dfs(pos, mask, alice):
best = -1e9 if alice else 1e9
any_move = False
for i in range(n):
if not (mask & (1<<i)): continue
d = dist[pos][i]
if d < 0: continue
any_move = True
next_val = dfs(i+1, mask ^ (1<<i), not alice) + d
if alice:
best = max(best, next_val)
else:
best = min(best, next_val)
if not any_move:
return 0
return best
return dfs(0, (1<<n)-1, True)
Rust
use std::collections::{HashMap, VecDeque};
impl Solution {
pub fn max_moves(kx: i32, ky: i32, positions: Vec<Vec<i32>>) -> i32 {
let n = positions.len();
let pawns: Vec<(i32, i32)> = positions.iter().map(|p| (p[0], p[1])).collect();
// Distance matrix: dist[i][j] = distance from position i to pawn j
let mut dist = vec![vec![0; n]; n + 1];
// BFS to compute minimum knight moves
let bfs = |sx: i32, sy: i32| -> Vec<i32> {
let mut d = vec![vec![-1; 50]; 50];
let mut queue = VecDeque::new();
queue.push_back((sx, sy));
d[sx as usize][sy as usize] = 0;
let mut res = vec![0; n];
let dx = [-2, -2, -1, -1, 1, 1, 2, 2];
let dy = [-1, 1, -2, 2, -2, 2, -1, 1];
while let Some((x, y)) = queue.pop_front() {
for k in 0..8 {
let nx = x + dx[k];
let ny = y + dy[k];
if nx >= 0 && nx < 50 && ny >= 0 && ny < 50 {
let (nx_u, ny_u) = (nx as usize, ny as usize);
if d[nx_u][ny_u] == -1 {
d[nx_u][ny_u] = d[x as usize][y as usize] + 1;
queue.push_back((nx, ny));
}
}
}
}
for i in 0..n {
res[i] = d[pawns[i].0 as usize][pawns[i].1 as usize];
}
res
};
// Compute distances from initial knight position and each pawn position
dist[0] = bfs(kx, ky);
for i in 0..n {
dist[i + 1] = bfs(pawns[i].0, pawns[i].1);
}
// Memoization map
let mut memo = HashMap::new();
fn dfs(
pos: usize,
mask: i32,
alice: bool,
dist: &Vec<Vec<i32>>,
memo: &mut HashMap<i64, i32>,
n: usize,
) -> i32 {
let key = ((pos as i64) << 16) | ((mask as i64) << 1) | if alice { 1 } else { 0 };
if let Some(&val) = memo.get(&key) {
return val;
}
let mut best = if alice { i32::MIN } else { i32::MAX };
let mut any_move = false;
for i in 0..n {
if (mask & (1 << i)) == 0 {
continue;
}
let d = dist[pos][i];
if d < 0 {
continue;
}
any_move = true;
let next_val = dfs(i + 1, mask ^ (1 << i), !alice, dist, memo, n) + d;
if alice {
best = best.max(next_val);
} else {
best = best.min(next_val);
}
}
if !any_move {
memo.insert(key, 0);
return 0;
}
memo.insert(key, best);
best
}
dfs(0, (1 << n) - 1, true, &dist, &mut memo, n)
}
}
TypeScript
function maxMoves(kx: number, ky: number, positions: number[][]): number {
const n = positions.length;
const pawns: [number, number][] = positions.map(p => [p[0], p[1]]);
// Distance matrix: dist[i][j] = distance from position i to pawn j
const dist: number[][] = Array(n + 1).fill(null).map(() => Array(n).fill(0));
// BFS to compute minimum knight moves
const bfs = (sx: number, sy: number): number[] => {
const d: number[][] = Array(50).fill(null).map(() => Array(50).fill(-1));
const queue: [number, number][] = [[sx, sy]];
d[sx][sy] = 0;
const res: number[] = Array(n).fill(0);
const dx = [-2, -2, -1, -1, 1, 1, 2, 2];
const dy = [-1, 1, -2, 2, -2, 2, -1, 1];
while (queue.length > 0) {
const [x, y] = queue.shift()!;
for (let k = 0; k < 8; k++) {
const nx = x + dx[k];
const ny = y + dy[k];
if (nx >= 0 && nx < 50 && ny >= 0 && ny < 50 && d[nx][ny] === -1) {
d[nx][ny] = d[x][y] + 1;
queue.push([nx, ny]);
}
}
}
for (let i = 0; i < n; i++) {
res[i] = d[pawns[i][0]][pawns[i][1]];
}
return res;
};
// Compute distances from initial knight position and each pawn position
dist[0] = bfs(kx, ky);
for (let i = 0; i < n; i++) {
dist[i + 1] = bfs(pawns[i][0], pawns[i][1]);
}
// Memoization map
const memo = new Map<string, number>();
const dfs = (pos: number, mask: number, alice: boolean): number => {
const key = `${pos},${mask},${alice}`;
if (memo.has(key)) {
return memo.get(key)!;
}
let best = alice ? -Infinity : Infinity;
let anyMove = false;
for (let i = 0; i < n; i++) {
if ((mask & (1 << i)) === 0) continue;
const d = dist[pos][i];
if (d < 0) continue;
anyMove = true;
const nextVal = dfs(i + 1, mask ^ (1 << i), !alice) + d;
if (alice) {
best = Math.max(best, nextVal);
} else {
best = Math.min(best, nextVal);
}
}
if (!anyMove) {
memo.set(key, 0);
return 0;
}
memo.set(key, best);
return best;
};
return dfs(0, (1 << n) - 1, true);
}
Complexity
- ⏰ Time complexity:
O(n! * n^2), wherenis the number of pawns (≤ 15), due to all permutations and BFS for each pawn. - 🧺 Space complexity:
O(n * 2^n), for memoization and distance tables.