LeetCode 3283 - Maximum Number of Moves to Kill All Pawns

LeetCode Problem 3283

Difficulty: 🔴 Hard
Topics: Array, Math, Bit Manipulation, Breadth-First Search, Game Theory, Bitmask

Solution

Problem Understanding

The problem gives us a 50 x 50 chessboard containing exactly one knight and up to 15 pawns. The knight starts at position (kx, ky), and every pawn is placed at one of the coordinates in positions.

Two players, Alice and Bob, alternate turns. Alice moves first. During a turn, the current player chooses one remaining pawn and moves the knight to that pawn using the minimum possible number of knight moves. Once the knight reaches the selected pawn, that pawn is removed from the board. Importantly, while traveling toward the chosen pawn, the knight may jump over or land near other pawns without capturing them. Only the selected pawn disappears.

The game continues until all pawns are removed.

The objective is unusual because the players optimize different things:

• Alice wants to maximize the total number of knight moves made throughout the entire game.
• Bob wants to minimize that same total.

Both players play optimally.

The return value is the final total number of moves after all pawns are captured.

A knight moves in the standard chess pattern:

• Two squares in one direction and one square perpendicular.
• There are eight possible moves from each cell.

The most important observation is that the board is small, but the game state space is not. There can be up to 15 pawns, meaning the number of subsets of pawns is:

$$2^{15} = 32768$$

This strongly suggests a bitmask dynamic programming solution.

Another key detail is that the knight can always eventually reach any square on a sufficiently large board, and the board here is large enough that all pawn positions are reachable.

Important edge cases include:

• Only one pawn exists.
• Multiple pawns are equally far away.
• A pawn that is physically close may still require many knight moves.
• The optimal strategy may intentionally choose a farther pawn to influence future game states.
• The knight's current position changes after every capture, so future costs depend on previous choices.

Approaches

Brute Force Approach

A brute force solution would try every possible order in which pawns can be captured.

If there are n pawns, there are:

$$n!$$

possible capture sequences.

For each sequence, we would:

1. Compute the knight distance between consecutive positions.
2. Alternate between maximizing and minimizing turns.
3. Evaluate the resulting total.

This approach is correct because it explicitly enumerates every legal game progression. However, it becomes infeasible very quickly.

For n = 15:

$$15! \approx 1.3 \times 10^{12}$$

which is completely impossible to search exhaustively.

Key Insight

The game has overlapping subproblems.

At any point, the future outcome depends only on:

1. Which pawns remain uncaptured.
2. The knight's current location.
3. Whose turn it is.

This naturally forms a minimax dynamic programming problem over subsets.

Another important insight is that movement costs between relevant positions never change. We only care about:

• Knight start position
• Pawn positions

So we can precompute all pairwise shortest knight distances using BFS.

After preprocessing distances, the game becomes:

• State = (mask, current_position, turn)
• Transition = choose next pawn
• Alice takes maximum
• Bob takes minimum

This reduces the exponential search into a manageable bitmask DP.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	$O(n! \cdot B)$	$O(n)$	Enumerates all capture orders
Optimal	$O((n+1)^2 \cdot 2500 + 2^n \cdot n^2)$	$O(2^n \cdot n)$	BFS preprocessing plus minimax DP

Here, B = 2500 represents the board size.

Algorithm Walkthrough

Step 1: Build the list of important positions

We only care about:

• The knight's starting position
• Every pawn position

Create an array:

points = [knight_start] + pawn_positions

If there are n pawns, then points has size n + 1.

Index 0 represents the knight start.

Indices 1..n represent pawns.

Step 2: Precompute knight distances with BFS

For every important position, run a BFS on the 50 x 50 board to compute the minimum knight moves to every cell.

Knight BFS works because:

• Every move has equal weight.
• BFS guarantees shortest paths in unweighted graphs.

The eight knight moves are:

(+2,+1), (+2,-1), (-2,+1), (-2,-1),
(+1,+2), (+1,-2), (-1,+2), (-1,-2)

From each BFS result, extract distances to every other important point.

Store them in:

dist[i][j]

where:

• i and j are indices in points
• dist[i][j] is the minimum knight moves between them

Step 3: Define the DP state

We use memoized minimax recursion.

Define:

dfs(mask, pos, alice_turn)

where:

