Minimum Moves to Capture The Queen
MedPrompt
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.
Approaches
2 approaches with complexity analysis and trade-offs.
A less efficient but more general approach is to treat this as a shortest path problem on a graph. The chessboard squares are the vertices, and the possible moves of the rook and bishop define the edges. We can use a Breadth-First Search (BFS) to explore the possible moves from the initial positions of the white pieces. BFS is guaranteed to find the shortest path in terms of the number of moves. We would start the search from both the rook and the bishop simultaneously (or in sequence) and stop as soon as one of them reaches the queen's square. The number of moves at that point would be the minimum.
Algorithm
- Model the chessboard as a graph where squares are nodes and legal moves are edges.
- Use a Breadth-First Search (BFS) algorithm to find the shortest path from the starting pieces (rook and bishop) to the queen's square.
- Initialize a queue with the starting states of the rook and bishop, e.g.,
(piece_type, x, y, moves). - Maintain
visitedsets for each piece to avoid redundant computations. - In each step of the BFS, explore all possible moves for the piece dequeued.
- A move is valid if it follows the piece's rules (horizontal/vertical for rook, diagonal for bishop) and does not land on or jump over the other white piece.
- The first time a path reaches the queen's square, the number of moves taken is the minimum. Return this number.
Walkthrough
This method involves simulating the movement of the pieces on the board level by level.
We would need a queue to store the states to visit, where a state includes the piece's identity, its current position, and the number of moves made so far. We also need to keep track of visited squares for each piece to avoid infinite loops and redundant work.
The algorithm would proceed as follows:
- Add the initial states for the rook
(rook, a, b, 0)and bishop(bishop, c, d, 0)to a queue. - While the queue is not empty, dequeue a state.
- Generate all valid next positions for the piece from its current position.
- For each new position, check if it's the queen's square. If so, we've found the shortest path, and the answer is
moves + 1. - If it's not the queen's square, and the new position hasn't been visited by that piece type, add it to the queue and mark it as visited.
This approach is unnecessarily complex because the maximum number of moves required is only 2. The overhead of setting up and running a BFS is much greater than simply checking the few possible scenarios directly.
Complexity
Time
O(N*M), where N and M are the dimensions of the board. The search explores the squares of the board. For a fixed 8x8 board, this is technically O(1), but with a much larger constant factor than the direct approach.
Space
O(N*M), where N and M are the dimensions of the board (8x8). This is for the queue and visited sets. In this problem, it's O(64) = O(1).
Trade-offs
Pros
It is a general algorithm that can be adapted to more complex pathfinding problems on a grid.
It correctly finds the shortest path if implemented properly.
Cons
Significantly more complex to implement compared to a direct analytical solution.
Higher computational overhead due to data structures like queues and sets.
It's a generic approach that doesn't leverage the specific, simple constraints of this problem, making it inefficient for this particular case.
The most efficient approach is to use direct case analysis based on the rules of chess. The key observation is that the minimum number of moves required will be either 1 or 2. A capture in more than 2 moves is never optimal because the rook can always capture any piece on the board in at most two moves. Therefore, the problem simplifies to checking if a 1-move capture is possible. If it is, the answer is 1. Otherwise, the answer is 2.
Algorithm
- Realize that the minimum number of moves can only be 1 or 2. A rook can always capture a queen in at most 2 moves on an empty board, and this holds true even with the bishop present.
- Check for a 1-move capture: The answer is 1 if either the rook or the bishop can capture the queen in a single move from their starting positions.
- Rook's 1-move capture:
- Check if the rook
(a, b)and queen(e, f)are in the same row (a == e) or column (b == f). - If so, check if the bishop
(c, d)is on the path between them, which would block the capture. If the path is clear, return 1.
- Check if the rook
- Bishop's 1-move capture:
- Check if the bishop
(c, d)and queen(e, f)are on the same diagonal (abs(c - e) == abs(d - f)). - If so, check if the rook
(a, b)is on the path between them. If the path is clear, return 1.
- Check if the bishop
- If no 1-move capture is possible: If neither piece can capture the queen in one move, the minimum number of moves must be 2. Return 2.
Walkthrough
We can solve this problem with a constant number of conditional checks.
First, we check if the rook can capture the queen in one move. This happens if the rook and queen are on the same row or column, and the bishop is not positioned between them, blocking the path.
// Check if rook at (a, b) and queen at (e, f) are on the same rowif (a == e) { // Bishop at (c, d) blocks if it's on the same row and between them if (!(c == a && (b < d && d < f || f < d && d < b))) { return 1; }}// Check if rook and queen are on the same columnif (b == f) { // Bishop blocks if it's on the same column and between them if (!(d == b && (a < c && c < e || e < c && c < a))) { return 1; }}Second, if the rook cannot capture, we check if the bishop can. This occurs if the bishop and queen are on the same diagonal, and the rook is not blocking the path.
// Check if bishop at (c, d) and queen at (e, f) are on the same diagonalif (Math.abs(c - e) == Math.abs(d - f)) { // Rook at (a, b) blocks if it's on the same diagonal and between them if (!(Math.abs(c - a) == Math.abs(d - b) && (c < a && a < e || e < a && a < c))) { return 1; }}If neither of these conditions for a 1-move capture is met, the minimum number of moves must be 2. A 2-move capture is always possible for the rook (e.g., by moving to the queen's row/column first, then to the queen's square).
Here is the complete implementation:
class Solution { public int minMovesToCaptureTheQueen(int a, int b, int c, int d, int e, int f) { // Check for 1-move rook capture if (a == e) { // Same row if (!(c == a && (b < d && d < f || f < d && d < b))) { return 1; } } if (b == f) { // Same column if (!(d == b && (a < c && c < e || e < c && c < a))) { return 1; } } // Check for 1-move bishop capture if (Math.abs(c - e) == Math.abs(d - f)) { // Same diagonal if (!(Math.abs(c - a) == Math.abs(d - b) && (c < a && a < e || e < a && a < c))) { return 1; } } return 2; }}Complexity
Time
O(1), as it involves a fixed number of comparisons and arithmetic operations, regardless of the input positions.
Space
O(1), as it only uses a few variables to store the coordinates and performs checks in place.
Trade-offs
Pros
Extremely fast with O(1) time complexity.
Uses no extra space, resulting in O(1) space complexity.
Simple and straightforward to implement once the logic is understood.
Cons
The logic is highly specific to this problem and not easily generalizable to other scenarios (e.g., with more pieces or different rules).
Solutions
Solution
class Solution {private final int[] dirs1 = {-1, 0, 1, 0, -1};private final int[] dirs2 = {-1, 1, 1, -1, -1};private int e, f;public int minMovesToCaptureTheQueen(int a, int b, int c, int d, int e, int f) { this.e = e; this.f = f; return check(dirs1, a, b, c, d) || check(dirs2, c, d, a, b) ? 1 : 2; }private boolean check(int[] dirs, int sx, int sy, int bx, int by) { for (int d = 0; d < 4; ++d) { for (int k = 1; k < 8; ++k) { int x = sx + dirs[d] * k; int y = sy + dirs[d + 1] * k; if (x < 1 || x > 8 || y < 1 || y > 8 || (x == bx && y == by)) { break; } if (x == e && y == f) { return true; } } } return false; }}class Solution {public: int minMovesToCaptureTheQueen(int a, int b, int c, int d, int e, int f) { int dirs[2][5] = {{-1, 0, 1, 0, -1}, {-1, 1, 1, -1, -1}}; auto check = [&](int i, int sx, int sy, int bx, int by) { for (int d = 0; d < 4; ++d) { for (int k = 1; k < 8; ++k) { int x = sx + dirs[i][d] * k; int y = sy + dirs[i][d + 1] * k; if (x < 1 || x > 8 || y < 1 || y > 8 || (x == bx && y == by)) { break; } if (x == e && y == f) { return true; } } } return false; }; return check(0, a, b, c, d) || check(1, c, d, a, b) ? 1 : 2; }};class Solution: def minMovesToCaptureTheQueen(self, a: int, b: int, c: int, d: int, e: int, f: int) -> int: def check(dirs, sx, sy, bx, by) -> bool: for dx, dy in pairwise(dirs): for k in range(1, 8): x = sx + dx * k y = sy + dy * k if not (1 <= x <= 8 and 1 <= y <= 8) or (x, y) == (bx, by): break if (x, y) == (e, f): return True return False dirs1 = (- 1, 0, 1, 0, - 1) dirs2 = (- 1, 1, 1, - 1, - 1) return 1 if check(dirs1, a, b, c, d) or check(dirs2, c, d, a, b) else 2Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.