title: Minimum number steps to reach goal in chess - knight traversal with BFS
body: <p>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.</p>
  
  <p>Here is the problem that I am trying to solve:<br>
  <a href="https://www.hackerrank.com/challenges/knightl-on-chessboard/problem" rel="nofollow noreferrer">https://www.hackerrank.com/challenges/knightl-on-chessboard/problem</a></p>
  
  <p><b>Program: <br></b></p>
  
  <pre><code>import java.util.LinkedList;&lt;br&gt;
  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 &gt;0 &amp;&amp; y&gt;0 &amp;&amp; x&lt;=n &amp;&amp; y&lt;=n)
              return true;
          return false;
      }
  
      public static void printAnswer(int answer[][], int n) {
          for(int i=0; i&lt;n-1; i++) {
              for(int j=0; j&lt;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&lt;Node&gt; 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] &amp;&amp; z.y == end[1])
                  return z.dist;
  
              for(int i=0; i&lt;8; i++)
              {
                  x = z.x + dx[i];
                  y = z.y + dy[i];            
                  if(checkBound(x,y,n) &amp;&amp; !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&lt;n; i++) {
              for(int j=i; j&lt;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);
  
      }
  }
  </code></pre>