> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/recursion-and-backtracking/knights-tour.md).

# Knight's tour

You are given a chess-board and a starting point co-oridnates. You are given a knight, which starts at the starting point. You've to check whether the knight can visit all the spots in the chess-board.

 **Input Format:**

N (integer) - size of 2-d array

X (integer) - x-coordinate of starting point 

Y (integer) - y-coordinate of starting point Constraints

0 <= N <= 5&#x20;

0 <= X < N&#x20;

0 <= Y < N&#x20;

**Output Format:** true or false

**Sample Input:** 5 0 0

**Sample Output:** true

![](https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Knight%27s_tour_anim_2.gif/250px-Knight%27s_tour_anim_2.gif)

```java
class Solution {
    static int moves[][] = { { 1, 2 }, { -1, 2 }, { 1, -2 }, { -1, -2 }, { 2, 1 }, { 2, -1 }, { -2, 1 }, { -2, -1 } };

    public static int DFS(int n, int x, int y, boolean[][] visited) {
        if (x < n && x >= 0 && y < n && y >= 0 && !visited[x][y]) {
            int ans = 1;
            visited[x][y] = true;
            for (int[] move : moves) {
                int smallAns = DFS(n, x + move[0], y + move[1], visited);
                if (smallAns != -1)
                    ans = Math.max(ans, smallAns + 1);
            }
            visited[x][y] = false;
            return ans;
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt(), x = s.nextInt(), y = s.nextInt();
        boolean[][] visited = new boolean[n][n];
        int result = DFS(n, x, y, visited);
        System.out.println(result == n * n);
    }
}
```