NullPointerException on this Hamiltonian Cycle problem

The following code finds the correct hamiltonian cycle for a knight in a chessboard when started on position 0 0 in a 10x10 or 8x8 chessboard but throws a NullPointerException when started anywhere else.

Input here should be

8
8
0
0

for the hamiltonian cycle on a 8x8 chessboard starting in position 0 0, which runs the correct output:

  1  16  27  22   3  18  29  32
  26  23   2  17  28  31   4  19
  15  64  25  36  21  50  33  30
  24  37  48  61  56  35  20   5
  47  14  63  38  49  60  51  34
  42  39  44  57  62  55   6   9
  13  46  41  54  11   8  59  52
  40  43  12  45  58  53  10   7

on

8
8
1 
1

I get:

Exception in thread "main" java.lang.NullPointerException
        at horseBETA.mover(horseBETA.java:55)
        at horseBETA.search(horseBETA.java:130)
        at horseBETA.main(horseBETA.java:164)
Java Result: 1

Why?

import java.util.Scanner;
/**
 *
 * @author Darwin Martinez
 */

class position{
    int x,y;
    position() {};
    position(int a, int b) { x=a; y=b; }
}

public class horseBETA {
    static int number_of_movements = 8;
    static int dx[] = {-1, -2, -2, -1, 1, 2, 2, 1};
    static int dy[] = {-2, -1, 1, 2, 2, 1, -1, -2};
    static int longCycle;
    static int N,M,I,J;
    static int[][] order;
    position solucion[];
    static boolean free[][];
    static int longitud;
    static int dfs_visited[][],stampdfs;

    horseBETA(int N, int M, int I, int J) {

      longCycle = N*M;
      order = new int[N][M];
      solucion = new position[longCycle];
      free = new boolean [N][M];
      dfs_visited = new int[N][M];

      for (int i=0;i<N;i++)
        for (int j=0;j<M;j++) {
          free[i][j] = true;
          dfs_visited[i][j] = 0;
        }
      stampdfs = 0;
      position aux=new position(I,J);
      int index=(I*N)+J;

      solucion[index]=aux;
      free[I][J] = false;
      longitud = 1;
    }

    boolean valida(position p) {
        return 0<=p.x && p.x<N &&
               0<=p.y && p.y<M &&开发者_Go百科; free[p.x][p.y];
    }

    position mover(position p,int i) {
        return new position(p.x+dx[i],p.y+dy[i]);
    }

    boolean es_terminal() {
        return longitud == longCycle;
    }

    boolean is_factible(position p) {
         return ((p.x == I+dx[0] && p.y == J+dy[0]) || (p.x == I+dx[1] && p.y == J+dy[1])
                 || (p.x == I+dx[2] && p.y == J+dy[2])|| (p.x == I+dx[3] && p.y == J+dy[3])
                 || (p.x == I+dx[4] && p.y == J+dy[4])|| (p.x == I+dx[5] && p.y == J+dy[5])
                 || (p.x == I+dx[6] && p.y == J+dy[6])|| (p.x == I+dx[7] && p.y == J+dy[7]));
    }

    boolean prometedor_recurs(position d) {
      if (is_factible(d)) return true;
      for (int i=0;i<number_of_movements;i++) {
        position a = mover(d,i);
        if (valida(a) && dfs_visited[a.x][a.y] != stampdfs) {
          dfs_visited[a.x][a.y] = stampdfs;
          if (prometedor_recurs(a)) return true;
        }
      }
      return false;
    }

    boolean promising(position d) {
      stampdfs++;
      return prometedor_recurs(d);
    }

    void print_solution() {

        for (int i=0;i<longCycle;i++)
            order[solucion[i].x][solucion[i].y] = i+1;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(order[i][j]<10)
                    System.out.print("   "+order[i][j]);
                else{
                    if(order[i][j]>=10&&order[i][j]<100)
                        System.out.print("  "+order[i][j]);
                    else
                        System.out.print(" "+order[i][j]);
                }
            }System.out.print("\n");
        }

        System.exit(0);
    }

   void insertionSort(position p[], int r[], int n) {
      int i,j,aux;
      position auxp;
      for (i=1; i<n; i++) {
        aux=r[i]; auxp = p[i];
        for (j=i-1; j>=0 && aux<r[j]; j--) {
          r[j+1]=r[j]; p[j+1]=p[j];
        }
        r[j+1]=aux; p[j+1] = auxp;
      }
    }

    public boolean search() {
      if (es_terminal()) {
        if (is_factible(solucion[longCycle-1])){
          print_solution();
            return true;
        }
      } else {
        int nchildren = 0;
        position p[]=new position[number_of_movements];
        int r[]=new int[number_of_movements];
        for (int i=0;i<number_of_movements;i++) {
          position a = mover(solucion[longitud-1],i);
          if (valida(a)) {
            int grado = 0;
            for (int j=0;j<number_of_movements;j++)
              if (valida(mover(a,j)))
                grado++;
            p[nchildren] = a;
            r[nchildren] = grado;
            nchildren++;
          }
        }

        insertionSort(p,r,nchildren);
        for (int i=0; i<nchildren; i++) {
          solucion[longitud] = p[i]; longitud++;
          free[p[i].x][p[i].y] = false;
          if (promising(p[i]))
            search();
          free[p[i].x][p[i].y] = true;
          longitud--;
        }
      }return false;
    }

     public static void main(String[] args) {

         Scanner x= new Scanner(System.in);

         N = x.nextInt();
         M = x.nextInt();
         I = x.nextInt();
         J = x.nextInt();

        horseBETA yy = new horseBETA(N,M,I,J);
        if(!yy.search())
            System.out.println("\nNo hay solucion");

     }
}

Here is a HINT to get you started:

Start with the stacktrace. The first line of the trace says:

at horseBETA.mover(horseBETA.java:55)

This means that the exception occurred in the mover method, and that method consists of just one line:

  return new position(p.x+dx[i],p.y+dy[i]);

A NPE is thrown when an attempt is made to dereference a null reference. There are 4 sub-expressions in the line above where object references are dereferenced, and NPEs could possibly occur.

• p.x and p.y could throw an NPE if p is null.

• dx[i] or dy[i] could throw an NPE if (respectively) dx and dy are null.

Two out of four of those possible causes can be excluded by simple inspection of the code; dx and dy are initialized to non-null values and then never assigned to. That leaves p being null as the probable cause. (You could confirm this with a traceprint or using a debugger.)

Now over to you ...

(I also agree with @Speck. You've got some serious style problems with your code which make it painful to read and hard to debug ... )

First, your code is illegible. If you use accepted style guidelines it will help when debugging.

A couple of things to help improve:

Use names not letters for variables and favor camelCaseVariables. These will help with readability especially when asking a question like this.

Use open and close brackets even for one lined if statements and loops. It will better set off loops and make them more readable and helps prevent bugs in program flow.

Anyway, you may be passing a null position object (capitalize your class names btw) to the mover method. In your IDE, set a breakpoint on that line and make it conditional to stop only when the passed pointer object is null. You'll quickly see why.