• mask indicates which pawns are already captured
• pos is the current knight position index
• alice_turn indicates whose move it is

The function returns the optimal total moves from this state onward.

Step 4: Base case

If all pawns are captured:

mask == (1 << n) - 1

then no more moves remain.

Return 0.

Step 5: Try every remaining pawn

For every pawn not yet captured:

1. Compute its bit in the mask.
2. Compute movement cost from current position.
3. Recurse into the next state.

Transition:

cost + dfs(next_mask, next_position, next_turn)

Step 6: Apply minimax logic

If it is Alice's turn:

• Choose the maximum result.

If it is Bob's turn:

• Choose the minimum result.

This models optimal play.

Step 7: Start the recursion

Initial state:

mask = 0
position = 0
alice_turn = True

The knight begins at the starting coordinate and no pawns are captured yet.

Why it works

The DP state fully captures all information needed for future decisions:

• Current knight location
• Remaining pawns
• Current player

Since every move transitions to a strictly smaller remaining set, recursion eventually terminates.

The minimax recurrence correctly models optimal adversarial play:

• Alice maximizes total moves.
• Bob minimizes total moves.

Because BFS gives exact shortest knight distances, every transition cost is accurate. Therefore the DP computes the true optimal game result.

Python Solution

from typing import List
from collections import deque
from functools import lru_cache

class Solution:
    def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:
        knight_moves = [
            (2, 1),
            (2, -1),
            (-2, 1),
            (-2, -1),
            (1, 2),
            (1, -2),
            (-1, 2),
            (-1, -2),
        ]

        points = [[kx, ky]] + positions
        n = len(positions)

        def bfs(start_x: int, start_y: int) -> List[List[int]]:
            dist = [[-1] * 50 for _ in range(50)]
            queue = deque([(start_x, start_y)])
            dist[start_x][start_y] = 0

            while queue:
                x, y = queue.popleft()

                for dx, dy in knight_moves:
                    nx = x + dx
                    ny = y + dy

                    if 0 <= nx < 50 and 0 <= ny < 50:
                        if dist[nx][ny] == -1:
                            dist[nx][ny] = dist[x][y] + 1
                            queue.append((nx, ny))

            return dist

        size = n + 1
        pair_dist = [[0] * size for _ in range(size)]

        all_distances = []

        for x, y in points:
            all_distances.append(bfs(x, y))

        for i in range(size):
            for j in range(size):
                x, y = points[j]
                pair_dist[i][j] = all_distances[i][x][y]

        full_mask = (1 << n) - 1

        @lru_cache(None)
        def dfs(mask: int, pos: int, alice_turn: bool) -> int:
            if mask == full_mask:
                return 0

            if alice_turn:
                best = 0

                for pawn_idx in range(n):
                    if (mask >> pawn_idx) & 1:
                        continue

                    next_mask = mask | (1 << pawn_idx)
                    next_pos = pawn_idx + 1

                    moves = pair_dist[pos][next_pos]

                    best = max(
                        best,
                        moves + dfs(next_mask, next_pos, False)
                    )

                return best

            best = float("inf")

            for pawn_idx in range(n):
                if (mask >> pawn_idx) & 1:
                    continue

                next_mask = mask | (1 << pawn_idx)
                next_pos = pawn_idx + 1

                moves = pair_dist[pos][next_pos]

                best = min(
                    best,
                    moves + dfs(next_mask, next_pos, True)
                )

            return best

        return dfs(0, 0, True)

The implementation begins by defining the eight knight movement directions.

Next, it builds the points array that contains the knight start position followed by all pawn coordinates. This lets us treat every important location uniformly.

The bfs function computes shortest knight distances from one starting square to every square on the board. Since the board is only 50 x 50, each BFS is very small and efficient.

After running BFS from every important point, the solution constructs the pair_dist matrix. This gives constant-time access to the shortest knight distance between any two relevant positions.

The recursive dfs function performs the minimax dynamic programming. The bitmask tracks captured pawns, pos tracks the knight location, and alice_turn determines whether to maximize or minimize.

Memoization is critical because many different move orders can lead to the same state. Caching ensures each state is solved only once.

Finally, the recursion starts from the initial board configuration.

Go Solution

package main

import (
	"container/list"
	"math"
)

