what is wrong with my backtracking algorithm? (sudoku solver, stackoverflow)

Question

below is a method to solve a sudoku with backtracking algorithm.. or that's what I meant to do

    private boolean fillGrid(int[][] a){


    if(!find(a)) // this method finds if there's unassigned grid
        return true;

    for(int i = 0; i<a.length ; i++){
        for(int j = 0; j < a.length ; j++){
            if(a[i][j] == 0){ // if a[i][j] is unassigned, perform things below
                for(int num = 1 ; num <=9; num++){
                    if(noConflict(a, i, j, num ) && noConflictGrid(a, i, j , num))
                        a[i][j]= num;
                    if(fillGrid(a)) // recurse
                        return true;
                    a[i][j] = 0; // unassigned to try again whenever false;



                }
            }
        }
    }

    return false;
}

however when I run it, it gave me stackoverflow. the stackoverflow points to fillGrid(a) the one with 'recurse' comment, and (!find(a)). the method find is below:

private boolean find(int[][] a){
    for(int[] b: a){
        for(int c: b){
            if(c == 0)
                return true;
        }
    }
    return false;
}

anyone please tell me what's wrong with the code?

read this it is helpful : http://stackoverflow.com/questions/214741/what-is-a-stack-overflow-error — Lrrr, Oct 10 '14 at 07:36

UmNyobe · Accepted Answer · 2014-10-10T09:07:00.227

1

  if(noConflict(a, i, j, num ) && noConflictGrid(a, i, j , num))
        a[i][j]= num;

Are you sure this is always guaranteed to be true? If it's not, the state of a doesnt change before the next call to fillGrid(a) and we go back to square one, calling the same method with the same input. Which lead to a stackoverflow.

edited Oct 10 '14 at 09:07

answered Oct 10 '14 at 07:36

UmNyobe

22,539
9
61
90

i've added else if(!noConflict(a, i, j, num) && !noConflictGrid(a, i, j , num)) continue; after that line you mentioned, and the stack overflow stops, but the algorithm doesn't seem to solve the sudoku, it goes to infinite loop trying to solve it, it seems. can you tell me what's wrong with it? – Rei Oct 10 '14 at 08:37

score 0 · Answer 2 · answered Oct 10 '14 at 08:38

You are creating a lot of branches on each step.

I recomend you to take one cell on each step and try to fill it with the 9 numbers, so you will only carry on with the valid.

Right now you are creating up to 9*9*9 branches on every step, you recursion is too much complex and this is was is creating the stack overflow.

So in every step just seek for the first free cell (with lower i and j index) and try to fill it with the 9 numbers.

what is wrong with my backtracking algorithm? (sudoku solver, stackoverflow)

2 Answers2