CODEWITHSUNDEEP
javastack-overflowsudokubacktracking
udiboy1209
udiboy1209

Reputation: 1502

Java sudoku backtracking recursive keeps giving StackOverflow

I implemented a SuDoku backtracking algorithm, but it keeps giving me StackOverflow Error. Any other methods or algorithms to avoid this, because I can't get my head around forming a loop for this. 

public boolean guess(int istart){
    int i=istart, j=0; boolean found=false;
    for(i=istart; i<9; i++){//find first empty cell
        for(j=0; j<9; j++){
            if(get(i,j)==0) {found=true; break;}
        }
        if(found) break;
    }
    boolean[] pos=pos_copy;//pos_copy is a length-9 boolean array with all elements set to true
    for(int n=0; n<9; n++){//store all possible numbers in pos[]
        if(get(i,n)!=0) pos[get(i,n)-1]=false;
        if(get(n,j)!=0) pos[get(n,j)-1]=false;
        if(get(start[i]+n/3, start[j]+n%3)!=0) pos[get(start[i]+n/3, start[j]+n%3)-1]=false;
    }
    for(int n=0; n<9; n++) if(pos[n]) {
        set(i,j,n+1);
        if(i==8 && j==8) return true;
        if(guess(i)) return true;//recurse; gives Stackoverflow at this line
    }
    set(i,j,0);
    return false;
}

Upvotes: 0

Views: 261

Answers (1)

TwoThe
TwoThe

Reputation: 14279

There is no (realistic) way to put this in a loop, but you can circumvent the recursion using a Dequeue approach (in the form of a stack).

First create a class that holds the current state of numbers entered into the Sodoku-field. Then instead of calling set(...) create a copy of that field and set the value in that copy. Then put that copy in a Dequeue and terminate the function.

Your search loop then becomes:

SodokuField field;
while (((field = dequeue.pollLast()) != null) && (field.isComplete() == false)) {
  guess(field);
}
if (field != null) {
  showSolution(field);
}

This approach has two benefits: first you won't get any StackOverflowException anymore, and second: you can easily put the code part above in the run() method of a Runnable and have multiple threads wait on a ConcurrentLinkedDeque.

Note: it is important to work stack-based, as otherwise you would create every possible combination of fields before finding the solution and therefore very soon run into memory issues.

Upvotes: 1

Related Questions