3

我正在尝试使用递归回溯算法解决任何给定的数独难题。我的数独求解器有两个问题。首先，它解决了这个难题，但是它会递归备份并在此过程中解决它（解决了大约 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;
    }

在我的谜题中，其中包含 0 的块相当于它是空的。然而，这似乎也被重置了，但我找不到重置的位置。关于我应该看的任何指示或建议或指示？

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

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

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

4

1 回答 1

3

如果我正确理解了您的代码，那么问题似乎在于递归没有很好地实现这一事实，因为即使您的程序找到了正确的答案，它也会继续循环最后一个 for 循环。

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

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

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

作为参考，这是我编写的解决方法，其中我的 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;
}
于 2013-08-12T19:02:45.587 回答