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:
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 <= 8Problem Overview: You are given coordinates of a rook, a bishop, and a queen on an 8x8 chessboard. The goal is to determine the minimum number of moves required for either the rook or the bishop to capture the queen while respecting normal chess movement rules and piece blocking.
Approach 1: Breadth-First Search (BFS) Enumeration (Time: O(1), Space: O(1))
This approach models the chessboard as a small state space and explores possible moves using Breadth-First Search. From the rook and bishop positions, generate all legal moves according to their movement rules and check whether the queen can be captured. BFS guarantees the shortest path because moves are explored level by level. The board size is fixed (8x8), so the number of states is constant, which keeps the complexity effectively O(1). This approach is useful if you want a generic framework that can be extended to other chess‑like movement problems.
To implement it, enqueue the current piece position and simulate each legal direction step by step until the edge of the board or a blocking piece is reached. If the queen appears along that path, you can capture in one move. Otherwise, continue exploring positions reachable in the next move. Because the board is tiny, BFS quickly terminates.
Approach 2: Direct Simulation with Pruning (Time: O(1), Space: O(1))
This method relies on direct geometric checks instead of exploring moves. The key observation: the answer can only be 1 or 2. A capture happens in one move if either the rook or bishop already has a clear attacking line to the queen. For the rook, check if they share the same row or column. Then verify the bishop is not positioned between them on that line. For the bishop, check if the queen lies on the same diagonal and ensure the rook is not blocking that diagonal path.
If any valid attacking line exists without obstruction, return 1. Otherwise return 2, since one piece can reposition on the first move and capture on the second. These checks are simple coordinate comparisons and conditional logic, which makes the algorithm constant time.
The solution is essentially a small enumeration of chess attack patterns using basic coordinate math. Even though the board could be represented with an array, the optimal solution avoids building a board entirely and instead works directly with positions.
Recommended for interviews: Direct simulation with pruning is what interviewers usually expect. It shows you recognize rook/diagonal attack patterns and handle blocking conditions cleanly in constant time. BFS still demonstrates problem‑solving ability and systematic exploration, but the direct check proves stronger pattern recognition and leads to a simpler O(1) implementation.
To determine the minimum number of moves required to capture the black queen, we can utilize a Breadth-First Search (BFS) approach. The idea is to explore all possible moves from both the rook and bishop simultaneously, updating and checking each piece's potential to capture the queen at every step. Starting from their initial positions, simulate the movements of the rook and bishop on the chessboard, adding each reachable position to a queue to explore subsequent moves. If a piece reaches the queen's position, return the number of moves required. This ensures the shortest path due to the nature of BFS.
This Python solution employs BFS to determine the minimum number of moves required by simulating the rook and bishop moves on the chessboard. The positions are tracked using a queue, and every possible move is explored until one of the pieces captures the queen.
Python
JavaScript
Time Complexity: O(1), because the chessboard size is fixed (8x8).
Space Complexity: O(1), due to limited storage of board positions.
This approach directly simulates the movement of the rook and bishop toward the queen while applying pruning strategies to skip unnecessary explorations. By examining direct lines of attack first and pruning paths that cannot reach the queen due to other pieces, this method aims for optimal move count calculations.
This C++ solution directly assesses whether the piece can 'see' the queen and captures it efficiently with 1 move. Otherwise, it calculates the shortest path using movement rules and constraints, avoiding unnecessary paths.
Time Complexity: O(1), since computations are constant time operations.
Space Complexity: O(1), due to basic variable usage only.
According to the problem description, we can categorize the scenarios for capturing the black queen as follows:
\ with no other pieces in between. In this case, the white bishop only needs to move once./ with no other pieces in between. In this case, the white bishop only needs to move once.The time complexity is O(1), and the space complexity is O(1).
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) | Time Complexity: O(1), because the chessboard size is fixed (8x8). |
| Direct Simulation with Pruning | Time Complexity: O(1), since computations are constant time operations. |
| Case Analysis | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search (BFS) | O(1) | O(1) | When modeling the board as a state graph or extending to more complex movement rules |
| Direct Simulation with Pruning | O(1) | O(1) | Best for interviews; uses coordinate math and blocking checks for immediate evaluation |
Minimum Moves to Capture The Queen | All Diagram Cases • Aryan Mittal • 2,302 views views
Watch 9 more video solutions →Practice Minimum Moves to Capture The Queen with our built-in code editor and test cases.
Practice on FleetCode