1

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

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

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

因此，我在 Internet 上搜索了提示，发现这是一个有据可查且经常解决的问题。然而，许多解决方案声称使用回溯，即使我面前有源代码，我也看不出他们是如何或在哪里做的。

例如：Java 中的数独求解器，使用回溯和递归或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;
}
4

3 回答 3

1

进行回溯的最简单方法是使用堆栈。让您的数独板成为一类，包括所有确定的数字和可能的数字。每当您需要选择一个数字时，您都会创建一个板的副本。一个副本将您在该方格中选择的数字标记为不可选择（您不想选择两次），然后将该副本放入堆栈。第二个副本您选择号码并照常进行。

每当你走到死胡同时，你就扔掉你正在处理的板子，从堆栈中取出最上面的板子，然后继续那个板子。这是“回溯”部分：您回到以前的状态并再次尝试不同的路径。如果您之前选择了 1 但它不起作用，那么您从同一位置重试，但选择 2。

如果数独是可解的，那么您最终会来到一个可以填写所有数字的板上。那时，您可以丢弃堆栈中剩余的任何零件板，因为您不需要它们。

如果您只是想生成可解的数独，那么您可以作弊，请参阅以下答案：如何生成具有独特解决方案的数独板

于 2016-02-07T15:22:31.713 回答
1

我只是解释一下回溯的含义。

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

返回的唯一方法是使用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; 我没有阅读您的代码，因此可能会有更多类似的错误。

于 2016-02-07T15:23:23.410 回答
0

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

调用 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 
            }
        }
    }
}

这当然只是勾勒出递归代码轮廓的低效示例。然而，我希望这显示了一种使用递归来调查所有可能性（给定棋盘和状态）的方法，同时在给定状态不具备解决方案的情况下启用回溯。

于 2016-02-07T21:57:36.877 回答