Maximum Number of Moves to Kill All Pawns - Problem

Array Math Bit Manipulation Breadth-First Search Game Theory Bitmask Hard

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

Input & Output

Example 1 — Basic Game

$ Input: kx = 1, ky = 1, positions = [[0,0]]

› Output: 4

💡 Note: Knight at (1,1) needs 4 moves to reach pawn at (0,0). Since there's only one pawn, Alice captures it in 4 moves, total = 4.

Example 2 — Two Pawns

$ Input: kx = 0, ky = 2, positions = [[1,1],[2,2],[3,3]]

› Output: 8

💡 Note: Alice tries to maximize moves by choosing the pawn that leads to maximum total, while Bob minimizes on his turn.

Example 3 — Strategic Choice

$ Input: kx = 0, ky = 0, positions = [[1,2],[2,4]]

› Output: 10

💡 Note: Alice chooses optimally to maximize total moves across all turns, considering Bob will minimize.

Constraints

1 ≤ positions.length ≤ 15
positions[i].length == 2
0 ≤ kx, ky, positions[i][0], positions[i][1] ≤ 49
All positions are unique
positions[i] ≠ [kx, ky]

Visualization

Tap to expand

Asked in

G Google 15 f Meta 12 a Amazon 8

This is a minimax game theory problem where Alice tries to maximize total moves while Bob minimizes them. The key insight is to use BFS to precompute distances between all positions, then apply memoization with bitmasks to represent game states efficiently. Best approach: Minimax with Memoization. Time: O(n² × 2ⁿ), Space: O(n × 2ⁿ).

Common Approaches

✓ Brute Force Recursion

⏱️ Time: O(n! × 50²) Space: O(n)

For each turn, try capturing each remaining pawn and recursively solve the remaining game. Alice maximizes the total moves while Bob minimizes them.

Minimax with Memoization

⏱️ Time: O(n² × 2ⁿ × 50²) Space: O(n × 2ⁿ)

Precompute all pairwise distances, then use minimax with bitmask state compression. Cache results using the current position and remaining pawns bitmask.

Brute Force Recursion — Algorithm Steps

Calculate distances from knight to all pawns using BFS
For Alice's turn: try each pawn, take maximum result
For Bob's turn: try each pawn, take minimum result
Base case: no pawns left, return 0

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Distances

Use BFS to find shortest path from knight to each pawn

Alice's Turn

Try capturing each pawn, choose maximum total moves

Bob's Turn

Try capturing each pawn, choose minimum total moves

Recursive Tree

Explore all possible capture sequences

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

typedef struct {
    int x, y, dist;
} Point;

int bfsDistance(int startX, int startY, int endX, int endY) {
    if (startX == endX && startY == endY) return 0;
    
    Point queue[2500];
    int visited[50][50] = {0};
    int front = 0, rear = 0;
    int directions[8][2] = {{-2,-1}, {-2,1}, {-1,-2}, {-1,2}, {1,-2}, {1,2}, {2,-1}, {2,1}};
    
    queue[rear++] = (Point){startX, startY, 0};
    visited[startX][startY] = 1;
    
    while (front < rear) {
        Point curr = queue[front++];
        for (int i = 0; i < 8; i++) {
            int nx = curr.x + directions[i][0];
            int ny = curr.y + directions[i][1];
            if (nx >= 0 && nx < 50 && ny >= 0 && ny < 50 && !visited[nx][ny]) {
                if (nx == endX && ny == endY) return curr.dist + 1;
                visited[nx][ny] = 1;
                queue[rear++] = (Point){nx, ny, curr.dist + 1};
            }
        }
    }
    return INT_MAX;
}

int solve(int currX, int currY, int positions[][2], int n, int aliceTurn) {
    if (n == 0) return 0;
    
    if (aliceTurn) {
        int maxMoves = 0;
        for (int i = 0; i < n; i++) {
            int moves = bfsDistance(currX, currY, positions[i][0], positions[i][1]);
            int newPos[n-1][2];
            int idx = 0;
            for (int j = 0; j < n; j++) {
                if (j != i) {
                    newPos[idx][0] = positions[j][0];
                    newPos[idx][1] = positions[j][1];
                    idx++;
                }
            }
            int total = moves + solve(positions[i][0], positions[i][1], newPos, n-1, 0);
            if (total > maxMoves) maxMoves = total;
        }
        return maxMoves;
    } else {
        int minMoves = INT_MAX;
        for (int i = 0; i < n; i++) {
            int moves = bfsDistance(currX, currY, positions[i][0], positions[i][1]);
            int newPos[n-1][2];
            int idx = 0;
            for (int j = 0; j < n; j++) {
                if (j != i) {
                    newPos[idx][0] = positions[j][0];
                    newPos[idx][1] = positions[j][1];
                    idx++;
                }
            }
            int total = moves + solve(positions[i][0], positions[i][1], newPos, n-1, 1);
            if (total < minMoves) minMoves = total;
        }
        return minMoves;
    }
}

int solution(int kx, int ky, int positions[][2], int n) {
    return solve(kx, ky, positions, n, 1);
}

int main() {
    int kx, ky;
    scanf("%d", &kx);
    scanf("%d", &ky);
    
    char line[1000];
    scanf(" %[^\n]", line);
    
    int positions[20][2];
    int n = 0;
    char* token = strtok(line + 1, "]");
    while (token != NULL) {
        if (strlen(token) > 1) {
            if (token[0] == ',') token++;
            if (token[0] == '[') token++;
            sscanf(token, "%d,%d", &positions[n][0], &positions[n][1]);
            n++;
        }
        token = strtok(NULL, "]");
    }
    
    printf("%d\n", solution(kx, ky, positions, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n! × 50²)

n! possible capture sequences, each BFS takes O(50²) time

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth up to n pawns

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~35 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Maximum Number of Moves to Kill All Pawns - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler