CODEWITHSUNDEEP
javaalgorithmsudoku
Rei
Rei

Reputation: 512

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

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?

Upvotes: 0

Views: 139

Answers (2)

UmNyobe
UmNyobe

Reputation: 22890

  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.

Upvotes: 1

Manjar
Manjar

Reputation: 3268

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.

Upvotes: 0

Related Questions