StackOverFlowError on Backtracking method

Question

У меня возникли проблемы с тем, чтобы этот метод работал, получив StackOverFlowError. Я пытаюсь autosolve головоломки с этой страницы Puff Ball

public static boolean backtrackingPuffBalls(Board board, int[] steps, int ball,int index){ 
    if(!(checkValidPosition(board))){ 
     if(checkSolution(board)){ 
      numberSolutions++; 
      solutions[numberSolutions] = steps; 
     } 
     else{ 
      return false; 
     } 
    } 
    else{ 
     while(ball<board.getNumObjectives()+1){ 
      puffBall(board, ball); 
      if(backtrackingPuffBalls(board, steps, ball, index++)){ 
       return true; 
      } 
      else{ 
       ball++; 
       index--; 
      } 
     } 
    } 

    return false; 

} 

Может быть, проходящей платы в каждом вызове проблемы ?, имеет следующие переменные:

int[][] board; 
    int numObjectives; 
    boolean solvable, solved; 
    int[] movements; 
    boolean valid; 
    Coordinates[] objectives; 
    Coordinates[] balls; 

код из профессиональней методы:

public static boolean checkValidPosition(Board board){ 
    int objectivesInBorder=0; 
    int ballsInBorder=0; 
    for(int i=0;i<board.getObjectives().length;i++){ 
     if(board.getObjectives()[i].getX()==0||board.getObjectives()[i].getX()==board.getBoard().length 
       ||board.getObjectives()[i].getY()==0||board.getObjectives()[i].getY()==board.getBoard()[0].length){ 
       objectivesInBorder++; 
     } 
    } 
    for(int i=0;i<board.getBalls().length;i++){ 
     if(board.getBalls()[i].getX()==0||board.getBalls()[i].getX()==board.getBoard().length 
       ||board.getBalls()[i].getY()==0||board.getBalls()[i].getY()==board.getBoard()[0].length){ 
       ballsInBorder++; 
     } 
    } 
    if(ballsInBorder>objectivesInBorder){ 
     board.setValid(false); 
     return false; 
    } 
    board.setValid(true); 
    return true; 
} 
    public static boolean checkSolution(Board board){ 
    int solved=0; 
    for(int i=0;i<board.getObjectives().length;i++){ 
     for(int j=0;j<board.getBalls().length;i++){ 
      if(board.getObjectives()[i]==board.getBalls()[j]){ 
       solved++; 
      } 
     } 
    } 
    if(solved==board.getNumObjectives()){ 
     return true; 
    } 
    return false; 
} 
public static Board puffBall(Board board, int ball){ 

    Coordinates xy=searchCoordinates(board, ball-1); 
    Coordinates[] balls=board.getBalls(); 
    //Moving from the edges to resolve conflict when 2 balls are touching each other 
    boolean ballsMoved = false; 
    //Bottom to Top 
    for (int i = board.getBoard().length;i==xy.getY();i--){ 
     if(board.getBoard()[xy.getX()][i]==1){ 
      if(checkValidMovement(board.getBoard(), i+1, 1)){ 
       board.getBoard()[xy.getX()][i]=-1; 
       board.getBoard()[xy.getX()][i+1]=1; 
       balls[searchBall(board, xy.getX(), i)-1].setY(i+1); 
       ballsMoved=true; 
      } 
     } 
    } 
    //Top to Bottom 
    for (int i = 0; i==xy.getY();i++){ 
     if(board.getBoard()[xy.getX()][i]==1){ 
      if(checkValidMovement(board.getBoard(), i-1, 1)){ 
       board.getBoard()[xy.getX()][i]=-1; 
       board.getBoard()[xy.getX()][i-1]=1; 
       balls[searchBall(board, xy.getX(), i)-1].setY(i-1); 
       ballsMoved=true; 
      } 

     } 
    } 
    //Right to Left 
    for (int i = board.getBoard()[0].length; i==xy.getY();i--){ 
     if(board.getBoard()[i][xy.getY()]==1){ 
      if(checkValidMovement(board.getBoard(), i+1, 0)){ 
       board.getBoard()[i][xy.getY()]=-1; 
       board.getBoard()[i+1][xy.getY()]=1; 
       balls[searchBall(board, i, xy.getY())-1].setX(i+1); 
       ballsMoved=true; 
      } 
     } 
    } 
    //Left to Right 
    for (int i = 0; i==xy.getY();i++){ 
     if(board.getBoard()[i][xy.getY()]==1){ 
      if(checkValidMovement(board.getBoard(), i-1, 0)){ 
       board.getBoard()[i][xy.getY()]=-1; 
       board.getBoard()[i-1][xy.getY()]=1; 
       balls[searchBall(board, i, xy.getY())-1].setX(i-1); 
       ballsMoved=true; 
      } 
     } 
    } 

    board.setBalls(balls); 
    board.setValid(ballsMoved); 
    return board; 

«решения []» и «numberSolutions» глобальные переменные Я думаю, что я может исправить «board.getBoard()» код, но он не должен Af fect backtracking

Answer 1

Причина, по которой вы видите StackOverFlowError, заключается в том, что вы делаете бесконечное количество рекурсивных вызовов метода backtrackingPuffBalls(). Я ожидаю, что это будет так, что состояние else продолжает происходить, и каждый вызов заканчивается тем, что делает другой рекурсивный вызов.

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

Отладчик - ваш лучший друг здесь, и вы узнаете многое, пройдя свой код, чтобы узнать, что происходит.