具有反向跟踪的数独求解算法 [英] Sudoku solving algorithm with back-tracking

问题描述

我正在寻求实现一种非常简单的算法，该算法使用强力反向跟踪来解决数独网格。我面临的问题是，在我的实现中，我为 Sudoku 类包含了两个实例变量，名为 row 和 col ，它对应于表示数独网格的二维数组中空单元格的行和列。

I'm looking to implement a very simple algorithm that uses brute-force back-tracking to solve Sudoku grids. The problem I'm facing is that in my implementation I included two instance variables for a Sudoku class called row and col, which correspond to the row and column of an empty cell in a two dimensional array that represents the Sudoku grid.

当我的 solve（）方法执行时，首先检查是否有空单元格，在这种情况下拼图已经完成。否则，同一方法将空单元格的行和列分配给<的实例变量 row 和 col code> Sudoku 包含网格的对象。之后，for循环通过方法调用 isSafe（int n）验证可以在该空单元格中放置哪个数字（此方法检查拼图的约束是否为满足，我可以保证它的功能完美）。因此， isSafe（）方法在空单元格中放置一个数字，然后对 solve（） Sudoku 对象上的>方法。

When my solve() method executes it first checks to see if there aren't any empty cells, in which case the puzzle is already complete. Otherwise, that same method assigns the row and column of an empty cell to the instance variables row and col of the Sudoku object that contains the grid. Afterwards, the for loop verifies which number can be placed in that empty cell through a method call isSafe(int n) (This method checks to see if the constraints of the puzzle are being met, I can guarantee that it functions perfectly). So, the isSafe() method places a number in the empty cell and then makes a recursive call to the solve() method again on the Sudoku object.

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

If we hit a constraint that can't be met, then we reassign a 0 to the last row and col that was filled. This is where the problem is found! Since the program is constantly updating the row and col variables then the old instances are lost with each recursive call. I have been trying to figure out how to store this values so the program can undo actions when it back-tracks. I thought about pushing each col and row to a stack but I'm really not sure where to go.

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

Can somebody tell me what would be a simple way to approach this problem? I'm not including the entire class, if you think it'd be helpful let me know and I'll post it.

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（）操作后，按行和 col 整数到堆栈上。继续这样做，然后修改以下代码行

---

If I were to implement a stack, does the following make sense? After the findNextZero() operations push the row and col integers onto the stack. Keep doing this and then modify the following line of code

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

类似

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

这是一种合理的方法吗？

Is this a reasonable approach?

推荐答案

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

Actually, you don't really need a stack or recursion. You just need an ordered way to visit the cells (see code below). This solution will not give you stackoverflow like a recursive version would.

我会创建一个初始矩阵来标记预解码的单元格：

I would create an initial matrix to label pre-solved cells:

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

然后根据您的回溯来前进或后退单元格：

Then go forwards or backwards through the cells based on if you are backtracking:

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

这篇关于具有反向跟踪的数独求解算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！