algorithm - 优化回溯算法求解数独

Question

我希望为我的数独求解器优化我的回溯算法。

---

它现在做什么:

递归求解器函数采用具有各种给定值的数独游戏。

我将搜索拼图中的所有空槽，寻找可能性最少的槽，并获得值列表。

从值列表中，我将通过将列表中的一个值放入槽中来循环遍历它，并递归求解它，直到填满整个网格。

---

这个实现对于一些谜题来说仍然需要很长时间，我希望进一步优化它。有谁知道我可以如何进一步优化它？

---

如果您有兴趣，这是我用 Java 编写的代码。

public int[][] Solve(int[][] slots) {
    // recursive solve v2 : optimization revision

    int[] least = new int[3];
    least[2] = Integer.MAX_VALUE;
    PuzzleGenerator value_generator = new PuzzleGenerator();
    LinkedList<Integer> least_values = null;

    // 1: find a slot with the least possible solutions
    // 2: recursively solve.

    // 1 - scour through all slots.
    int i = 0;
    int j = 0;
    while (i < 9) {
        j = 0;
        while (j < 9) {
            if (slots[i][j] == 0) {
                int[] grid_posi = { i, j };
                LinkedList<Integer> possible_values = value_generator
                        .possibleValuesInGrid(grid_posi, slots);
                if ((possible_values.size() < least[2])
                        && (possible_values.size() != 0)) {
                    least[0] = i;
                    least[1] = j;
                    least[2] = possible_values.size();
                    least_values = possible_values;
                }
            }
            j++;
        }
        i++;
    }

    // 2 - work on the slot
    if (least_values != null) {
        for (int x : least_values) {
            int[][] tempslot = new int[9][9];
            ArrayDeepCopy(slots, tempslot);
            tempslot[least[0]][least[1]] = x;

            /*ConsoleInterface printer = new gameplay.ConsoleInterface();
            printer.printGrid(tempslot);*/

            int[][] possible_sltn = Solve(tempslot);
            if (noEmptySlots(possible_sltn)) {
                System.out.println("Solved");
                return possible_sltn;
            }
        }
    }
    if (this.noEmptySlots(slots)) {
        System.out.println("Solved");
        return slots;
    }
    slots[0][0] = 0;
    return slots;
}

Answer 1

我有一项任务要做:用 Java 构建最快的数独解算器。我最终以 0.3 毫秒的时间赢得了比赛。

我没有使用跳舞链接算法，也没有与之进行比较，但肯定有参赛者尝试过，但我最接近的竞争对手用了大约 15 毫秒。

我只是使用了一个递归回溯算法，增加了 4 个“规则”(这使得几乎每个谜题都不需要回溯)并保留一个位字段作为每个位置的合法值列表。

我写了一篇关于它的博文:http://byteauthor.com/2010/08/sudoku-solver/

并在此处发布代码:https://github.com/stonkie/SudokuSolverV1