数独回溯解法算法

Question

数独回溯解法算法

9

我想实现一个使用暴力回溯算法来解决数独网格的简单算法。我遇到的问题是，在我的实现中，我为Sudoku类包含了两个实例变量，称为row和col，它们对应于表示数独网格的二维数组中空单元格的行和列。

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

如果我们遇到无法满足的约束，则将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;

这种方法合理吗？

- Macalaca

在方法isSafe中有什么，请先发布代码。 - Mengjun

已发布！从isSafe()调用的三种方法仅检查网格是否满足数独问题的约束条件。 - Macalaca

使用堆栈是一个不错的方法。 - newtonrd

我认为你要么需要调用一个递归函数，要么在遍历时将未解决的节点添加到一个堆栈中，并在无法满足约束条件时进行弹出。 - bcorso

你可以发布完整的代码吗？ - Nishant Lakhara

显示剩余2条评论

2个回答

1

我能够通过在Sudoku类的Stack实例变量中存储“行”和“列”的空单元格的值，来避免每次递归调用时都会丢失它们。findNextZero()方法将“行”和“列”值推入两个空栈中。然后，我重新组织了程序的其余部分，通过peek()方法访问这些信息，在需要回溯时，我只需弹出最后两个值，并将对应于那些值的网格上的数字设置为0。

- Macalaca

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- bcorso · Accepted Answer

实际上，您并不需要使用堆栈或递归。您只需要按照一定顺序访问单元格（请参见下面的代码）。这种解决方案不会像递归版本那样导致堆栈溢出。

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

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