如何通过回溯和递归来解决数独? [英] How to solve Sudoku by backtracking and recursion?

问题描述

我之所以创建这个新线程，而不是仅仅阅读之前针对这个特定问题的答案，是因为我觉得我只是不完全理解其背后的全部想法.我似乎无法理解整个回溯概念.因此，我需要完全了解回溯，然后解决特定的数独问题.

the reason why I am creating this new thread instead of just reading the answers to this particular question that have been given before is that I feel I just don't fully understand the whole idea behind it. I can't seem to get my head around the whole backtracking concept. So I need to fully understand backtracking and then solve the particular sudoku problem.

到目前为止，我了解的是，回溯是一种可以回溯的技术，例如，如果人们发现在当前状态之前做出的决定导致了死胡同，则该回溯是一种递归流程.因此，您返回尝试其他方法，然后再次继续.

What I understand so far is that backtracking is a technique to go back, in (e.g.) a recursive flow if one discovers that decisions made prior to the current state led to a dead end. So you go back try something else and continue again.

因此，在我的数独示例中，我选择了第一个空单元格，并尝试从{1 ... 9}中填充一个自然数，该数与众所周知的数独规则没有冲突.现在，我对下一个空单元格执行相同的操作，直到无法插入有效数字而没有冲突为止.以我的理解，这应该是回溯起作用的地方.但是如何?如果我使用递归返回到最后一个写入的单元格，该算法将再次填写数字，继续并最终陷入无休止的循环.

So in my sudoku example I pick the first empty cell and try to fill in a natural number out of {1...9} that doesn't conflict with the well know sudoku rules. Now I do the same thing with the next empty cell until I get to the point where no valid number may be inserted without conflicts. As of my understanding this should be the point where backtracking comes into play. But how? If I use recursion to go back to the last written cell the algorithm will fill in the number again, continue and end up stuck in an endless loop.

因此，我在Internet上搜索了提示，发现这是一个文档齐全且经常解决的问题.但是许多解决方案声称使用回溯，即使我眼前有源代码，我也看不到它们如何执行或在何处进行.

So I searched the Internet for hints and found this to be a quite well documented and frequently solved problem. Yet many solutions claim to use backtracking I don't see how or where they do it even if I have the source code right in front of me.

示例包括: Java中的Sudoku求解器，使用回溯和递归或 http://www.heimetli.ch/ffh/simplifiedsudoku.html

这是我的(无效的)源代码:

Here is my (not working) source code:

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

现在我不知道如何继续.如何实施回溯?这似乎是一个愚蠢的问题，但是我真的看不到上面链接中提到的源代码中发生了更多的回溯.

Now I don't know how to continue. How to implement the backtracking or did I already? This seems like a stupid question but I really don't see more backtracking going on in source codes mentioned in the links above.

最终(有效)版本:

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

推荐答案

我将解释回溯的含义.

递归表示从同一函数内调用该函数.现在发生的是，当函数遇到对自身的调用时.想象一下，当函数在此再次遇到调用时，会打开一个新页面并将控制权从旧页面转移到该新页面上，直至该函数的开始.新页面，旁边会打开另一个页面，这样，新页面会继续在旧页面旁边弹出.

Recursion means to call the function from within that same function. Now what happens is that when the function encounters a call to itself.. imagine that a new page opens up and control is transferred from the old page onto this new page to the start of the function, when the function encounters the call again in this new page, another page opens up beside it and in this way new pages keep popping up beside the old page.

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

The only way to go back is using return statement. When the function encounters it the control goes from the new page back to the old page on the same line from where it was called and starts executing whatever is below that line. This is where backtracking starts. In order to avoid issues like feeding data again when its filled up you need to put a return statement after every call to the function.

例如在您的代码中

if(row > 8)
        return true;

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

This is the base case. When its true, the function starts backtracking i.e control goes back from the new page to the old page BUT it goes back to from wherever it was called. If for e.g it was called from this statement.

 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;我还​​没有阅读您的代码，因此可能还会有更多类似的错误.

it will go back to this line and start doing whatever it should. This statement is inside the for loop and if i < 10 the loop will run and it will try to set values again. That's not what you want, you want it to keep backtracking till it exits the function because sudoku is filled up right? In order to do that you need to put a return statement after this call i.e return true; I haven't read your code so there might be many more mistakes like that.

这篇关于如何通过回溯和递归来解决数独?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！