我希望为我的数独求解器优化我的回溯算法。
它现在的作用:
递归求解器函数采用具有各种给定值的数独游戏。
我将遍历拼图中的所有空槽,寻找可能性最小的槽,并获取值列表。
从值列表中,我将通过将列表中的一个值放入槽中来循环遍历它,并递归求解它,直到填满整个网格。
对于一些谜题,这个实现仍然需要非常长的时间,我希望进一步优化它。有谁知道我如何能够进一步优化这个?
如果您有兴趣,这是我的 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;
}