具有反向跟踪的数独求解算法

Question

我正在寻求实现一个非常简单的算法,该算法使用强力反向跟踪来解决数独网格.我现在面临的问题是,我在执行中,我有两个实例变量Sudoku称为类row和col,对应于空单元格的行和列在代表数独网格二维数组.

当我的solve()方法执行时,它首先检查是否没有任何空单元格,在这种情况下拼图已经完成.否则,同一方法将空单元格的行和列分配给实例变量row和包含网格col的Sudoku对象.之后,for循环验证通过方法调用可以在该空单元格中放置哪个数字isSafe(int n)(此方法检查是否满足拼图的约束,我可以保证它完美地运行).因此,该isSafe()方法在空单元格中放置一个数字,然后solve()在该Sudoku对象上再次对该方法进行递归调用.

如果我们遇到了无法满足的约束,那么我们将a重新分配0给最后一个row并且col填充了.这就是问题所在!由于程序不断更新row和col变量,因此每次递归调用都会丢失旧实例.我一直在试图弄清楚如何存储这些值,以便程序可以在回溯时撤消操作.我想过互推col及row到堆栈,但我真的不知道该去哪里.

有人能告诉我解决这个问题的简单方法是什么？我不包括整个班级,如果你觉得它有用,请告诉我,我会发布.

class Sudoku {
    int SIZE, N, row, col;
    int Grid[][];    

    public boolean solve() {
        if (!this.findNextZero()) return true;

        for (int num = 1; num <= 9; num++) {
            if (isSafe(num)) {
                this.Grid[this.row][this.col] = num;

                if (this.solve()) return true;

                this.Grid[this.row][this.col] = 0;
                // this.Grid[oldRow][oldCol] = 0;
            }
        }
        return false;
    }

    public boolean findNextZero() {
        for (int i = 0; i < this.N; i++) {
            for (int j = 0; j < this.N; j++) {
                if (this.Grid[i][j] == 0) {
                    this.row = i;
                    this.col = j;
                    return true;
                }
            }
        }
        return false;
    }

    public boolean isSafe(int num) {
        return !this.usedInRow(num) 
                && !this.usedInColumn(num) 
                && !this.usedInBox(num);
    }

---

如果我要实现堆栈,以下是否有意义？findNextZero()操作后将整数row和col整数推入堆栈.继续这样做,然后修改以下代码行

this.Grid[this.row][this.col] = 0;

喜欢的东西

this.Grid[s.pop][s.pop] = 0;

这是一种合理的方法吗？

Answer 1

实际上，您并不真正需要堆栈或递归。您只需要一种有序的方式来访问单元格（请参见下面的代码）。这个解决方案不会像递归版本那样给你带来 stackoverflow。

我将创建一个初始矩阵来标记预先解决的单元格：

public boolean[][] findSolved(int[][] grid){
    boolean[][] isSolved = new boolean[9][9];        

    for(int i=0; i<9; i++)
        for(int j=0; j<9; j++)
            isSolved[i][j] = grid[i][j] != 0;

    return isSolved;
}

然后根据您是否要回溯，向前或向后浏览单元格：

public boolean solve(int[][] grid){
    boolean[][] isSolved = findSolved(grid);
    int row, col, k = 0;
    boolean backtracking = false;

    while( k >= 0 && k < 81){
        // Find row and col
        row = k/9;
        col = k%9;

        // Only handle the unsolved cells
        if(!isSolved[row][col]){
            grid[row][col]++;

            // Find next valid value to try, if one exists
            while(!isSafe(grid, row, col) && grid[row][col] < 9)
                grid[row][col]++;

            if(grid[row][col] >= 9){
                // no valid value exists. Reset cell and backtrack
                grid[row][col] = 0;
                backtracking = true;
            } else{
                // a valid value exists, move forward
                backtracking = false;
            }
        }

        // if backtracking move back one, otherwise move forward 1.
        k += backtracking ? -1:1
    }

    // k will either equal 81 if done or -1 if there was no solution.
    return k == 81;
}