Minimum Moves to Capture The Queen solution and explanation
8 more videos on this problem
Minimum Moves to Capture The Queen | All Diagram CasesAryan Mittal · 14:46 · 2K views
Minimum Moves to Capture The Queen - PythonCheatCode Ninja · 4:56 · 464 views
3001. Minimum Moves to Capture The Queen (Leetcode Medium)Programming Live with Larry · 18:10 · 421 views
LeetCode 10036 - Minimum Moves to Capture the Queen - PythonAlpha-Code · 11:31 · 216 views
Leetcode 3001: Minimum Moves to Capture The Queen | Weekly ContestAlgorithms Casts · 20:02 · 178 views
Minimum Moves to Capture The Queen | Leetcode 3001 | Approach + Code with explanation.Pirai's Academy · 13:36 · 90 views
Minimum Moves to Capture The QueenCodingOak · 20:43 · 86 views
LeetCode Weekly 379 - Medium - 3001 Minimum Moves to Capture The QueenLearn with EmKay · 24:07 · 56 views
【力扣每日一題】Leetcode 3001. 捕获黑皇后需要的最少移动次数 - 1797 Medium - Java - BFSLeetcode刷題最後希望 · 12:50 · 53 views
The problem
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.
Approach overview
Problem 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.
Approach 1: Breadth-First Search (BFS)
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.
from collections import deque
def min_capture_moves(a, b, c, d, e, f):
directions_rook = [(0, 1), (1, 0), (0, -1), (-1, 0)]
directions_bishop = [(1, 1), (1, -1), (-1, -1), (-1, 1)]
def bfs(start_x, start_y, target_x, target_y, directions):
queue = deque([(start_x, start_y, 0)])
visited = set()
visited.add((start_x, start_y))
while queue:
x, y, moves = queue.popleft()
if (x, y) == (target_x, target_y):
return moves
for dx, dy in directions:
nx, ny = x + dx, y + dy
while 1 <= nx <= 8 and 1 <= ny <= 8 and (nx, ny) not in visited:
visited.add((nx, ny))
queue.append((nx, ny, moves + 1))
nx += dx
ny += dy
return float('inf')
rook_moves = bfs(a, b, e, f, directions_rook)
bishop_moves = bfs(c, d, e, f, directions_bishop)
return min(rook_moves, bishop_moves)function minCaptureMoves(a, b, c, d, e, f) {
const directionsRook = [[0, 1], [1, 0], [0, -1], [-1, 0]];
const directionsBishop = [[1, 1], [1, -1], [-1, -1], [-1, 1]];
function bfs(startX, startY, targetX, targetY, directions) {
const queue = [[startX, startY, 0]];
const visited = new Set([`${startX},${startY}`]);
while (queue.length > 0) {
const [x, y, moves] = queue.shift();
if (x === targetX && y === targetY) return moves;
for (const [dx, dy] of directions) {
let nx = x + dx, ny = y + dy;
while (nx >= 1 && nx <= 8 && ny >= 1 && ny <= 8 && !visited.has(`${nx},${ny}`)) {
visited.add(`${nx},${ny}`);
queue.push([nx, ny, moves + 1]);
nx += dx; ny += dy;
}
}
}
return Number.MAX_VALUE;
}
const rookMoves = bfs(a, b, e, f, directionsRook);
const bishopMoves = bfs(c, d, e, f, directionsBishop);
return Math.min(rookMoves, bishopMoves);
}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.
Time Complexity: O(1), because the chessboard size is fixed (8x8).
Space Complexity: O(1), due to limited storage of board positions.
Approach 2: Direct Simulation with Pruning
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.
public int directCaptureSimulation(int a, int b, int c, int d, int e, int f) {
int movesRook = (a == e || b == f) ? 1 : 2;
int dx = Math.abs(c - e);
int dy = Math.abs(d - f);
int movesBishop = (dx == dy) ? 1 : ((dx + dy) % 2 == 1 ? Integer.MAX_VALUE : 2);
if ((a == e && b == f) || (c == e && d == f)) {
return 0;
} else if (movesBishop == Integer.MAX_VALUE) {
return movesRook;
} else {
return Math.min(movesRook, movesBishop);
}
}#include <algorithm>
#include <cmath>
int directCaptureSimulation(int a, int b, int c, int d, int e, int f) {
int movesRook = (a == e || b == f) ? 1 : 2;
int dx = abs(c - e);
int dy = abs(d - f);
int movesBishop = (dx == dy) ? 1 : ((dx + dy) % 2 == 1 ? -1 : 2);
if ((a == e && b == f) || (c == e && d == f)) {
return 0;
} else if (movesBishop == -1) {
return movesRook;
} else {
return std::min(movesRook, movesBishop);
}
}This Java solution models the potential capture routes by both the rook and bishop, considering their specific limitations and direct attack lines to reach the target efficiently.
Time Complexity: O(1), reflecting constant time checks and calculations.
Space Complexity: O(1), minimal storage required for simple variables.
Approach 3: Case Analysis
According to the problem description, we can categorize the scenarios for capturing the black queen as follows:
- The white rook and the black queen are in the same row with no other pieces in between. In this case, the white rook only needs to move once.
- The white rook and the black queen are in the same column with no other pieces in between. In this case, the white rook only needs to move once.
- The white bishop and the black queen are on the same diagonal
\with no other pieces in between. In this case, the white bishop only needs to move once. - The white bishop and the black queen are on the same diagonal
/with no other pieces in between. In this case, the white bishop only needs to move once. - In other cases, only two moves are needed.
The time complexity is O(1), and the space complexity is O(1).
function minMovesToCaptureTheQueen(
a: number,
b: number,
c: number,
d: number,
e: number,
f: number,
): number {
if (a === e && (c !== a || (d - b) * (d - f) > 0)) {
return 1;
}
if (b === f && (d !== b || (c - a) * (c - e) > 0)) {
return 1;
}
if (c - e === d - f && (a - e !== b - f || (a - c) * (a - e) > 0)) {
return 1;
}
if (c - e === f - d && (a - e !== f - b || (a - c) * (a - e) > 0)) {
return 1;
}
return 2;
}func minMovesToCaptureTheQueen(a int, b int, c int, d int, e int, f int) int {
if a == e && (c != a || (d-b)*(d-f) > 0) {
return 1
}
if b == f && (d != b || (c-a)*(c-e) > 0) {
return 1
}
if c-e == d-f && (a-e != b-f || (a-c)*(a-e) > 0) {
return 1
}
if c-e == f-d && (a-e != f-b || (a-c)*(a-e) > 0) {
return 1
}
return 2
}impl Solution {
pub fn min_moves_to_capture_the_queen(a: i32, b: i32, c: i32, d: i32, e: i32, f: i32) -> i32 {
if a == e && (c != a || (d - b) * (d - f) > 0) {
return 1;
}
if b == f && (d != b || (c - a) * (c - e) > 0) {
return 1;
}
if c - e == d - f && (a - e != b - f || (a - c) * (a - e) > 0) {
return 1;
}
if c - e == f - d && (a - e != f - b || (a - c) * (a - e) > 0) {
return 1;
}
return 2;
}
}class Solution {
func minMovesToCaptureTheQueen(a: Int64, b: Int64, c: Int64, d: Int64, e: Int64, f: Int64): Int64 {
if (a == e && (c != a || (d - b) * (d - f) > 0)) {
return 1
}
if (b == f && (d != b || (c - a) * (c - e) > 0)) {
return 1
}
if (c - e == d - f && (a - e != b - f || (a - c) * (a - e) > 0)) {
return 1
}
if (c - e == f - d && (a - e != f - b || (a - c) * (a - e) > 0)) {
return 1
}
2
}
}Complexity comparison
| 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), reflecting constant time checks and calculations. |
| Case Analysis | – |
Complexity 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 |
Frequently asked questions
Is Minimum Moves to Capture The Queen easy or hard?
The problem is rated Medium because the logic involves multiple geometric conditions and blocking scenarios. Once you recognize the rook and bishop attack patterns and handle the blocking checks correctly, the implementation becomes short and runs in constant time.
Minimum Moves to Capture The Queen Python/Java solution
Python and Java implementations typically follow the same constant‑time logic: check rook alignment with the queen, verify no blocking by the bishop, then check bishop diagonal alignment and ensure the rook does not block the path. The code mainly consists of coordinate comparisons and simple conditional statements.
How to solve Minimum Moves to Capture The Queen in O(1)?
Check two attack conditions. First, verify whether the rook and queen share the same row or column and ensure the bishop is not positioned between them on that line. Second, verify whether the bishop and queen lie on the same diagonal and ensure the rook does not block the diagonal. If either condition is satisfied, return 1; otherwise return 2.
What is the best approach for Minimum Moves to Capture The Queen?
Direct simulation with pruning is the best approach. Instead of exploring moves, check if the rook shares the same row or column with the queen or if the bishop shares the same diagonal. If the attacking line is not blocked by the other piece, the queen can be captured in one move; otherwise the answer is two. This method runs in O(1) time and uses O(1) space.
Is Minimum Moves to Capture The Queen asked at Google/Amazon/Meta?
Chessboard geometry and coordinate simulation problems appear frequently in technical interviews at companies like Google, Amazon, and Meta. Variations involving rook, bishop, or queen movement are common because they test logical reasoning, edge‑case handling, and constant‑time optimization.
What data structure is used in Minimum Moves to Capture The Queen?
The optimal approach does not require a complex data structure. It mainly uses coordinate comparisons and conditional checks. A BFS version may conceptually treat the board as a grid or array, but the direct simulation solution avoids building an explicit board structure.
What is the time complexity of Minimum Moves to Capture The Queen?
The optimal solution runs in O(1) time and O(1) space because it only performs a few coordinate comparisons and blocking checks. Even a BFS-based solution remains effectively constant time since the chessboard size is fixed at 8x8 and the number of states is very small.