如何通过回溯和递归来解数独？

Question

我创建这个新线程而不是仅仅阅读之前给出的这个特定问题的答案的原因是我觉得我只是不完全理解它背后的整个想法。我似乎无法理解整个回溯概念。所以我需要充分理解回溯，然后解决特定的数独问题。

到目前为止我所理解的是，回溯是一种返回的技术，如果发现在当前状态之前做出的决定导致死胡同，则在（例如）递归流中。所以你回去尝试别的东西，然后再继续。

因此，在我的数独示例中，我选择了第一个空单元格，并尝试从 {1...9} 中填充一个自然数，这与众所周知的数独规则不冲突。现在我对下一个空单元格做同样的事情，直到我到达没有冲突的情况下不能插入有效数字的地步。据我了解，这应该是回溯发挥作用的地方。但是怎么办？如果我使用递归返回到最后写入的单元格，算法将再次填充数字，继续并最终陷入无限循环。

所以我在 Internet 上搜索提示，发现这是一个有据可查且经常被解决的问题。然而，许多解决方案声称使用回溯，即使我有源代码，我也看不到他们是如何或在何处使用回溯的。

例如：Sudoku solver in Java, using backtracking and recursion or http://www.heimetli.ch/ffh/simplifiedsudoku.html

这是我的（不工作的）源代码：

private boolean isSolvable( Sudoku sudoku, int row, int col ){

    //if the method is called for a row > 8 the sudoku is solved
    if(row > 8)
        return true;

    //calculate the next cell, jump one row if at last column
    int[] nextCell = (col < 8) ? new int[]{row,col+1} : new int[]{row+1,0};

    //check if the current cell isWritable() that is if it is not a given cell by the puzzle
    //continue recursively with the next cell if not writable
    if(!sudoku.isWritable(row, col))
        isSolvable(sudoku, nextCell[0], nextCell[1]);
    else{
        //set the current cell to the lowest possible not conflicting number
        for(int i=1; i< 10; i++){
            if(!conflictAt(sudoku, row, col, i)){
                sudoku.setValue(row, col, i);

                //continue recursively with the next cell
                isSolvable(sudoku, nextCell[0], nextCell[1]);
            }
        }
    }

    return false;
}

现在我不知道如何继续。如何实施回溯或我已经实施了？这似乎是一个愚蠢的问题，但我真的没有看到在上面链接中提到的源代码中有更多的回溯。

编辑：最终（工作）版本：

private boolean isSolvable( Sudoku sudoku, int row, int col ){

    //if the method is called for a row > 8 the Sudoku is solved
    if(row > 8)
        return true;

    //if the cell is not writable, get the next writable cell recursively
    if(!sudoku.isWritable(row,col))
        return isSolvable(sudoku, (col<8) ? row : row + 1, (col<8) ? col + 1 : 0);

    //brute forcing for solution
    for(int i=1; i<=9; i++){
        if(!conflictAt(sudoku, row, col, i)){
            sudoku.setValue(row, col, i);
            if(isSolvable(sudoku, (col<8) ? row : row + 1, (col<8) ? col + 1 : 0)) return true; 
        }
    }
    sudoku.setValue(row, col, 0);
    return false;
}

Answer 1

实现回溯的最简单方法是使用堆栈。让你的数独板成为 class，包括所有的确定数和可能数。每当您需要选择一个数字时，您都会创建一个看板副本。一份有你在那个方块中选择的数字标记为不可选择（你不想选择它两次）和你放在堆栈上的那个副本。第二本你选号码照常进行。

每当你走到死胡同时，你就会扔掉你正在处理的板，从堆栈中取出最上面的板，然后继续处理那块板。这是 "backtracking" 部分：你回到以前的状态，然后沿着不同的路径再次尝试。如果您之前选择了 1 但没有成功，那么您可以从相同的位置重试，但改为选择 2。

如果数独是可解的，那么您最终会来到一个可以填写所有数字的棋盘。那时你可以扔掉堆栈中剩余的任何部分板，因为你不需要它们。

如果您只是想生成可解的数独，那么您可以作弊，请参阅以下答案：How to generate Sudoku boards with unique solutions

Answer 2

我只是想解释一下回溯是什么意思。

递归意味着从同一个函数中调用函数。现在发生的事情是，当函数遇到对自身的调用时......想象一下，一个新页面打开并且控制权从旧页面转移到这个新页面到函数的开始，当函数再次遇到调用时新页面，另一个页面在它旁边打开，这样新页面不断在旧页面旁边弹出。

返回的唯一方法是使用 return 语句。当函数遇到它时，控件会从新页面返回到调用它的同一行上的旧页面，并开始执行该行下方的任何内容。这是回溯开始的地方。为了避免在数据填满时再次输入数据等问题，您需要在每次调用该函数后放置一个 return 语句。

例如在您的代码中

if(row > 8)
        return true;

这是基本情况。当它为真时，该函数开始回溯，即控制从新页面返回到旧页面，但它返回到调用它的地方。例如，如果它是从此语句中调用的。

 for(int i=1; i< 10; i++){
            if(!conflictAt(sudoku, row, col, i)){
                sudoku.setValue(row, col, i);

                //continue recursively with the next cell
                isSolvable(sudoku, nextCell[0], nextCell[1]);  <------ here
            }

它将回到这一行并开始做它应该做的事。此语句在 for 循环内，如果 i < 10 循环将运行并尝试再次设置值。那不是您想要的，您希望它继续回溯直到它退出函数，因为数独已填满，对吗？为此，您需要在此调用后添加一个 return 语句，即 return true; 我还没有阅读您的代码，因此可能会有更多类似的错误。

Answer 3

我认为递归和回溯的方式如下：

调用 isSolvable() 应该尝试将数独作为第一个参数，并从特定的行和列解决它（从而假设所有先前的值都已确定且有效）。

计算出数独的完整解决方案类似于以下代码。如果我理解 rossum 正确的话，这多少有点概括了同样的想法：

// you are handed a sudoku that needs solving
Sudoku sudoku; 
for (int row=0; row <= 9; row++) {
    for (int col=0; col <= 9; col++) {
        for (int value_candidate = 1; value_candidate <= 10; value_candidate++) {

            // or any other type of deep-copy 
            Sudoku sudokuCopy = sudoku.clone(); 
            sudokuCopy.setValue(row, col, value_candidate);

            if (isSolvable(sudokuCopy, row, col)) { // (recursion)

                // only if the value_candidate has proven to allow the                  
                // puzzle to be solved, 
                // we persist the value to the original board

                sudoku.setValue(row, col, value_candidate);

                // and stop attempting more value_candidates for the current row and col 
                // by breaking loose of this for-loop
                continue;
            } else { // (backtracking)

                // if the value_candidate turns out to bring no valid solution
                // move on to the next candidate while staying put at 
                // the current row and col 
            }
        }
    }
}

这当然只是围绕递归的代码大纲的低效示例。然而，我希望这展示了一种使用递归来调查所有可能性（给定棋盘和状态）的方法，同时在给定状态不支持解决方案的情况下启用回溯。

如何通过回溯和递归来解数独？

How to solve Sudoku by backtracking and recursion?

java

recursion

sudoku

backtracking

recursive-backtracking