Facebook Pixel

3283. Maximum Number of Moves to Kill All Pawns

HardBit ManipulationBreadth-First SearchArrayMathBitmaskGame Theory
Leetcode Link

Problem Description

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. Each move is two cells in a cardinal direction, then one cell in an orthogonal direction.

Intuition

The problem can be tackled using a combination of Breadth-First Search (BFS) and dynamic programming with state compression and memoization. The key insight is to preprocess the shortest possible moves from the knight's position to any other position on the board for each pawn using BFS. Then, employ a recursive dynamic programming approach to explore the optimal strategy for both Alice and Bob.

The dynamic programming function dfs(last, state, k) represents the game's state, where last is the last captured pawn's index, state is a bitmask representing which pawns are still on the board, and k designates whose turn it is (Alice or Bob).

  • If state is zero, indicating no pawns are left, return 0 as no further moves are possible.
  • If it is Alice's turn (k = 1), she maximizes the number of moves by choosing the pawn that results in the highest possible total moves, including subsequent moves calculated recursively.
  • If it is Bob's turn (k = 0), his goal is to minimize the total moves by selecting the pawn that results in the fewest possible additional moves.

By using memoization to avoid recalculating results for previously encountered states, this approach efficiently determines the maximum total moves Alice can achieve under optimal play from both players.

Learn more about Breadth-First Search, Math and Bitmask patterns.

Solution Approach

The solution uses a combination of BFS for preprocessing distances and a DFS with memoization for optimal game strategy.

BFS for Distance Preprocessing

  1. Initialize dist array: Use a 3D array dist where dist[i][x][y] represents the minimum number of knight moves needed for the i-th pawn to reach position (x, y).

  2. Knight's Moves: Define the possible moves for a knight using arrays dx and dy.

  3. Process Each Pawn:

    • For each pawn (including the knight's starting position considered as an extra pawn), use a BFS starting from the pawn's position to calculate the shortest path to every other square on the board. This populates the dist array.

DFS with State Compression and Memoization

  1. Define dfs(last, state, k): This recursive function simulates the game:

    • last is the index of the last pawn captured.
    • state is a bitmask representing which pawns are still active.
    • k indicates the current player's turn (Alice or Bob).

  2. Base Case:

    • If state equals zero (meaning all pawns have been captured), return 0.

  3. Recursive Case for Alice (k = 1):

    • Set res to 0.
    • Iterate over each active pawn and simulate capturing that pawn.
    • Calculate the new state and use dist to get the number of moves from last to the current pawn.
    • Recursively call dfs for the new state with the turn switched to Bob, and update res to maximize the moves.

  4. Recursive Case for Bob (k = 0):

    • Set res to infinity.
    • Iterate over each active pawn similarly, but update res to minimize the moves.

  5. Memoization: Use a caching mechanism to store and reuse results of previously calculated states to optimize the recursion.

Execution

Calculate the answer by invoking dfs starting from the knight's initial position, with all pawns active and Alice's turn.

ans = dfs(n, (1 << n) - 1, 1)

Where n is the number of pawns, and (1 << n) - 1 represents all pawns being active in the beginning.

This technique leverages BFS for distance calculation and DFS with state compression for strategic decision-making in the game, ensuring that the solution is both optimal and efficient.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take a small example to illustrate the solution approach. Consider a 5 x 5 chessboard with a knight at position (2, 2) and two pawns at positions (0, 0) and (4, 4).

Step 1: BFS for Distance Preprocessing

  1. Distance Array Initialization:

    • We initialize a 3D dist array where dist[i][x][y] is the minimum number of moves the knight needs to travel from the i-th pawn's position (treated as sources) to (x, y) on the board. Here, i ranges from 0 to the number of pawns (3 in this example, counting the knight as the starting position).

  2. Possible Knight Moves:

    • A knight can move in 8 possible ways. Use dx = [2, 2, -2, -2, 1, 1, -1, -1] and dy = [1, -1, 1, -1, 2, -2, 2, -2] to represent these movements.

  3. BFS from Each Pawn:

    • Start a BFS from the knight's position (2, 2), and from each pawn position (0, 0) and (4, 4), storing results in dist for all positions the knight can reach.

Step 2: DFS with State Compression and Memoization

  1. Define the dfs Function:

    • The function dfs(last, state, k) will calculate the optimal moves. Here, last is the last captured pawn's index, state is a bitmask representing which pawns are still on the board, and k indicates whose turn it is (Alice's or Bob's).

  2. Initial Call:

    • We start with dfs(2, 0b11, 1) where 2 is the index representing the knight's starting position, 0b11 indicates both pawns are still on the board, and 1 indicates it's Alice's turn.

  3. Recursive Logic:

    • If state is 0, no pawns remain to be captured; return 0.
    • If it's Alice's turn (k = 1):
      • Iterate through each pawns' indices where the pawn is still active in state.
      • Calculate the moves from the last position to the current one using dist.
      • Update res to maximize the moves, calling dfs for the next state with Bob's turn.
    • If it's Bob's turn (k = 0):
      • Do the same iteration, aiming to minimize the moves.

  4. Memoization:

    • Store the results of dfs for each last, state, and k combination to avoid recalculating.

Step 3: Calculate Result

Invoke dfs to find the maximum total moves Alice can achieve:

n = 2  # Number of pawns
initial_state = (1 << n) - 1  # All pawns active
ans = dfs(2, initial_state, 1)

In this example, ans will hold the maximum total number of moves made during the game, assuming both players play optimally.

Solution Implementation

1from typing import List
2from functools import cache
3from collections import deque
4from math import inf
5
6class Solution:
7    def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:
8        @cache
9        def dfs(last: int, state: int, k: int) -> int:
10            # Base case: if no positions left, return 0
11            if state == 0:
12                return 0
13            if k:  # Player 1's turn (trying to maximize the score)
14                result = 0
15                for i, (x, y) in enumerate(positions):
16                    if state >> i & 1:  # Check if position i is part of the current state
17                        current_distance = dfs(i, state ^ (1 << i), k ^ 1) + distance[last][x][y]
18                        # Update result with the maximum distance
19                        if result < current_distance:
20                            result = current_distance
21                return result
22            else:  # Player 2's turn (trying to minimize the score)
23                result = inf
24                for i, (x, y) in enumerate(positions):
25                    if state >> i & 1:  # Check if position i is part of the current state
26                        current_distance = dfs(i, state ^ (1 << i), k ^ 1) + distance[last][x][y]
27                        # Update result with the minimum distance
28                        if result > current_distance:
29                            result = current_distance
30                return result
31
32        n = len(positions)
33        m = 50  # Board size (assuming a 50x50 grid)
34        # Initialize a 3D list to store distances
35        distance = [[[-1] * m for _ in range(m)] for _ in range(n + 1)]
36        # Directions for knight moves
37        dx = [1, 1, 2, 2, -1, -1, -2, -2]
38        dy = [2, -2, 1, -1, 2, -2, 1, -1]
39      
40        # Add knight's initial position to positions
41        positions.append([kx, ky])
42      
43        # Precompute distances from each position to every other position on the board
44        for i, (x, y) in enumerate(positions):
45            distance[i][x][y] = 0
46            queue = deque([(x, y)])
47            step = 0
48            while queue:
49                step += 1
50                for _ in range(len(queue)):
51                    current_x, current_y = queue.popleft()
52                    for j in range(8):  # Explore all knight's possible moves
53                        next_x, next_y = current_x + dx[j], current_y + dy[j]
54                        if 0 <= next_x < m and 0 <= next_y < m and distance[i][next_x][next_y] == -1:
55                            distance[i][next_x][next_y] = step
56                            queue.append((next_x, next_y))
57
58        # Starting DFS from knight's initial position
59        answer = dfs(n, (1 << n) - 1, 1)
60        dfs.cache_clear()
61        return answer
62
1import java.util.ArrayDeque;
2import java.util.Deque;
3
4class Solution {
5    // 3D array caches computed results for dynamic programming
6    private Integer[][][] dpCache; 
7    // 3D array to store distances between each knight position and the king
8    private Integer[][][] distances; 
9    // Positions of knights on the chess board
10    private int[][] positions;
11  
12    // Knight's possible moves on a chessboard
13    private final int[] dx = {1, 1, 2, 2, -1, -1, -2, -2}; 
14    private final int[] dy = {2, -2, 1, -1, 2, -2, 1, -1}; 
15
16    public int maxMoves(int kingX, int kingY, int[][] positions) {
17        int numOfKnights = positions.length;
18        final int boardSize = 50; // Define the size of the chess board
19      
20        distances = new Integer[numOfKnights + 1][boardSize][boardSize];
21        this.positions = positions;
22      
23        // Calculate shortest paths (distances) using BFS
24        for (int i = 0; i <= numOfKnights; ++i) {
25            int startX = i < numOfKnights ? positions[i][0] : kingX;
26            int startY = i < numOfKnights ? positions[i][1] : kingY;
27          
28            Deque<int[]> queue = new ArrayDeque<>();
29            queue.offer(new int[] { startX, startY });
30          
31            for (int step = 1; !queue.isEmpty(); ++step) {
32                for (int qSize = queue.size(); qSize > 0; --qSize) {
33                    var pos = queue.poll();
34                    int currentX = pos[0], currentY = pos[1];
35                  
36                    for (int j = 0; j < 8; ++j) {
37                        int nextX = currentX + dx[j], nextY = currentY + dy[j];
38                      
39                        if (nextX >= 0 && nextX < boardSize && nextY >= 0 && nextY < boardSize && distances[i][nextX][nextY] == null) {
40                            distances[i][nextX][nextY] = step;
41                            queue.offer(new int[] { nextX, nextY });
42                        }
43                    }
44                }
45            }
46        }
47      
48        // Initialize the memoization cache
49        dpCache = new Integer[numOfKnights + 1][1 << numOfKnights][2];
50      
51        // Start computation with all knights and king's turn
52        return dfs(numOfKnights, (1 << numOfKnights) - 1, 1);
53    }
54
55    // Depth-First Search with memoization to compute optimal moves
56    private int dfs(int lastKnight, int state, int turn) {
57        if (state == 0) {
58            return 0; // Base case, no more moves left
59        }
60      
61        if (dpCache[lastKnight][state][turn] != null) {
62            return dpCache[lastKnight][state][turn];
63        }
64      
65        int result = (turn == 1) ? 0 : Integer.MAX_VALUE;
66      
67        for (int i = 0; i < positions.length; ++i) {
68            int knightX = positions[i][0], knightY = positions[i][1];
69          
70            if ((state >> i & 1) == 1) { // Check if the ith knight is in the state
71                int tempResult = dfs(i, state ^ (1 << i), turn ^ 1) + distances[lastKnight][knightX][knightY];
72                result = (turn == 1) ? Math.max(result, tempResult) : Math.min(result, tempResult);
73            }
74        }
75      
76        // Memoize and return the result
77        return dpCache[lastKnight][state][turn] = result;
78    }
79}
80
1#include <vector>
2#include <queue>
3#include <cstring>
4#include <utility> // For std::pair
5#include <climits> // For INT_MAX
6
7class Solution {
8public:
9    int maxMoves(int kx, int ky, std::vector<std::vector<int>>& positions) {
10        int n = positions.size();
11        const int gridSize = 50;
12      
13        // Possible knight moves in chess
14        const int dx[8] = {1, 1, 2, 2, -1, -1, -2, -2};
15        const int dy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
16      
17        // Distance array initialized to -1 (unvisited)
18        int dist[n + 1][gridSize][gridSize];
19        std::memset(dist, -1, sizeof(dist));
20      
21        // Compute the shortest distance from each position to all other positions
22        for (int i = 0; i <= n; ++i) {
23            int x = (i < n) ? positions[i][0] : kx;
24            int y = (i < n) ? positions[i][1] : ky;
25          
26            std::queue<std::pair<int, int>> queue;
27            queue.push({x, y});
28            dist[i][x][y] = 0;
29
30            // Standard BFS to compute shortest path
31            for (int step = 1; !queue.empty(); ++step) {
32                for (int k = queue.size(); k > 0; --k) {
33                    auto [x1, y1] = queue.front();
34                    queue.pop();
35                  
36                    // Explore all possible knight moves
37                    for (int j = 0; j < 8; ++j) {
38                        int x2 = x1 + dx[j], y2 = y1 + dy[j];
39                      
40                        // Check if move is within bounds and unvisited
41                        if (x2 >= 0 && x2 < gridSize && y2 >= 0 && y2 < gridSize && dist[i][x2][y2] == -1) {
42                            dist[i][x2][y2] = step;
43                            queue.push({x2, y2});
44                        }
45                    }
46                }
47            }
48        }
49
50        // Dynamic programming table to store results
51        int f[n + 1][1 << n][2];
52        std::memset(f, -1, sizeof(f));
53
54        // Depth-First Search (DFS) with memoization
55        auto dfs = [&](auto &&dfs, int last, int state, int turn) -> int {
56            if (state == 0) {
57                return 0; // Base case: no positions to visit
58            }
59            if (f[last][state][turn] != -1) {
60                return f[last][state][turn]; // Return cached result
61            }
62            int result = (turn == 1) ? 0 : INT_MAX;
63
64            // Attempt to visit each unvisited position
65            for (int i = 0; i < positions.size(); ++i) {
66                int x = positions[i][0], y = positions[i][1];
67                if ((state >> i) & 1) { // Check if position i is part of the current state
68                    int tempResult = dfs(i, state ^ (1 << i), turn ^ 1) + dist[last][x][y];
69                    if (turn == 1) {
70                        result = std::max(result, tempResult);
71                    } else {
72                        result = std::min(result, tempResult);
73                    }
74                }
75            }
76            return f[last][state][turn] = result;
77        };
78      
79        // Initial call to dfs with starting position and full state
80        return dfs(n, (1 << n) - 1, 1);
81    }
82};
83
84// Note: This code can be utilized in a main function or unit test to instantiate the Solution class and call maxMoves.
85
1type Position = [number, number];
2
3// Possible knight moves in chess
4const dx: number[] = [1, 1, 2, 2, -1, -1, -2, -2];
5const dy: number[] = [2, -2, 1, -1, 2, -2, 1, -1];
6
7function maxMoves(kx: number, ky: number, positions: Position[]): number {
8    const n: number = positions.length;
9    const gridSize: number = 50;
10
11    // Distance array initialized to -1 (unvisited)
12    const dist: number[][][] = Array.from({ length: n + 1 }, () =>
13        Array.from({ length: gridSize }, () => Array(gridSize).fill(-1))
14    );
15
16    // Compute the shortest distance from each position to all other positions using BFS
17    for (let i = 0; i <= n; ++i) {
18        const x: number = (i < n) ? positions[i][0] : kx;
19        const y: number = (i < n) ? positions[i][1] : ky;
20      
21        let queue: Position[] = [[x, y]];
22        dist[i][x][y] = 0;
23
24        for (let step = 1; queue.length > 0; ++step) {
25            let queueSize = queue.length;
26          
27            while (queueSize-- > 0) {
28                const [x1, y1] = queue.shift()!;
29              
30                // Explore all possible knight moves
31                for (let j = 0; j < 8; ++j) {
32                    const x2 = x1 + dx[j], y2 = y1 + dy[j];
33                  
34                    // Check if move is within bounds and unvisited
35                    if (x2 >= 0 && x2 < gridSize && y2 >= 0 && y2 < gridSize && dist[i][x2][y2] === -1) {
36                        dist[i][x2][y2] = step;
37                        queue.push([x2, y2]);
38                    }
39                }
40            }
41        }
42    }
43
44    // Dynamic programming table to store results
45    const f: number[][][] = Array.from({ length: n + 1 }, () => 
46        Array.from({ length: 1 << n }, () => Array(2).fill(-1))
47    );
48
49    // Recursive function with memoization to explore all routes
50    const dfs = (last: number, state: number, turn: number): number => {
51        if (state === 0) {
52            return 0; // Base case: no positions to visit
53        }
54        if (f[last][state][turn] !== -1) {
55            return f[last][state][turn]; // Return cached result if available
56        }
57
58        let result = (turn === 1) ? 0 : Number.MAX_SAFE_INTEGER;
59
60        // Attempt to visit each unvisited position
61        for (let i = 0; i < positions.length; ++i) {
62            const [x, y] = positions[i];
63            if ((state >> i) & 1) { // Check if position i is part of the current state
64                const tempResult = dfs(i, state ^ (1 << i), turn ^ 1) + dist[last][x][y];
65                if (turn === 1) {
66                    result = Math.max(result, tempResult);
67                } else {
68                    result = Math.min(result, tempResult);
69                }
70            }
71        }
72        return f[last][state][turn] = result;
73    };
74
75    // Initial call to dfs with starting position and full state
76    return dfs(n, (1 << n) - 1, 1);
77}
78

Time and Space Complexity

The time complexity of the code consists of two main parts: the calculation of distances (dist) and the depth-first search (dfs) using memoization.

  1. Distance Calculation:

    • The dist array is computed using a breadth-first search (BFS) from each position, plus the initial knight position. This BFS explores the entire m x m board.
    • For each pawn (and the knight), the BFS runs in O(m^2) time, giving a total complexity of O(n \times m^2) for all positions.

  2. Depth-First Search with Memoization:

    • The recursive dfs function examines all subsets of positions to determine the maximum moves.
    • There are 2^n subsets, and for each subset, the function considers n possible choices, leading to a time complexity of O(2^n \times n).
    • Each recursive call involves additional computation across n positions, which adds up to O(2^n \times n^2) in total.

Combining both parts, the overarching time complexity is O(n \times m^2 + 2^n \times n^2).

The space complexity results from storing the dist matrix and the use of memoization in dfs.

  1. Distance Storage:

    • The dist matrix requires O(n \times m^2) space as distances are calculated for each pawn position plus the knight (hence n + 1).

  2. Memoization:

    • The cache used by dfs stores results for each combination of state and last move, requiring O(2^n \times n) space.

Overall, the space complexity is O(n \times m^2 + 2^n \times n).

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Recommended Readings

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com 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

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 Introduction

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