Java数独回溯递归不断给出StackOverflow

Question

我实现了一个SuDoku回溯算法，但它一直给我StackOverflow错误。任何其他方法或算法都可以避免这种情况，因为我无法对此形成一个循环。

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;
}

Answer 1

没有（现实的）方法将其放入循环中，但您可以使用Dequeue方法（以堆栈的形式）来规避递归。

首先创建一个类，保存输入到Sodoku字段中的数字的当前状态。然后不调用set(...)，而是创建该字段的副本并在该副本中设置值。然后将该副本放入Dequeue并终止该函数。

然后您的搜索循环变为：

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

这种方法有两个好处：第一，你不会再得到任何StackOverflowException，第二：你可以很容易地将上面的代码部分放在Runnable的run()方法中，并让多个线程等待ConcurrentLinkedDeque。

注意：基于堆栈的工作很重要，否则在找到解决方案之前会创建所有可能的字段组合，因此很快就会遇到内存问题。