Minimum Moves to Capture The Queen

Medium

Asked by:

30 views

There is a 1-indexed 8 x 8 chessboard containing 3 pieces.

You are given 6 integers a, b, c, d, e, and f where:

(a, b) denotes the position of the white rook.
(c, d) denotes the position of the white bishop.
(e, f) denotes the position of the black queen.

Given that you can only move the white pieces, return the minimum number of moves required to capture the black queen.

Note that:

Rooks can move any number of squares either vertically or horizontally, but cannot jump over other pieces.
Bishops can move any number of squares diagonally, but cannot jump over other pieces.
A rook or a bishop can capture the queen if it is located in a square that they can move to.
The queen does not move.

Example 1:

Input: a = 1, b = 1, c = 8, d = 8, e = 2, f = 3
Output: 2
Explanation: We can capture the black queen in two moves by moving the white rook to (1, 3) then to (2, 3).
It is impossible to capture the black queen in less than two moves since it is not being attacked by any of the pieces at the beginning.

Example 2:

Input: a = 5, b = 3, c = 3, d = 4, e = 5, f = 2
Output: 1
Explanation: We can capture the black queen in a single move by doing one of the following: 
- Move the white rook to (5, 2).
- Move the white bishop to (5, 2).

Constraints:

1 <= a, b, c, d, e, f <= 8
No two pieces are on the same square.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Are the rook, bishop, and queen positions guaranteed to be within the bounds of the 8x8 chessboard (i.e., between 0 and 7 inclusive for both row and column)?
If both the rook and bishop can capture the queen, should I return the minimum moves of either, or is there a preference (e.g., prioritize the rook)?
Can the rook and bishop occupy the same square initially, and can either of them occupy the same square as the queen initially?
Is it possible for the rook and bishop to block each other's path to the queen? If so, should the path be considered blocked?
If neither the rook nor the bishop can capture the queen, is -1 the only acceptable return value, or are there other error codes or exceptions I should consider?

Brute Force Solution

Approach

The goal is to figure out the fewest moves a rook, a bishop, and a king need to capture a queen on a chessboard. The brute force strategy involves trying every possible move for each piece and seeing if that capture is possible with the current move order.

Here's how the algorithm would work step-by-step:

Consider each piece (Rook, Bishop, King) individually.
For each piece, imagine moving it one square at a time in every possible direction it's allowed to move.
After each move of a piece, check if it can now directly capture the queen without being blocked by any other piece.
If the piece can capture the queen after that move, record the number of moves it took.
Repeat this process, trying out all possible single moves and then all possible combinations of two moves, three moves, and so on, for each piece, until a capturing sequence is found.
Make sure to check that the path between the piece and the queen is clear after each move.
Finally, compare the minimum number of moves required by each of the three pieces to capture the queen and return the smallest value.

Code Implementation

def minimum_moves_to_capture_the_queen(
    rook_row,
    rook_column,
    bishop_row,
    bishop_column,
    queen_row,
    queen_column,
):
    queue = [
        ((rook_row, rook_column), 0),
        ((bishop_row, bishop_column), 0),
    ]
    visited = {
        (rook_row, rook_column),
        (bishop_row, bishop_column),
    }

    while queue:
        (current_row, current_column), moves = queue.pop(0)

        # Check if the queen is captured from the current position
        if current_row == queen_row and current_column == queen_column:
            return moves

        # Generate possible moves for the rook
        if current_row == rook_row and current_column == rook_column:
            for row_delta, column_delta in [
                (0, 1),
                (0, -1),
                (1, 0),
                (-1, 0),
            ]:
                next_row, next_column = (
                    current_row + row_delta,
                    current_column + column_delta,
                )
                if (
                    0 <= next_row < 8
                    and 0 <= next_column < 8
                    and (next_row, next_column) not in visited
                ):
                    queue.append(((next_row, next_column), moves + 1))
                    visited.add((next_row, next_column))

        # Generate possible moves for the bishop
        if current_row == bishop_row and current_column == bishop_column:
            for row_delta, column_delta in [
                (1, 1),
                (1, -1),
                (-1, 1),
                (-1, -1),
            ]:
                next_row, next_column = (
                    current_row + row_delta,
                    current_column + column_delta,
                )
                if (
                    0 <= next_row < 8
                    and 0 <= next_column < 8
                    and (next_row, next_column) not in visited
                ):
                    queue.append(((next_row, next_column), moves + 1))
                    visited.add((next_row, next_column))

    return -1

Big(O) Analysis

Time Complexity

O(1) – The chess board is fixed at 8x8, meaning the maximum number of squares any piece needs to traverse is limited. The brute-force search described explores a constant number of possible moves for each piece (Rook, Bishop, King) to capture the queen, bound by the board size. Since the input size (board dimension) is constant, the time complexity does not grow with input and remains O(1).

Space Complexity

O(1) – The described brute force strategy primarily involves iterative movement and checking for capture. While exploring possible moves, the algorithm keeps track of the minimum moves found so far for each piece, which requires constant space. No dynamic data structures like lists or hash maps are used to store intermediate states or visited positions according to the explanation. Thus, the auxiliary space required remains constant regardless of the chessboard size, leading to O(1) space complexity.

Optimal Solution

Approach

The key is to check if the rook, bishop and queen are on the same line, column or diagonal. We need to efficiently find the first piece that blocks the queen in each possible direction.

