LeetCode Solutions Blog

Maximum Number of Moves to Kill All Pawns

Number: 3560

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

On a 50x50 chessboard, you are given one knight positioned at (kx, ky) and a set of pawns at specified positions. Two players – Alice and Bob – take turns. On each turn, the current player selects any pawn (even if it is not the one that can be reached fastest) and then moves the knight toward that pawn following the knight’s shortest possible path (using standard L-shaped moves). Only the chosen pawn is captured (even if the knight passes over other pawns). Alice’s objective is to maximize the total number of moves taken over the entire game, while Bob’s goal is to minimize it. Return the maximum total number of moves possible assuming optimal play from both players.

Key Insights

Precompute the minimum number of knight moves between every pair among the knight’s starting position and the pawn positions using Breadth-First Search (BFS).
Represent the game state using a bitmask (to track captured pawns), the current knight position, and the current turn (Alice or Bob).
Use a minimax-style dynamic programming (DP) with bitmasking where Alice (maximizer) picks the move that adds maximum moves and Bob (minimizer) picks the move that minimizes the total.
The small number of pawns (<=15) ensures that a recursive DP with memoization is computationally feasible.

Space and Time Complexity

Time Complexity: O(2^n * n) for the DP, plus O(n^2 * board_area) for pairwise BFS precomputation. Space Complexity: O(2^n * n) for the DP memoization and additional space for BFS grids.

Solution

The solution begins by precomputing the minimum knight moves between the knight’s starting position and all pawn positions as well as between every pair of pawn positions using BFS. With these distances computed, we model the game as a turn-based minimax problem. Each state is represented by a bitmask indicating which pawns have been captured, the current knight position (which is one of the precomputed points), and whose turn it is. In Alice’s turn, the recursive DP chooses the move that maximizes the cumulative moves; in Bob’s turn, it chooses the move that minimizes it. Memoization is used to cache results for each state, ensuring that the solution remains efficient given the exponential state space (which is manageable because n is at most 15).

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with line-by-line comments.

from collections import deque
import functools

# Knight's possible moves (L-shaped)
knight_moves = [(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)]

# BFS function to compute minimum moves from start to target on a 50x50 board
def bfs(start, target):
    sx, sy = start
    tx, ty = target
    if start == target:
        return 0
    visited = [[False] * 50 for _ in range(50)]
    queue = deque()
    queue.append((sx, sy, 0))
    visited[sx][sy] = True
    while queue:
        x, y, moves_count = queue.popleft()
        for dx, dy in knight_moves:
            nx, ny = x + dx, y + dy
            if 0 <= nx < 50 and 0 <= ny < 50 and not visited[nx][ny]:
                if (nx, ny) == target:
                    return moves_count + 1
                visited[nx][ny] = True
                queue.append((nx, ny, moves_count + 1))
    return float('inf')  # Should not occur

def max_moves_to_kill_pawns(kx, ky, positions):
    n = len(positions)
    # Create points list: index 0 is starting knight position; indices 1..n are pawns.
    points = [(kx, ky)] + [tuple(pos) for pos in positions]
    
    # Precompute minimum moves between each pair of points using BFS.
    dist = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        for j in range(n + 1):
            if i == j:
                dist[i][j] = 0
            else:
                dist[i][j] = bfs(points[i], points[j])
    
    # Use DP with bitmasking and minimax. State: (mask, current_index, turn)
    # turn: 0 for Alice (maximizer), 1 for Bob (minimizer)
    @functools.lru_cache(maxsize=None)
    def dp(mask, cur, turn):
        # Base case: all pawns have been captured.
        if mask == (1 << n) - 1:
            return 0
        
        if turn == 0:
            # Alice's turn: maximize total moves.
            best = -float('inf')
            for pawn in range(n):
                if not (mask & (1 << pawn)):
                    # pawn index in points list is pawn+1 (since index 0 is knight start)
                    cost = dist[cur][pawn + 1]
                    best = max(best, cost + dp(mask | (1 << pawn), pawn + 1, 1))
            return best
        else:
            # Bob's turn: minimize total moves.
            worst = float('inf')
            for pawn in range(n):
                if not (mask & (1 << pawn)):
                    cost = dist[cur][pawn + 1]
                    worst = min(worst, cost + dp(mask | (1 << pawn), pawn + 1, 0))
            return worst

    return dp(0, 0, 0)

# Example usage:
if __name__ == '__main__':
    print(max_moves_to_kill_pawns(1, 1, [[0, 0]]))              # Expected output: 4
    print(max_moves_to_kill_pawns(0, 2, [[1, 1], [2, 2], [3, 3]]))  # Expected output: 8
    print(max_moves_to_kill_pawns(0, 0, [[1, 2], [2, 4]]))          # Expected output: 3