# Minimum Moves to Capture The Queen
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-moves-to-capture-the-queen)
Canonical: https://scaleengineer.com/dsa/problems/minimum-moves-to-capture-the-queen
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Companies:** [Wipro](https://scaleengineer.com/companies/wipro)
---
## 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:**

![](https://assets.glich.co/dsa/minimum-moves-to-capture-the-queen/image0.png) 

**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:**

![](https://assets.glich.co/dsa/minimum-moves-to-capture-the-queen/image1.png) 

**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
## State-Space Search (BFS)
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.
**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).
**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.
### Explanation
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:
1. Add the initial states for the rook `(rook, a, b, 0)` and bishop `(bishop, c, d, 0)` to a queue.
2. While the queue is not empty, dequeue a state.
3. Generate all valid next positions for the piece from its current position.
4. 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`.
5. 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.
### 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 `visited` sets 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.

## Direct Case Analysis
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.
**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.
**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).
### Explanation
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.

```java
// Check if rook at (a, b) and queen at (e, f) are on the same row
if (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 column
if (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.

```java
// Check if bishop at (c, d) and queen at (e, f) are on the same diagonal
if (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:
```java
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;
    }
}
```
### 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.
- **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.
- **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.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 2

```