Facebook Pixel

3283. Maximum Number of Moves to Kill All Pawns

HardBit ManipulationBreadth-First SearchArrayMathBitmaskGame Theory
Leetcode Link

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.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

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:

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

  2. 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)

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

  4. 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 pawn i's position to reach square (x, y)
  • We allocate n+1 positions because index n 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] and dy = [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 (or n for knight's initial position)
  • state: Bitmask representing remaining pawns (bit i is 1 if pawn i exists)
  • k: Turn indicator (1 for Alice, 0 for Bob)

Base Case:

  • If state == 0, no pawns remain, return 0

Recursive Cases:

  1. 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)

  2. 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 pawn i exists
  • state ^ (1 << i): Remove pawn i from the state
  • k ^ 1: Switch turns between players
  • dist[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 Evaluator

Example 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:

  1. Alice captures first pawn (1 move)
  2. Bob captures remaining pawn (2 moves)
  3. 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:

  1. 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, where m = 50
    • Total: O((n+1) × m²) = O(n × m²)

  2. Dynamic programming with memoization: O(2^n × n²)

    • The dfs function uses memoization with states defined by (last, state, k)
    • last can have n+1 values (indices of positions including initial knight position)
    • state is a bitmask with 2^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²)

Combined: O(n × m² + 2^n × n²)

Space Complexity: O(n × m² + 2^n × n)

The space complexity consists of:

  1. Distance array: O(n × m²)

    • 3D array dist of size (n+1) × m × m storing precomputed distances

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

  3. Recursion stack: O(n)

    • Maximum recursion depth is n (number of pawns to collect)

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
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which data structure is used in a depth first search?

Recommended Readings

BFS Fundamentals

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 Basics

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 Intro

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!

Load More