We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Moves to Capture The Queen

Number: 3270

Difficulty: Medium

Paid? No

Companies: Goldman Sachs

Problem Description

There is an 8x8 chessboard with three pieces: a white rook, a white bishop, and a black queen. Given their positions, you are allowed to move only the white pieces following standard chess rules (note that they cannot jump over other pieces). Determine the minimum number of moves needed to capture the queen.

Key Insights

  • A piece can capture the queen if the queen lies on a valid move path of that piece (i.e. same row/column for the rook and same diagonal for the bishop) and the path between the piece and the queen is unobstructed by the other white piece.
  • Check if either white piece can capture the queen in one move by ensuring:
    • For the rook: either the row or the column is shared and the bishop does not block the path.
    • For the bishop: the queen is on the same diagonal and the rook does not lie in between.
  • If a one move solution isn’t available, then a two move solution always exists because one can first reposition one piece to remove a blocking obstacle or to line up a direct strike.

Space and Time Complexity

Time Complexity: O(1) — the board is of constant size (8x8) and only a few arithmetic and comparison operations are performed. Space Complexity: O(1) — a constant amount of extra space is used.

Solution

The algorithm first checks if the rook or bishop can capture the queen in one move:

  1. For the rook: If the queen shares the same row or column, iterate through the squares between the rook and queen. If the bishop is present on this segment, the path is blocked.
  2. For the bishop: If the queen is diagonally aligned with the bishop, iterate along the diagonal path and check if the rook is between them. If either piece can capture the queen directly, the answer is 1. Otherwise, 2 moves are required—one move to reposition a piece to an unobstructed line or diagonal, and the second to capture the queen.

Key data structures and methods used:

  • Simple arithmetic and iteration over a fixed set of squares.
  • The checking functions for unobstructed paths ensure that there is no interference from the other white piece.

Code Solutions

def minimumMoves(a, b, c, d, e, f):
    # Helper to check if path is clear for a rook move from (x1, y1) to (x2, y2)
    def clear_rook_path(x1, y1, x2, y2, blockerX, blockerY):
        if x1 == x2:  # Same row
            left, right = sorted([y1, y2])
            # Check if blocker is in between on the same row
            return not (blockerX == x1 and left < blockerY < right)
        elif y1 == y2:  # Same column
            top, bottom = sorted([x1, x2])
            # Check if blocker is in between on the same column
            return not (blockerY == y1 and top < blockerX < bottom)
        return False

    # Helper to check if path is clear for a bishop move from (x1, y1) to (x2, y2)
    def clear_bishop_path(x1, y1, x2, y2, blockerX, blockerY):
        if abs(x1 - x2) != abs(y1 - y2):
            return False
        dx = 1 if x2 > x1 else -1
        dy = 1 if y2 > y1 else -1
        curX, curY = x1 + dx, y1 + dy
        while (curX, curY) != (x2, y2):
            if (curX, curY) == (blockerX, blockerY):
                return False
            curX += dx
            curY += dy
        return True

    # Check if rook can capture queen in one move.
    if a == e or b == f:
        if clear_rook_path(a, b, e, f, c, d):
            return 1

    # Check if bishop can capture queen in one move.
    if abs(c - e) == abs(d - f) and clear_bishop_path(c, d, e, f, a, b):
        return 1

    # Otherwise, two moves are sufficient.
    return 2

# Example calls for testing:
print(minimumMoves(1, 1, 8, 8, 2, 3))  # Output: 2 (Example 1)
print(minimumMoves(5, 3, 3, 4, 5, 2))  # Output: 1 (Example 2)
← Back to All Questions