NullPointerException для этой задачи о гамильтоновом цикле

Question

Следующий код находит правильный гамильтонов цикл для коня на шахматной доске, когда он стартовал в позиции 0 0 на шахматной доске 10x10 или 8x8, но выдает исключение NullPointerException, когда он начинается где-либо еще.

Ввод здесь должен быть

8
8
0
0

для гамильтонова цикла на шахматной доске 8x8, начинающейся в позиции 0 0, которая выполняет правильный вывод:

  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

на

8
8
1 
1

Я получаю:

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

Почему?

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 && 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");

     }
}

Answer 1

Вот подсказка для начала:

Начните с трассировки стека. Первая строка трассировки гласит:

at horseBETA.mover(horseBETA.java:55)

Это означает, что исключение произошло в методе mover, и этот метод состоит только из одной строки:

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

NPE выбрасывается при попытке разыменования нулевой ссылки. В приведенной выше строке есть 4 подвыражения, где ссылки на объекты разыменовываются, и, возможно, могут возникать NPE.

• p.x и p.y могут бросить NPE, если p равно нулю.

• dx[i] или dy[i] могут бросить NPE, если (соответственно) dx и dy равны нулю.

Две из четырех возможных причин могут быть исключены простой проверкой кода; dx и dy инициализируются ненулевыми значениями, а затем никогда не присваиваются. Это оставляет p быть null в качестве вероятной причины. (Вы можете подтвердить это с помощью трассировки или отладчика.)

Теперь к вам ...

---

(Я также согласен с @Speck. У вас есть серьезные проблемы со стилем в вашем коде, которые затрудняют чтение и отладку ...)

Answer 2

Во-первых, ваш код неразборчив.Если вы используете принятые рекомендации по стилю, это поможет при отладке.

Несколько вещей, которые помогут улучшить:

Используйте имена, а не буквы для переменных и предпочитайте camelCaseVariables.Это поможет с удобочитаемостью, особенно когда задаешь такой вопрос.

Используйте открывающие и закрывающие скобки даже для однострочных операторов if и циклов.Это лучше отключит циклы и сделает их более читаемыми, что поможет предотвратить ошибки в потоке программы.

В любом случае, вы можете передавать объект с нулевой позицией (например, с использованием заглавных букв в именах ваших классов) методу mover.В вашей среде IDE установите точку останова на этой строке и сделайте ее условной остановкой только тогда, когда переданный объект указателя равен нулю.Вы быстро поймете, почему.