java - 我的回溯算法有什么问题？ (数独求解器，计算器)

Question

下面是一个用回溯算法解决数独的方法..或者这就是我想要做的

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

但是当我运行它时，它给了我 stackoverflow。 stackoverflow 指向带有“递归”注释的 fillGrid(a) 和 (!find(a))。查找方法如下:

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

任何人请告诉我代码有什么问题？

Answer 1

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

你确定这总是保证是真的吗？如果不是，则 a 的状态在下一次调用 fillGrid(a) 之前不会改变，我们回到原点，使用相同的输入调用相同的方法。这会导致计算器溢出。