3283. Maximum Number of Moves to Kill All Pawns
Problem Description
You have a 50x50 chessboard with one knight at position (kx, ky)
and several pawns at positions given in the array positions
. Two players, Alice and Bob, play a turn-based game starting with Alice.
Game Rules:
- On each turn, a player selects any remaining pawn on the board
- The knight moves to capture the selected pawn using the minimum number of moves possible
- While moving to capture the selected pawn, the knight can pass through other pawns without capturing them
- Only the selected pawn is removed from the board after being captured
- The knight moves in an L-shape pattern (2 squares in one direction and 1 square perpendicular, or vice versa)
Objective:
- Alice wants to maximize the total number of moves made by both players throughout the entire game
- Bob wants to minimize the total number of moves
- Both players play optimally
Your Task: Return the maximum total number of moves that Alice can achieve when both players play optimally.
Example of Knight Movement: A knight has 8 possible moves from any position - it can move 2 squares horizontally and 1 square vertically, or 2 squares vertically and 1 square horizontally, in any direction (as long as it stays within the board).
Key Points:
- Players can choose ANY pawn to capture on their turn, not necessarily the closest one
- The distance to capture each selected pawn is calculated as the minimum number of knight moves needed
- The game continues until all pawns are captured
- Alice goes first and wants the game to last as long as possible (more total moves)
- Bob wants the game to end quickly (fewer total moves)
Flowchart Walkthrough
First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:
Is it a graph?
- Yes: The chessboard can be viewed as a graph where each square is a node, and the knight's possible moves from each square represent edges. We need to find shortest paths between positions.
Is it a tree?
- No: The chessboard graph has cycles (a knight can return to its starting position through various paths), so it's not a tree structure.
Is the problem related to directed acyclic graphs?
- No: The knight movement graph is undirected (moves are reversible) and contains cycles.
Is the problem related to shortest paths?
- Yes: A core component of the problem is finding the minimum number of moves (shortest path) for the knight to reach each pawn from any position.
Is the graph Weighted?
- No: Each knight move counts as exactly 1 step, making this an unweighted graph problem where all edges have equal weight.
BFS
- Yes: For unweighted shortest path problems, BFS is the optimal choice.
Conclusion: The flowchart correctly identifies that BFS should be used for this problem. Specifically, BFS is used to precompute the shortest distances from each pawn's position (and the knight's initial position) to all other positions on the board. This preprocessing step creates the distance matrix dist[i][x][y]
that represents the minimum moves needed for a knight at position i
to reach any square (x, y)
. The BFS handles the knight's L-shaped movement pattern across the chessboard efficiently.
Intuition
The key insight is that this is a game theory problem where two players make alternating optimal moves. Alice wants to maximize the total moves while Bob wants to minimize them. This immediately suggests we need to model the game state and explore all possible decision trees.
Let's break down what we need:
-
Distance Information: We need to know how many moves it takes for the knight to reach any pawn from any position. Since the knight can be at different positions after capturing each pawn, we need to precompute distances from every pawn position (and the initial knight position) to every other position on the board. This is where BFS comes in - for each starting position, we run BFS to find the shortest path to all reachable squares.
-
Game State Representation: At any point in the game, we need to track:
- Which pawns are still on the board (we can use a bitmask for this)
- Where the knight currently is (the position of the last captured pawn)
- Whose turn it is (Alice or Bob)
-
Minimax Strategy: This is a classic minimax problem. When it's Alice's turn, she'll choose the pawn that leads to the maximum total moves. When it's Bob's turn, he'll choose the pawn that leads to the minimum total moves. Both players can see all remaining pawns and make the optimal choice.
-
Dynamic Programming with Memoization: Since the same game state (same remaining pawns, same knight position, same player's turn) can be reached through different sequences of moves, we'll encounter repeated subproblems. We can use memoization to avoid recalculating the optimal result for states we've already evaluated.
The solution combines these elements:
- Use BFS to precompute all distances (preprocessing step)
- Use recursive DFS with memoization to explore all possible game sequences
- Apply minimax logic: maximize on Alice's turn, minimize on Bob's turn
- Use bit manipulation to efficiently track which pawns remain
The beauty of this approach is that by precomputing distances and using memoization, we transform what could be an intractable problem into one that's solvable even with the game tree's exponential nature.
Learn more about Breadth-First Search, Math and Bitmask patterns.
Solution Approach
The solution implements a combination of BFS for preprocessing distances and DFS with memoization for game state exploration.
Step 1: Distance Preprocessing with BFS
First, we precompute the shortest distance from each pawn position (and the knight's initial position) to every square on the board:
dist = [[[-1] * m for _ in range(m)] for _ in range(n + 1)]
dist[i][x][y]
stores the minimum moves needed for a knight starting at pawni
's position to reach square(x, y)
- We allocate
n+1
positions because indexn
represents the knight's initial position
For each starting position, we run BFS:
- Initialize the starting position with distance 0
- Use a queue to explore all reachable positions level by level
- For each position, try all 8 possible knight moves:
dx = [1, 1, 2, 2, -1, -1, -2, -2]
anddy = [2, -2, 1, -1, 2, -2, 1, -1]
- Mark unvisited squares with their distance and add them to the queue
Step 2: Game State Exploration with DFS
The core game logic is implemented in the dfs(last, state, k)
function:
Parameters:
last
: Index of the last captured pawn (orn
for knight's initial position)state
: Bitmask representing remaining pawns (biti
is 1 if pawni
exists)k
: Turn indicator (1 for Alice, 0 for Bob)
Base Case:
- If
state == 0
, no pawns remain, return 0
Recursive Cases:
-
Alice's Turn (k = 1): Maximize total moves
res = 0 for each pawn i still on board: moves = dfs(i, state ^ (1 << i), k ^ 1) + dist[last][x][y] res = max(res, moves)
-
Bob's Turn (k = 0): Minimize total moves
res = inf for each pawn i still on board: moves = dfs(i, state ^ (1 << i), k ^ 1) + dist[last][x][y] res = min(res, moves)
Key Operations:
state >> i & 1
: Check if pawni
existsstate ^ (1 << i)
: Remove pawni
from the statek ^ 1
: Switch turns between playersdist[last][x][y]
: Add the cost of moving from last position to pawn at(x, y)
Step 3: Memoization
The @cache
decorator automatically memoizes the dfs
function, storing results for each unique (last, state, k)
combination. This prevents redundant calculations when the same game state is reached through different move sequences.
Step 4: Final Computation
The solution starts with:
ans = dfs(n, (1 << n) - 1, 1)
- Initial position:
n
(knight's starting position) - Initial state:
(1 << n) - 1
(all n pawns present) - Initial turn:
1
(Alice goes first)
The function returns the maximum total moves Alice can achieve when both players play optimally.
Ready to land your dream job?
Unlock your dream job with a 5-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach.
Setup:
- Board: 50x50
- Knight starts at position (0, 0)
- 2 pawns at positions: [(2, 1), (1, 2)]
Step 1: Distance Preprocessing
Using BFS, we calculate minimum knight moves from each position to all others:
From knight's initial position (0, 0):
- To pawn at (2, 1): 1 move (direct L-shape)
- To pawn at (1, 2): 1 move (direct L-shape)
From pawn position (2, 1):
- To (1, 2): 2 moves (e.g., (2,1) β (0,0) β (1,2))
From pawn position (1, 2):
- To (2, 1): 2 moves (e.g., (1,2) β (0,0) β (2,1))
So our distance array contains:
dist[2][2][1] = 1
(knight start to first pawn)dist[2][1][2] = 1
(knight start to second pawn)dist[0][1][2] = 2
(first pawn to second pawn)dist[1][2][1] = 2
(second pawn to first pawn)
Step 2: Game Tree Exploration
Initial call: dfs(2, 0b11, 1)
last = 2
(knight's initial position index)state = 0b11
(both pawns exist: bit 0 and bit 1 are set)k = 1
(Alice's turn)
Alice's Turn 1: Alice can choose either pawn. She evaluates both options:
Option A: Capture pawn 0 at (2, 1)
- Cost: 1 move to reach it
- Resulting state:
dfs(0, 0b10, 0) + 1
- Bob's turn with only pawn 1 remaining
Option B: Capture pawn 1 at (1, 2)
- Cost: 1 move to reach it
- Resulting state:
dfs(1, 0b01, 0) + 1
- Bob's turn with only pawn 0 remaining
Let's explore Option A further:
Bob's Turn (after Alice captures pawn 0):
- Current state:
dfs(0, 0b10, 0)
- Knight is at (2, 1), only pawn 1 at (1, 2) remains
- Bob must capture pawn 1: cost = 2 moves
- Total for this path: 1 + 2 = 3 moves
Similarly for Option B:
- Bob captures pawn 0 from position (1, 2): cost = 2 moves
- Total for this path: 1 + 2 = 3 moves
Step 3: Minimax Decision
Since both options lead to the same total (3 moves), Alice can choose either. The game proceeds:
- Alice captures first pawn (1 move)
- Bob captures remaining pawn (2 moves)
- Total: 3 moves
Key Observations:
- Even with just 2 pawns, we see how players' opposing goals create strategic depth
- Alice tries to set up situations where Bob must make longer moves
- Bob tries to minimize the damage by choosing shorter paths when possible
- Memoization helps when the same state (e.g., "knight at position X with pawns Y remaining") appears multiple times in different game branches
In larger examples with more pawns, the strategy becomes more complex. Alice might sacrifice immediate short moves to force Bob into positions where all remaining choices require long moves, maximizing the overall total.
Solution Implementation
1class Solution:
2 def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:
3 from collections import deque
4 from functools import cache
5 from typing import List
6
7 @cache
8 def minimax(last_position: int, remaining_pawns_mask: int, is_alice_turn: int) -> int:
9 """
10 Minimax algorithm with memoization to find optimal moves.
11
12 Args:
13 last_position: Index of the last visited position (knight's current position)
14 remaining_pawns_mask: Bitmask representing which pawns are still available
15 is_alice_turn: 1 if Alice's turn (maximizing), 0 if Bob's turn (minimizing)
16
17 Returns:
18 Optimal score for the current player
19 """
20 # Base case: no pawns left to capture
21 if remaining_pawns_mask == 0:
22 return 0
23
24 if is_alice_turn:
25 # Alice's turn: maximize the total distance
26 max_score = 0
27 for pawn_idx, (pawn_x, pawn_y) in enumerate(positions):
28 # Check if this pawn is still available
29 if remaining_pawns_mask >> pawn_idx & 1:
30 # Remove this pawn from the mask and recursively calculate
31 new_mask = remaining_pawns_mask ^ (1 << pawn_idx)
32 score = minimax(pawn_idx, new_mask, is_alice_turn ^ 1) + distances[last_position][pawn_x][pawn_y]
33 if score > max_score:
34 max_score = score
35 return max_score
36 else:
37 # Bob's turn: minimize the total distance
38 min_score = float('inf')
39 for pawn_idx, (pawn_x, pawn_y) in enumerate(positions):
40 # Check if this pawn is still available
41 if remaining_pawns_mask >> pawn_idx & 1:
42 # Remove this pawn from the mask and recursively calculate
43 new_mask = remaining_pawns_mask ^ (1 << pawn_idx)
44 score = minimax(pawn_idx, new_mask, is_alice_turn ^ 1) + distances[last_position][pawn_x][pawn_y]
45 if score < min_score:
46 min_score = score
47 return min_score
48
49 # Initialize variables
50 num_pawns = len(positions)
51 board_size = 50
52
53 # Create 3D array to store distances from each position to all board cells
54 # distances[i][x][y] = minimum knight moves from position i to cell (x, y)
55 distances = [[[-1] * board_size for _ in range(board_size)] for _ in range(num_pawns + 1)]
56
57 # Knight's possible moves (8 directions)
58 knight_moves_dx = [1, 1, 2, 2, -1, -1, -2, -2]
59 knight_moves_dy = [2, -2, 1, -1, 2, -2, 1, -1]
60
61 # Add knight's starting position to the positions list (at the end)
62 positions.append([kx, ky])
63
64 # BFS to compute minimum distances from each position to all board cells
65 for position_idx, (start_x, start_y) in enumerate(positions):
66 # Initialize BFS
67 distances[position_idx][start_x][start_y] = 0
68 queue = deque([(start_x, start_y)])
69 current_distance = 0
70
71 # BFS to find minimum distances
72 while queue:
73 current_distance += 1
74 # Process all cells at the current distance level
75 for _ in range(len(queue)):
76 curr_x, curr_y = queue.popleft()
77
78 # Try all 8 possible knight moves
79 for move_idx in range(8):
80 next_x = curr_x + knight_moves_dx[move_idx]
81 next_y = curr_y + knight_moves_dy[move_idx]
82
83 # Check if the new position is valid and unvisited
84 if (0 <= next_x < board_size and
85 0 <= next_y < board_size and
86 distances[position_idx][next_x][next_y] == -1):
87 distances[position_idx][next_x][next_y] = current_distance
88 queue.append((next_x, next_y))
89
90 # Start the game with Alice's turn
91 # Knight starts at position num_pawns (last index in positions)
92 # All pawns are available initially (bitmask with all bits set)
93 result = minimax(num_pawns, (1 << num_pawns) - 1, 1)
94
95 # Clear the cache to free memory
96 minimax.cache_clear()
97
98 return result
99
1class Solution {
2 // Memoization cache: [lastPosition][visitedState][currentPlayer]
3 private Integer[][][] memo;
4
5 // Precomputed distances: [fromPosition][toX][toY]
6 private Integer[][][] distances;
7
8 // Array of pawn positions
9 private int[][] positions;
10
11 // Knight movement directions (8 possible L-shaped moves)
12 private final int[] deltaX = {1, 1, 2, 2, -1, -1, -2, -2};
13 private final int[] deltaY = {2, -2, 1, -1, 2, -2, 1, -1};
14
15 public int maxMoves(int kx, int ky, int[][] positions) {
16 int numPawns = positions.length;
17 final int BOARD_SIZE = 50;
18
19 // Initialize distance array for all positions (pawns + knight)
20 distances = new Integer[numPawns + 1][BOARD_SIZE][BOARD_SIZE];
21 this.positions = positions;
22
23 // Precompute shortest distances from each position to all board cells using BFS
24 for (int i = 0; i <= numPawns; i++) {
25 // Get starting position (pawn position or initial knight position)
26 int startX = i < numPawns ? positions[i][0] : kx;
27 int startY = i < numPawns ? positions[i][1] : ky;
28
29 // BFS to compute distances from current position
30 Deque<int[]> queue = new ArrayDeque<>();
31 queue.offer(new int[] {startX, startY});
32 distances[i][startX][startY] = 0;
33
34 for (int step = 1; !queue.isEmpty(); step++) {
35 int levelSize = queue.size();
36 for (int k = 0; k < levelSize; k++) {
37 int[] current = queue.poll();
38 int currentX = current[0];
39 int currentY = current[1];
40
41 // Try all 8 possible knight moves
42 for (int j = 0; j < 8; j++) {
43 int nextX = currentX + deltaX[j];
44 int nextY = currentY + deltaY[j];
45
46 // Check if the move is valid and not visited
47 if (nextX >= 0 && nextX < BOARD_SIZE &&
48 nextY >= 0 && nextY < BOARD_SIZE &&
49 distances[i][nextX][nextY] == null) {
50 distances[i][nextX][nextY] = step;
51 queue.offer(new int[] {nextX, nextY});
52 }
53 }
54 }
55 }
56 }
57
58 // Initialize memoization array
59 memo = new Integer[numPawns + 1][1 << numPawns][2];
60
61 // Start DFS with knight at initial position, all pawns unvisited, Alice's turn
62 return dfs(numPawns, (1 << numPawns) - 1, 1);
63 }
64
65 /**
66 * DFS with memoization to find optimal game result
67 * @param lastPosition - index of last visited position (numPawns means knight's initial position)
68 * @param state - bitmask representing which pawns are still unvisited
69 * @param currentPlayer - 1 for Alice (maximizing), 0 for Bob (minimizing)
70 * @return optimal score for current player
71 */
72 private int dfs(int lastPosition, int state, int currentPlayer) {
73 // Base case: no pawns left to capture
74 if (state == 0) {
75 return 0;
76 }
77
78 // Check memoization cache
79 if (memo[lastPosition][state][currentPlayer] != null) {
80 return memo[lastPosition][state][currentPlayer];
81 }
82
83 // Initialize result based on current player
84 // Alice maximizes, Bob minimizes
85 int result = currentPlayer == 1 ? 0 : Integer.MAX_VALUE;
86
87 // Try capturing each remaining pawn
88 for (int i = 0; i < positions.length; i++) {
89 // Check if pawn i is still unvisited
90 if ((state >> i & 1) == 1) {
91 int pawnX = positions[i][0];
92 int pawnY = positions[i][1];
93
94 // Calculate score: recursive call + distance to reach this pawn
95 int newState = state ^ (1 << i); // Remove pawn i from state
96 int nextPlayer = currentPlayer ^ 1; // Switch player
97 int score = dfs(i, newState, nextPlayer) + distances[lastPosition][pawnX][pawnY];
98
99 // Update result based on current player's objective
100 if (currentPlayer == 1) {
101 result = Math.max(result, score); // Alice maximizes
102 } else {
103 result = Math.min(result, score); // Bob minimizes
104 }
105 }
106 }
107
108 // Store in cache and return
109 memo[lastPosition][state][currentPlayer] = result;
110 return result;
111 }
112}
113
1class Solution {
2public:
3 int maxMoves(int kx, int ky, vector<vector<int>>& positions) {
4 int numPositions = positions.size();
5 const int BOARD_SIZE = 50;
6
7 // Knight's 8 possible moves: (row_offset, col_offset)
8 const int knightMoveRow[8] = {1, 1, 2, 2, -1, -1, -2, -2};
9 const int knightMoveCol[8] = {2, -2, 1, -1, 2, -2, 1, -1};
10
11 // distances[i][row][col] = minimum knight moves from position i to (row, col)
12 // i < numPositions: from positions[i]
13 // i == numPositions: from initial knight position (kx, ky)
14 int distances[numPositions + 1][BOARD_SIZE][BOARD_SIZE];
15 memset(distances, -1, sizeof(distances));
16
17 // Calculate minimum distances using BFS for each starting position
18 for (int startPos = 0; startPos <= numPositions; ++startPos) {
19 // Get starting coordinates
20 int startRow = (startPos < numPositions) ? positions[startPos][0] : kx;
21 int startCol = (startPos < numPositions) ? positions[startPos][1] : ky;
22
23 // BFS to find minimum distances from starting position
24 queue<pair<int, int>> bfsQueue;
25 bfsQueue.push({startRow, startCol});
26 distances[startPos][startRow][startCol] = 0;
27
28 for (int currentDistance = 1; !bfsQueue.empty(); ++currentDistance) {
29 int levelSize = bfsQueue.size();
30 for (int i = 0; i < levelSize; ++i) {
31 auto [currentRow, currentCol] = bfsQueue.front();
32 bfsQueue.pop();
33
34 // Try all 8 knight moves
35 for (int move = 0; move < 8; ++move) {
36 int nextRow = currentRow + knightMoveRow[move];
37 int nextCol = currentCol + knightMoveCol[move];
38
39 // Check if the next position is valid and unvisited
40 if (nextRow >= 0 && nextRow < BOARD_SIZE &&
41 nextCol >= 0 && nextCol < BOARD_SIZE &&
42 distances[startPos][nextRow][nextCol] == -1) {
43 distances[startPos][nextRow][nextCol] = currentDistance;
44 bfsQueue.push({nextRow, nextCol});
45 }
46 }
47 }
48 }
49 }
50
51 // dp[lastPosition][visitedMask][currentPlayer]
52 // lastPosition: last visited position (numPositions means knight's initial position)
53 // visitedMask: bitmask of remaining unvisited positions
54 // currentPlayer: 1 for Alice (maximizing), 0 for Bob (minimizing)
55 int dp[numPositions + 1][1 << numPositions][2];
56 memset(dp, -1, sizeof(dp));
57
58 // Recursive function with memoization for minimax game tree
59 auto calculateOptimalMoves = [&](this auto&& calculateOptimalMoves,
60 int lastPosition,
61 int remainingMask,
62 int currentPlayer) -> int {
63 // Base case: no more positions to visit
64 if (remainingMask == 0) {
65 return 0;
66 }
67
68 // Return memoized result if already calculated
69 if (dp[lastPosition][remainingMask][currentPlayer] != -1) {
70 return dp[lastPosition][remainingMask][currentPlayer];
71 }
72
73 // Initialize result based on current player
74 // Alice (1) maximizes, Bob (0) minimizes
75 int result = (currentPlayer == 1) ? 0 : INT_MAX;
76
77 // Try visiting each remaining position
78 for (int nextPos = 0; nextPos < numPositions; ++nextPos) {
79 // Check if this position is still available
80 if ((remainingMask >> nextPos) & 1) {
81 int targetRow = positions[nextPos][0];
82 int targetCol = positions[nextPos][1];
83
84 // Calculate total moves: distance to next position + recursive result
85 int newMask = remainingMask ^ (1 << nextPos); // Remove current position from mask
86 int nextPlayer = currentPlayer ^ 1; // Switch player
87 int totalMoves = calculateOptimalMoves(nextPos, newMask, nextPlayer) +
88 distances[lastPosition][targetRow][targetCol];
89
90 // Update result based on current player's strategy
91 if (currentPlayer == 1) {
92 result = max(result, totalMoves); // Alice maximizes
93 } else {
94 result = min(result, totalMoves); // Bob minimizes
95 }
96 }
97 }
98
99 // Memoize and return result
100 return dp[lastPosition][remainingMask][currentPlayer] = result;
101 };
102
103 // Start game with knight at initial position, all positions unvisited, Alice's turn
104 return calculateOptimalMoves(numPositions, (1 << numPositions) - 1, 1);
105 }
106};
107
1function maxMoves(kx: number, ky: number, positions: number[][]): number {
2 const numPositions = positions.length;
3 const BOARD_SIZE = 50;
4
5 // Knight's 8 possible moves: (row_offset, col_offset)
6 const knightMoveRow = [1, 1, 2, 2, -1, -1, -2, -2];
7 const knightMoveCol = [2, -2, 1, -1, 2, -2, 1, -1];
8
9 // distances[i][row][col] = minimum knight moves from position i to (row, col)
10 // i < numPositions: from positions[i]
11 // i == numPositions: from initial knight position (kx, ky)
12 const distances: number[][][] = Array(numPositions + 1)
13 .fill(null)
14 .map(() => Array(BOARD_SIZE)
15 .fill(null)
16 .map(() => Array(BOARD_SIZE).fill(-1)));
17
18 // Calculate minimum distances using BFS for each starting position
19 for (let startPos = 0; startPos <= numPositions; startPos++) {
20 // Get starting coordinates
21 const startRow = startPos < numPositions ? positions[startPos][0] : kx;
22 const startCol = startPos < numPositions ? positions[startPos][1] : ky;
23
24 // BFS to find minimum distances from starting position
25 const bfsQueue: [number, number][] = [];
26 bfsQueue.push([startRow, startCol]);
27 distances[startPos][startRow][startCol] = 0;
28
29 let currentDistance = 1;
30 while (bfsQueue.length > 0) {
31 const levelSize = bfsQueue.length;
32 for (let i = 0; i < levelSize; i++) {
33 const [currentRow, currentCol] = bfsQueue.shift()!;
34
35 // Try all 8 knight moves
36 for (let move = 0; move < 8; move++) {
37 const nextRow = currentRow + knightMoveRow[move];
38 const nextCol = currentCol + knightMoveCol[move];
39
40 // Check if the next position is valid and unvisited
41 if (nextRow >= 0 && nextRow < BOARD_SIZE &&
42 nextCol >= 0 && nextCol < BOARD_SIZE &&
43 distances[startPos][nextRow][nextCol] === -1) {
44 distances[startPos][nextRow][nextCol] = currentDistance;
45 bfsQueue.push([nextRow, nextCol]);
46 }
47 }
48 }
49 currentDistance++;
50 }
51 }
52
53 // dp[lastPosition][visitedMask][currentPlayer]
54 // lastPosition: last visited position (numPositions means knight's initial position)
55 // visitedMask: bitmask of remaining unvisited positions
56 // currentPlayer: 1 for Alice (maximizing), 0 for Bob (minimizing)
57 const dp: Map<string, number> = new Map();
58
59 // Recursive function with memoization for minimax game tree
60 const calculateOptimalMoves = (lastPosition: number,
61 remainingMask: number,
62 currentPlayer: number): number => {
63 // Base case: no more positions to visit
64 if (remainingMask === 0) {
65 return 0;
66 }
67
68 // Create unique key for memoization
69 const key = `${lastPosition},${remainingMask},${currentPlayer}`;
70
71 // Return memoized result if already calculated
72 if (dp.has(key)) {
73 return dp.get(key)!;
74 }
75
76 // Initialize result based on current player
77 // Alice (1) maximizes, Bob (0) minimizes
78 let result = currentPlayer === 1 ? 0 : Number.MAX_SAFE_INTEGER;
79
80 // Try visiting each remaining position
81 for (let nextPos = 0; nextPos < numPositions; nextPos++) {
82 // Check if this position is still available
83 if ((remainingMask >> nextPos) & 1) {
84 const targetRow = positions[nextPos][0];
85 const targetCol = positions[nextPos][1];
86
87 // Calculate total moves: distance to next position + recursive result
88 const newMask = remainingMask ^ (1 << nextPos); // Remove current position from mask
89 const nextPlayer = currentPlayer ^ 1; // Switch player
90 const totalMoves = calculateOptimalMoves(nextPos, newMask, nextPlayer) +
91 distances[lastPosition][targetRow][targetCol];
92
93 // Update result based on current player's strategy
94 if (currentPlayer === 1) {
95 result = Math.max(result, totalMoves); // Alice maximizes
96 } else {
97 result = Math.min(result, totalMoves); // Bob minimizes
98 }
99 }
100 }
101
102 // Memoize and return result
103 dp.set(key, result);
104 return result;
105 };
106
107 // Start game with knight at initial position, all positions unvisited, Alice's turn
108 return calculateOptimalMoves(numPositions, (1 << numPositions) - 1, 1);
109}
110
Time and Space Complexity
Time Complexity: O(n Γ mΒ² + 2^n Γ nΒ²)
The time complexity consists of two main parts:
-
BFS preprocessing:
O(n Γ mΒ²)
- For each of the
n+1
starting positions (including the knight's initial position), we run a BFS to compute distances to all cells on the board - Each BFS explores all
m Γ m
cells on the board, wherem = 50
- Total:
O((n+1) Γ mΒ²) = O(n Γ mΒ²)
- For each of the
-
Dynamic programming with memoization:
O(2^n Γ nΒ²)
- The
dfs
function uses memoization with states defined by(last, state, k)
last
can haven+1
values (indices of positions including initial knight position)state
is a bitmask with2^n
possible values (subsets of pawns)k
alternates between 0 and 1 (Alice's turn or Bob's turn)- Total possible states:
O((n+1) Γ 2^n Γ 2) = O(n Γ 2^n)
- For each state, we iterate through up to
n
pawns to make the next move - Total:
O(n Γ 2^n Γ n) = O(2^n Γ nΒ²)
- The
Combined: O(n Γ mΒ² + 2^n Γ nΒ²)
Space Complexity: O(n Γ mΒ² + 2^n Γ n)
The space complexity consists of:
-
Distance array:
O(n Γ mΒ²)
- 3D array
dist
of size(n+1) Γ m Γ m
storing precomputed distances
- 3D array
-
Memoization cache:
O(2^n Γ n)
- The cache stores results for
O(n Γ 2^n)
different states (as analyzed above) - Each cached value stores a single integer
- The cache stores results for
-
Recursion stack:
O(n)
- Maximum recursion depth is
n
(number of pawns to collect)
- Maximum recursion depth is
Combined: O(n Γ mΒ² + 2^n Γ n)
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Incorrect Initial State Representation
A common mistake is incorrectly setting up the initial bitmask for available pawns. Developers might use (1 << n)
instead of (1 << n) - 1
, which would only set the nth bit instead of setting all n bits.
Wrong:
result = minimax(num_pawns, 1 << num_pawns, 1) # Only sets bit at position n
Correct:
result = minimax(num_pawns, (1 << num_pawns) - 1, 1) # Sets all bits from 0 to n-1
2. Modifying the Original Positions List
The code appends the knight's starting position to the original positions
list, which modifies the input. This could cause issues if the function is called multiple times or if the caller expects the list to remain unchanged.
Problem:
positions.append([kx, ky]) # Modifies the input list
Solution:
# Create a copy or use a separate list all_positions = positions + [[kx, ky]] # Or use positions without modification and handle knight position separately
3. Memory Overflow with Large State Spaces
The memoization cache can grow exponentially with the number of pawns. With n pawns, there are 2^n possible states, which can cause memory issues for large n.
Solution:
# Add cache size limit or clear cache periodically
from functools import lru_cache
@lru_cache(maxsize=100000) # Limit cache size
def minimax(...):
...
4. Off-by-One Errors in BFS Distance Calculation
The BFS implementation increments current_distance
at the beginning of each level, which could lead to confusion about when to use the distance value.
Potential Issue:
while queue:
current_distance += 1 # Incremented before processing
for _ in range(len(queue)):
# Process nodes at this level
Clearer Alternative:
while queue:
level_size = len(queue)
for _ in range(level_size):
curr_x, curr_y = queue.popleft()
# Process and add new nodes with distance = distances[position_idx][curr_x][curr_y] + 1
5. Not Handling Edge Cases
The code doesn't explicitly handle edge cases like:
- Empty positions list (no pawns)
- Knight starting position coinciding with a pawn position
Solution:
def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:
if not positions:
return 0
# Check if knight starts on any pawn position
# Handle this case appropriately
6. Inefficient Distance Array Initialization
Creating a 50x50 grid for each position might be wasteful if there are many positions but they're clustered in a small area.
Alternative Approach:
# Use dictionary to store only computed distances from collections import defaultdict distances = defaultdict(lambda: defaultdict(lambda: -1)) # Only compute and store distances that are actually needed
How does quick sort divide the problem into subproblems?
Recommended Readings
https assets algo monster cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell Breadth First Search BFS
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Bitmask and Dynamic Programming Bit manipulation is a crucial aspect of computer programming and one of the most powerful tools for bit manipulation is bitmasks Let's first understand what a bit is A bit is a binary digit It's the smallest piece of data in a computer and can be
Want a Structured Path to Master System Design Too? Donβt Miss This!