数独回溯递归算法

Question

数独回溯递归算法

3

我正在尝试使用递归回溯算法解决任何给定的数独谜题。我的数独求解器有两个问题。首先，它可以解决谜题，但在过程中递归返回并取消解决（大约在4718次递归后解决，并继续进行另外10000次左右的递归）。第二个问题源于我尝试解决这个问题。我使用全局矩阵 solution 来保存找到的解决方案，并使用类似于以下内容的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;
    }

再次感谢您的时间，完整的代码和读取文件已经放在Github上的wechtera/ssolverOO上，其中ssolver.java是代码文件，ssolverin.txt是读取文件。

- Adam Wechter

你是什么意思说“它正在被重置”？ - bas

它解决了问题，然后将其恢复为原始的空谜题，只保留原始点。 - Adam Wechter

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Allbeert · Accepted Answer

如果我正确理解了你的代码，问题似乎在于递归没有很好地实现，也就是说，即使程序已经找到了正确的答案，它仍然会保持最后一个for循环的循环。例如，在第一个空格中，正确的数字是4。但是你的程序正在考虑的可能数字列表（在那个时间点上）是{2, 4, 6, 7}。在这种情况下，它似乎确实会在4处找到正确的答案，并生成正确的输出。但它仍然会检查6和7。由于它（当然）无法找到任何答案，因此它将留下输入为空，将原始面板返回给您。

现在，尽管我认为你在设置全局变量以存储实际答案方面有一定正确的想法。但问题在于你没有生成数组的副本，而只是复制了指针（引用）。

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

供参考，这是我编写的solve方法，其中我的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;
}