# Knight On Chess Board

Given any source point, **(C, D)** and destination point, **(E, F)** on a chess board, we need to find whether Knight can move to the destination or not.

![Knight's movements on a chess board](http://i.imgur.com/lmKL4AU.jpg)

The above figure details the movements for a knight ( **8** possibilities ).

If yes, then what would be the **minimum** number of steps for the knight to move to the said point.\
If knight can not move from the source point to the destination point, then return **-1**.

**Note:** A knight cannot go out of the board.

**Input Format:**

```
The first argument of input contains an integer A.
The second argument of input contains an integer B.
    => The chessboard is of size A x B.
The third argument of input contains an integer C.
The fourth argument of input contains an integer D.
    => The Knight is initially at position (C, D).
The fifth argument of input contains an integer E.
The sixth argument of input contains an integer F.
    => The Knight wants to reach position (E, F).
```

**Output Format:**

```
If it is possible to reach the destination point, return the minimum number of moves.
Else return -1.
```

**Constraints:**

```
1 <= A, B <= 500
```

**Example**

```
Input 1:
    A = 8
    B = 8
    C = 1
    D = 1
    E = 8
    F = 8
    
Output 1:
    6

Explanation 1:
    The size of the chessboard is 8x8, the knight is initially at (1, 1) and the knight wants to reach position (8, 8).
    The minimum number of moves required for this is 6.
```

```java
public class Solution {
    static class Coordinate {
        int x, y;

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

    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[][] visited = new boolean[N + 1][M + 1];
        Queue<Coordinate> queue = new LinkedList<Coordinate>();
        queue.add(new Coordinate(x1, y1));
        visited[x1][y1] = true;
        int level = 0;
        // BFS to find the minimum number of steps.
        while (!queue.isEmpty()) {
            int nodesInCurrentLevel = queue.size();
            // Iterate over the coordinates at current breadth, as level would be
            // incremented by 1 per breadth level.
            for (int count = 0; count < nodesInCurrentLevel; count++) {
                Coordinate currPos = queue.poll();
                if (currPos.x == x2 && currPos.y == y2)
                    return level;

                for (int i = 0; i < 8; i++) {
                    if (isValid(currPos.x + dx[i], currPos.y + dy[i], N, M, visited)) {
                        queue.add(new Coordinate(currPos.x + dx[i], currPos.y + dy[i]));
                        visited[currPos.x + dx[i]][currPos.y + dy[i]] = true;
                    }
                }
            }
            level++;
        }
        return -1;
    }

    private boolean isValid(int x, int y, int N, int M, boolean[][] visited) {
        if (x >= 1 && x <= N && y >= 1 && y <= M && !visited[x][y])
            return true;
        return false;
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mayanktyagi3111.gitbook.io/interview-prep/graphs-bfs-and-dfs/knight-on-chess-board.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.