Sudoku Solver Infinite Recursion Java

Question

I'm building a sudoku solver in Java, and I'm using a backtracking algorithm. There is a stack overflow error and I'm suspecting there's infinite recursion somewhere in my code. I know I'm giving little information but I'm so stuck and don't know how to precede.

    public void run(int r, int c){
        if(!grid[r][c].isOriginal()){
            checkAll(r, c);
        }

        if(moveOn){
            if(c < 8){
                c++;
            } else if (r < 8){
                c = 0;
                r++;
            }
        } else {
            if(c > 0){
                c--;
            } else if(r > 0){
                c = 8;
                r--;
            }
        }

        if(!finished()) {
            run(r, c);
        }
    }

    public void checkAll(int r, int c){
        if(grid[r][c].getVal() < 9) {
            grid[r][c].setVal(grid[r][c].getVal() + 1);
            if(checkSquare(r, c) && checkRow(r, c) && checkCol(r, c)){
                moveOn = true;
            } else {
                checkAll(r, c);
            }
        } else {
            moveOn = false;
            grid[r][c].setVal(0);
        }
    }
}

The functions "checkRow", "checkCol", and "checkSquare" all seem to work, as does "finished" and "printGrid".

I start the program by calling

run(0, 0);

in the main, with the program solving the sudoku left to right, then top to bottom.

The grid, which is a 9 by 9 array that represents each sudoku square, holds a custom type called "Value", which simply contains an integer and a boolean, "isOriginal" indicating whether the value was a given or changeable.

"moveOn" is a global variable which value is set in "checkAll" and decides whether to move on to the next sudoku square or backtrack.

Théo camb. Théo camb. · Accepted Answer · 2018-09-17T14:17:17

One tip that might help you in the future, try to avoid global variables. The fact you use the "moveOn" variable as global is making is harder to debug and less predictable. Make your "checkAll" function return a boolean instead of this global variable.

Now for your issue, I think that in your recursive call to checkAll, you should change something in one of your variables, right? Otherwise it will always have the same parameters in input.

Sudoku Solver Infinite Recursion Java

1 Answers