func maxMoves(kx int, ky int, positions [][]int) int {
	knightMoves := [][]int{
		{2, 1},
		{2, -1},
		{-2, 1},
		{-2, -1},
		{1, 2},
		{1, -2},
		{-1, 2},
		{-1, -2},
	}

	points := [][]int{{kx, ky}}
	points = append(points, positions...)

	n := len(positions)
	size := n + 1

	bfs := func(startX int, startY int) [][]int {
		dist := make([][]int, 50)
		for i := 0; i < 50; i++ {
			dist[i] = make([]int, 50)
			for j := 0; j < 50; j++ {
				dist[i][j] = -1
			}
		}

		queue := list.New()
		queue.PushBack([]int{startX, startY})
		dist[startX][startY] = 0

		for queue.Len() > 0 {
			front := queue.Front()
			queue.Remove(front)

			x := front.Value.([]int)[0]
			y := front.Value.([]int)[1]

			for _, move := range knightMoves {
				nx := x + move[0]
				ny := y + move[1]

				if nx >= 0 && nx < 50 && ny >= 0 && ny < 50 {
					if dist[nx][ny] == -1 {
						dist[nx][ny] = dist[x][y] + 1
						queue.PushBack([]int{nx, ny})
					}
				}
			}
		}

		return dist
	}

	allDistances := make([][][]int, size)

	for i, p := range points {
		allDistances[i] = bfs(p[0], p[1])
	}

	pairDist := make([][]int, size)
	for i := 0; i < size; i++ {
		pairDist[i] = make([]int, size)
		for j := 0; j < size; j++ {
			x := points[j][0]
			y := points[j][1]
			pairDist[i][j] = allDistances[i][x][y]
		}
	}

	fullMask := (1 << n) - 1

	type State struct {
		mask  int
		pos   int
		turn  int
	}

	memo := map[State]int{}

	var dfs func(mask int, pos int, aliceTurn int) int

	dfs = func(mask int, pos int, aliceTurn int) int {
		if mask == fullMask {
			return 0
		}

		state := State{mask, pos, aliceTurn}

		if val, exists := memo[state]; exists {
			return val
		}

		var best int

		if aliceTurn == 1 {
			best = 0

			for pawnIdx := 0; pawnIdx < n; pawnIdx++ {
				if (mask>>pawnIdx)&1 == 1 {
					continue
				}

				nextMask := mask | (1 << pawnIdx)
				nextPos := pawnIdx + 1

				moves := pairDist[pos][nextPos]

				candidate := moves + dfs(nextMask, nextPos, 0)

				if candidate > best {
					best = candidate
				}
			}
		} else {
			best = math.MaxInt32

			for pawnIdx := 0; pawnIdx < n; pawnIdx++ {
				if (mask>>pawnIdx)&1 == 1 {
					continue
				}

				nextMask := mask | (1 << pawnIdx)
				nextPos := pawnIdx + 1

				moves := pairDist[pos][nextPos]

				candidate := moves + dfs(nextMask, nextPos, 1)

				if candidate < best {
					best = candidate
				}
			}
		}

		memo[state] = best
		return best
	}

	return dfs(0, 0, 1)
}

The Go implementation follows the same structure as the Python solution, but there are several language-specific differences.

Go does not provide built-in memoization decorators, so the solution uses a custom map[State]int cache. A small struct is used as the memoization key.

The BFS queue uses container/list, which is the standard queue-like structure in Go's standard library.

Go also requires explicit initialization of all distance arrays because slices default to zero rather than -1.

Finally, the implementation uses integer constants 1 and 0 instead of booleans for turn tracking inside the memoization state.

Worked Examples

Example 1

Input:

kx = 1
ky = 1
positions = [[0,0]]

There is only one pawn.

The knight distance from (1,1) to (0,0) is 4.

Initial state:

Variable	Value
mask	0
position	knight start
turn	Alice

Alice must capture the only pawn.

Transition:

Captured Pawn	Distance	Next Mask
(0,0)	4	1

All pawns are captured afterward.

Total:

4

Example 2

Input:

kx = 0
ky = 2
positions = [[1,1],[2,2],[3,3]]

Suppose indices are:

Index	Position
0	knight start
1	(1,1)
2	(2,2)
3	(3,3)

Key distances:

