Minimum number steps to reach goal in chess - knight traversal with BFS

Question

Code given below works for chess of size less than 13 efficiently, but after that it takes too much time and runs forever. I want to reduce time to reach till end node. Also this code finds minimum path from starti,startj to endi,endj where starti and startj takes value from 1 to n-1.

Here is the problem that I am trying to solve:
https://www.hackerrank.com/challenges/knightl-on-chessboard/problem

Program:

import java.util.LinkedList;<br>
import java.util.Scanner;

class Node {

    int x,y,dist;

    Node(int x, int y, int dist) {
        this.x = x;
        this.y = y;
        this.dist = dist;
    }

    public String toString() {
        return "x: "+ x +" y: "+y +" dist: "+dist;
    }
}

class Solution {

    public static boolean checkBound(int x, int y, int n) {

        if(x >0 && y>0 && x<=n && y<=n)
            return true;
        return false;
    }

    public static void printAnswer(int answer[][], int n) {
        for(int i=0; i<n-1; i++) {
            for(int j=0; j<n-1; j++) {
                System.out.print(answer[i][j]+" ");
            }
            System.out.println();
        }

    }

    public static int findMinimumStep(int n, int[] start, int[] end, int a, int b) {

        LinkedList<Node> queue = new LinkedList();
        boolean visited[][] = new boolean[n+1][n+1];
        queue.add(new Node(start[0],start[1],0));       
        int x,y;

        int[] dx = new int[] {a, -a, a, -a, b, -b, b, -b};
        int[] dy = new int[] {b, b, -b, -b, a, a, -a, -a};


        while(!queue.isEmpty()) {
            Node z = queue.removeFirst();
            visited[z.x][z.y] = true;

            if(z.x == end[0] && z.y == end[1])
                return z.dist;

            for(int i=0; i<8; i++)
            {
                x = z.x + dx[i];
                y = z.y + dy[i];            
                if(checkBound(x,y,n) && !visited[x][y])
                    queue.add(new Node(x,y,z.dist+1));
            }
        }
        return -1;
    }

    public static void main(String args[]) {

        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int start[] = new int[] {1,1};
        int goal[] = new int[] {n,n};
        int answer[][] = new int[n-1][n-1];

        for(int i=1; i<n; i++) {
            for(int j=i; j<n; j++) {
                int result = findMinimumStep(n, start, goal, i, j);
                answer[i-1][j-1] = result;
                answer[j-1][i-1] = result;
            }
        }
        printAnswer(answer,n);

    }
}

Answer 1

You set visited too late and the same cells are added multiple times to the queue, then you pop them from the queue without checking their visited state that makes things even worse. This leads to the fast growth of the queue.

You need to set visited right after you add the Node to the queue:

if(checkBound(x,y,n) && !visited[x][y]) {
    queue.add(new Node(x,y,z.dist+1)); 
    visited[x][y] = true;   
}