Here's how the algorithm would work step-by-step:

Consider the eight possible directions (horizontal, vertical, and both diagonals) from the queen.
For each direction, look for the rook and bishop one at a time without considering other pieces.
If you find the rook or bishop first along that direction, check the distance from the queen.
If the rook is the closest, the rook can capture the queen in one move, mark this case as possible.
If the bishop is the closest, the bishop can capture the queen in one move, mark this case as possible.
Return the minimum number of moves (0 if neither can capture, 1 if either can). A piece captures if it's in the path to the queen with no piece in the way.

Code Implementation

def min_moves_to_capture_the_queen(rook_row, rook_col, bishop_row, bishop_col, queen_row, queen_col, obstacles):
    min_moves = float('inf')
    obstacles_set = set((row, col) for row, col in obstacles)

    # Check rook moves
    for direction_row, direction_col in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        moves_count = 0
        current_row = rook_row
        current_col = rook_col
        while True:
            moves_count += 1
            current_row += direction_row
            current_col += direction_col

            if not (0 <= current_row < 8 and 0 <= current_col < 8):
                break

            if (current_row, current_col) == (queen_row, queen_col):
                min_moves = min(min_moves, moves_count)
                break

            if (current_row, current_col) in obstacles_set:
                break

    # Check bishop moves
    for direction_row, direction_col in [(1, 1), (1, -1), (-1, 1), (-1, -1)]:
        moves_count = 0
        current_row = bishop_row
        current_col = bishop_col
        while True:
            moves_count += 1
            current_row += direction_row
            current_col += direction_col

            if not (0 <= current_row < 8 and 0 <= current_col < 8):
                break

            if (current_row, current_col) == (queen_row, queen_col):
                min_moves = min(min_moves, moves_count)
                break

            if (current_row, current_col) in obstacles_set:
                break

    # If min_moves is unchanged, no capture is possible
    if min_moves == float('inf'):
        return -1
    else:
        return min_moves

Big(O) Analysis

Time Complexity

O(1) – The algorithm examines a fixed number of directions (8) from the queen. For each direction, it iterates at most until it finds the first blocking piece (rook or bishop). The board size is implicitly fixed, so the maximum distance to check in any direction is constant. Therefore, the time complexity is independent of any input size and is O(1).

Space Complexity

O(1) – The algorithm iterates through at most 8 directions, checking for the rook and bishop. It uses a fixed number of variables to store distances and boolean flags to indicate if a piece can capture the queen. The space used doesn't depend on the position of pieces (N) and remains constant. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Rook, Bishop, and Queen all start at the same position	Return 0, as the Queen is already captured.
Rook and Bishop occupy the same space	The algorithm should correctly calculate minimum moves independently for the rook and bishop and then find the minimum of the two if both can capture the queen.
Rook's path to Queen is blocked by the Bishop	Rook cannot move through Bishop. If Bishop is on the same row or column between Rook and Queen then Rook cannot capture the queen and its moves should return a large number or infinity, if that's allowed, or be ignored.
Bishop's path to Queen is blocked by the Rook	Bishop cannot move through Rook. If Rook is on a diagonal between Bishop and Queen, then Bishop cannot capture the Queen and its moves should return a large number or infinity, if that's allowed, or be ignored.
Queen is unreachable by both Rook and Bishop	Return -1 because neither piece can capture the queen.
Coordinates are out of bounds (less than 0 or greater than 7)	Assume the coordinates are always in bound as stated in problem description, otherwise add input validation at the beginning to return -1 or throw an error if any coordinate is out of bounds.
Integer overflow when calculating distances	The board size is fixed to 8x8, so distances are small enough to avoid integer overflow issues within the integer data type constraints.
Both Rook and Bishop can capture Queen in the same number of moves	Return the calculated minimum number of moves, no additional handling is needed as it naturally determines the minimum path.

Rook, Bishop, and Queen all start at the same position

How to Handle:

Return 0, as the Queen is already captured.

Rook and Bishop occupy the same space

How to Handle:

The algorithm should correctly calculate minimum moves independently for the rook and bishop and then find the minimum of the two if both can capture the queen.

Rook's path to Queen is blocked by the Bishop

How to Handle:

Rook cannot move through Bishop. If Bishop is on the same row or column between Rook and Queen then Rook cannot capture the queen and its moves should return a large number or infinity, if that's allowed, or be ignored.

Bishop's path to Queen is blocked by the Rook

How to Handle:

Bishop cannot move through Rook. If Rook is on a diagonal between Bishop and Queen, then Bishop cannot capture the Queen and its moves should return a large number or infinity, if that's allowed, or be ignored.

Queen is unreachable by both Rook and Bishop

How to Handle:

Return -1 because neither piece can capture the queen.

Coordinates are out of bounds (less than 0 or greater than 7)

How to Handle:

Assume the coordinates are always in bound as stated in problem description, otherwise add input validation at the beginning to return -1 or throw an error if any coordinate is out of bounds.

Integer overflow when calculating distances

How to Handle:

The board size is fixed to 8x8, so distances are small enough to avoid integer overflow issues within the integer data type constraints.

Both Rook and Bishop can capture Queen in the same number of moves

How to Handle:

Return the calculated minimum number of moves, no additional handling is needed as it naturally determines the minimum path.