From	To	Distance
start	(2,2)	2
(2,2)	(3,3)	2
(3,3)	(1,1)	4

Alice chooses (2,2) first because it leads to the best eventual outcome.

State transitions:

Turn	Chosen Pawn	Cost	Running Total
Alice	(2,2)	2	2
Bob	(3,3)	2	4
Alice	(1,1)	4	8

Final answer:

8

Example 3

Input:

kx = 0
ky = 0
positions = [[1,2],[2,4]]

Distances:

From	To	Distance
start	(1,2)	1
start	(2,4)	2
(2,4)	(1,2)	1

Alice intentionally chooses the farther pawn first.

Transitions:

Turn	Pawn	Cost	Total
Alice	(2,4)	2	2
Bob	(1,2)	1	3

Final answer:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	$O((n+1)\cdot 2500 + 2^n \cdot n^2)$	BFS preprocessing plus minimax DP
Space	$O(2^n \cdot n + (n+1)\cdot 2500)$	Memoization cache and BFS distance storage

The BFS preprocessing runs once for every important position. Since the board has only 2500 cells, this cost is very small.

The dominant factor is the DP. There are:

$$2^n \cdot n$$

possible states because each subset of pawns can pair with multiple knight locations.

From each state, we may iterate through all remaining pawns, producing the additional n factor.

Since n <= 15, this complexity is practical.

Test Cases

from typing import List

s = Solution()

assert s.maxMoves(1, 1, [[0, 0]]) == 4
# Single pawn case

assert s.maxMoves(0, 2, [[1, 1], [2, 2], [3, 3]]) == 8
# Official example with alternating optimal play

assert s.maxMoves(0, 0, [[1, 2], [2, 4]]) == 3
# Alice chooses farther pawn strategically

assert s.maxMoves(0, 0, [[1, 2]]) == 1
# Pawn reachable in one knight move

assert s.maxMoves(25, 25, [[24, 23], [26, 27]]) >= 2
# Symmetric nearby pawns

assert s.maxMoves(0, 0, [[49, 49]]) > 0
# Large board distance

assert s.maxMoves(10, 10, [[12, 11], [14, 12], [16, 13]]) >= 0
# Multiple chained knight moves

assert s.maxMoves(5, 5, [[6, 7], [7, 9], [9, 10], [11, 11]]) >= 0
# Larger state space

assert s.maxMoves(0, 0, [[1, 2], [2, 1]]) >= 2
# Multiple equally close pawns

assert s.maxMoves(20, 20, [[0, 0], [49, 49]]) >= 0
# Very distant pawn combinations

Test Summary

Test	Why
Single pawn	Smallest valid input
Official example 2	Validates minimax behavior
Official example 3	Validates strategic longer path
One knight move	Minimal movement distance
Symmetric positions	Tests equal-cost decisions
Corner to corner	Large-distance traversal
Chained positions	Multiple transitions
Larger state space	Tests DP branching
Equal nearby pawns	Tests tie handling
Distant combinations	Tests BFS correctness

Edge Cases

One important edge case is when there is only a single pawn. In this scenario, there is no real game tree because Alice has exactly one possible move. A buggy implementation might incorrectly apply minimax recursion or mishandle the base case. The solution handles this naturally because after the first capture the bitmask becomes fully set, causing the recursion to terminate immediately.

Another subtle edge case occurs when multiple pawns are equally close to the knight. Greedy logic can easily fail here because the locally optimal move may not lead to the globally optimal total. The minimax DP correctly evaluates every possible remaining game state instead of relying on immediate distance comparisons.

A third important edge case involves pawns that are physically near but require surprisingly many knight moves. Knight movement is non-Euclidean and unintuitive. For example, moving from (0,0) to (1,1) requires four knight moves. Implementations that attempt to estimate distances mathematically may fail. Using BFS guarantees exact shortest path distances for every pair of relevant positions.

Another important case is when Alice intentionally chooses a farther pawn first. A naive solution might assume the maximizing player should always take the largest immediate distance. However, future knight positions heavily influence later costs. The DP correctly evaluates the entire future game tree before deciding which move is optimal.

Finally, the implementation must correctly update the knight's current position after every capture. Forgetting this detail would cause all future distances to be computed from the original start square, producing completely incorrect answers. The DP state explicitly stores the current knight position index, ensuring all future transitions use the proper location.