Java 带回溯的数独递归

Sudoku recursion with backtracking

提问by Adam Wechter

I am trying to solve any given sudoku puzzle using a recursive backtracking algorithm. I'm having two problems with my sudoku solver. First off, it solves for the puzzle, however it recurses back up and unsolves it in the process (solves in around 4718 recurses and carries on for another 10000 or so back up for some reason). The second problem stems from my attempt to fix this. I use a global matrix solution to hold the solution once I find it, verifying I have found it using an isSolved method that looks like this:

我正在尝试使用递归回溯算法解决任何给定的数独谜题。我的数独求解器有两个问题。首先，它解决了这个难题，但是它会递归备份并在此过程中解开它（在大约 4718 次递归中解决并由于某种原因继续进行另外 10000 次左右的备份）。第二个问题源于我试图解决这个问题。一旦我找到它，我就使用全局矩阵解决方案来保存解决方案，验证我是否使用如下所示的 isSolved 方法找到了它：

  public static boolean isSolved(int[][]puzzle){
            for(int i = 0; i<9; i++){  //y rotation
                    for(int j = 0; j<8; j++){
                            if(puzzle[i][j]==0){
                                    return false;
                            }
                    }
            }
            return true;
    }

where, in my puzzle, a block with a 0 in it is equivalent of it being empty. However this seems to also get reset although however I cannot find where this is being reset. Any pointers or suggestions or pointers at where I should look?

在我的谜题中，一个带有 0 的块相当于它是空的。然而，这似乎也被重置了，尽管我找不到重置的位置。任何关于我应该看的地方的指示或建议或指示？

Here is my solve method, I have annotated important lines

这是我的解决方法，我已经注释了重要的行

  public static int[][] solve(int[][]puzzle, int x, int y){
            System.out.println("RecrDepth:  " + recDepth);
            recDepth++;
            //using backtracking for brute force power of the gods(norse cause they obviously most b.a.
            ArrayList<Integer> list = new ArrayList<Integer>();
            //next for both  x and y
            int nextx = getNextx(x);
            int nexty = getNexty(x, y);
            while(puzzle[y][x] != 0){  //progress until blank space
                    x = nextx;
                    y = nexty;
                    if(isSolved(puzzle)){
                            System.out.println("resetting solution improperly");
                            solution = puzzle;
                            return puzzle;
                    }
                    nextx = getNextx(x);
                    nexty = getNexty(x, y);
            }
            for(int i = 1; i<10; i++){
                    if(isTrue(puzzle, y, x, i))  //isTrue checks column, row and box so we dont go down unnecessary paths
                            list.add(i);
            }
            for(int i=0; i<list.size(); i++){  //iterating through options in open squre recursing for each one
                    puzzle[y][x]= list.get(i);
                    if(isSolved(puzzle)){
                            System.out.println("Resetting Solution");  //appears to reset solution here but only once that I see in print out
                            solution = puzzle;
                            return puzzle;
                    }
                    System.out.print("=");
                    puzzle = solve(puzzle, nextx, nexty);
                    puzzle[y][x] = 0;//clear spot upon backtracking THIS WAS WHAT I WAS MISSIN
            }
            return puzzle;
    }

Thank you for your time again, the full code and readin file is on github at wechtera/ssolverOO it is the ssolver.java file and the readin is ssolverin.txt

再次感谢您的时间，完整的代码和 readin 文件在 github 上的 wechtera/ssolverOO 它是 ssolver.java 文件，readin 是 ssolverin.txt

采纳答案by Allbeert

If I understood correctly your code, the problems seems to lay on the fact that the recursion is not well implemented, in the sense that your program will keep looping the last for loop even after it has found the right answer.

如果我正确理解您的代码，问题似乎在于递归没有很好地实现，从某种意义上说，即使您的程序找到了正确的答案，它也会继续循环最后一个 for 循环。

Say for instance that in the first blank square, the right number is a 4. But the possible list of numbers (at that point in time) that your program is considering is {2, 4, 6, 7}. In this case, what it seems to happen, is that it will find indeed the right answer at 4, and it will generate the correct output. But it will still check for 6 and 7. And since it will (of course) fail to find any answer, it will leave the inputs blank, giving you back the original board.

例如，在第一个空白方块中，正确的数字是 4。但是您的程序正在考虑的可能的数字列表（在那个时间点）是 {2, 4, 6, 7}。在这种情况下，它似乎会在 4 处找到正确的答案，并且会生成正确的输出。但它仍然会检查 6 和 7。而且由于它（当然）找不到任何答案，它会将输入留空，让您返回原始板。

Now, although I think you had to some extent the right idea in setting a global variable to store the actual answer. The problem is that you're not generating a copy of the array, and you're simply copying the pointer (reference) to it.

现在，尽管我认为您在设置全局变量来存储实际答案时在某种程度上是正确的。问题是您没有生成数组的副本，而只是将指针（引用）复制到它。

You could simply create a copy method to actually copy the entire array, but keep in mind that even if you do generate the correct answer, your algorithm will still needlessly loop and waste time.

您可以简单地创建一个复制方法来实际复制整个数组，但请记住，即使您确实生成了正确的答案，您的算法仍然会不必要地循环并浪费时间。

For reference, here's the solve method I wrote, where my isValid() method is equivalent to your isTrue() :

作为参考，这是我编写的解决方法，其中我的 isValid() 方法等效于您的 isTrue() ：

public static final int SIZE = 9;

public static boolean solve(int[][] s) {

    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            if (s[i][j] != 0) {
                continue;
            }
            for (int num = 1; num <= SIZE; num++) {
                if (isValid(num, i, j, s)) {
                    s[i][j] = num;
                    if (solve(s)) {
                        return true;
                    } else {
                        s[i][j] = 0;
                    }
                }
            }
            return false;
        }
    }
    return true;
}