StackOverFlowError on Backtracking method

Question

I'm having a little trouble getting this method to work, getting a StackOverFlowError. I'm trying to autosolve the puzzles from this page 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;
    
}

Could it be passing the board in each call the problem?, it has the next variables:

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

The code of the envolved methods:

    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;

"solutions[]" and "numberSolutions" are global variables I think i may fix the "board.getBoard()" code but it shouldn't affect the backtracking

If you had included the code for the other helper methods, you might have gotten a more focused answer. — Tim Biegeleisen, Jan 11 '16 at 03:52
Possible duplicate of [What is a StackOverflowError?](http://stackoverflow.com/questions/214741/what-is-a-stackoverflowerror) — Raedwald, Jan 22 '16 at 13:29

Tim Biegeleisen · Answer 1 · 2016-01-11T05:04:39.187

The reason you are seeing the StackOverFlowError is that you are making an infinite number of recursive calls to the backtrackingPuffBalls() method. I expect it to be the case that the else condition keeps happening, and each call ends up making another recursive call.

To solve this you need to sort out your logic and make sure that the recursion ends at the appropriate time.

The debugger is your best friend here, and you will learn a lot by stepping through your code to see what is happening.

StackOverFlowError on Backtracking method

1 Answers1