# Minimum steps to reach target by a Knight in a Chess Board

Given a square chessboard of `N x N` size, and given any source point, `(X1, Y1)` and destination point, `(X2, Y2)` on the chessboard, we need to find whether a Knight can move to the destination or not from the source point.

Example:

In the above diagram, Knight takes 3 steps to reach the destination where `T` denotes the destination in the chessboard.

Every position in the chessboard is defined by a `Coordinate`.

```class Coordinate {
int x, y;
public Coordinate(int x, int y) {
this.x = x;
this.y = y;
}
}```

This problem can be seen as the shortest path in an unweighted graph. Therefore we use BFS to solve this problem. We try all 8 possible positions where a Knight can reach from its position. If the reachable position is not already visited and is inside the board, we push this state into a `queue` with distance 1 more than its parent state. Finally, we return distance of the target position, when it gets to `pop` out from `queue`. The below code implements BFS for searching through cells, where each cell contains its coordinate and distance from the starting node.

```import java.util.Queue;

class Coordinate {
int x, y;

public Coordinate(int x, int y) {
this.x = x;
this.y = y;
}
}

public class Solution {
public int knight(int N, int M, int x1, int y1, int x2, int y2) {

// The 8 positions a knight could move to for the current position.
int[] dx = {-1, -2, -1, -2, 1, 2, 1, 2};
int[] dy = {-2, -1, 2, 1, -2, -1, 2, 1};

boolean[][] isVisited = new boolean[N + 1][M + 1];
isVisited[x1][y1] = true;
int moveCount = 0;

// BFS to find the minimum number of steps.
while (!queue.isEmpty()) {
// Iterate over the coordinates at current breadth, as
// moveCount would be increased by 1 per breadth level.
for (int count = 0; count < nodesAtCurrentBreadth; count++) {
Coordinate currPos = queue.remove();
if (currPos.x == x2 && currPos.y == y2) {
return moveCount;
}
for (int i = 0; i < dx.length; i++) {
int newX = currPos.x + dx[i];
int newY = currPos.y + dy[i];
if (isValid(newX, newY, N, M) && !isVisited[newX][newY]) {
isVisited[newX][newY] = true;
}
}
}
moveCount++;
}
return -1;
}

private boolean isValid(int x, int y, int N, int M) {
if (x <= 0 || y <= 0 || x > N || y > M) {
return false;
}
return true;
}
}
```

Complexity Analysis:

• Time complexity: `O(N2)`.
At worst case, all the cells will be visited so time complexity is `O(N2)`.

Categories: BFS