我希望为我的Sudoku Solver优化我的回溯算法.
它现在做了什么:
递归求解器函数采用具有各种给定值的数独谜题.
我将遍历拼图中的所有空槽,寻找可能性最小的槽,并获取值列表.
从值列表中,我将通过将列表中的一个值放入插槽中来循环遍历它,并递归地求解它,直到填满整个网格.
对于一些难题,这种实现仍然需要非常长的时间,我希望进一步优化这一点.有没有人有任何想法我怎么能够进一步优化这个？
如果您有兴趣,这是我的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;
}
我有一个任务就是这样做:用Java构建最快的数独求解器.我最终以0.3毫秒的时间赢得了比赛.
我没有使用跳舞链接算法并且没有与它进行比较,但是一些参赛者必须尝试过,但我最接近的竞争对手花了大约15毫秒.
我简单地使用递归回溯算法,用4个"规则"对其进行扩充(这使得几乎每个谜题都不需要回溯)并且将一个字段保存为每个位置的合法值列表.
我写了一篇关于它的博客文章并在此处发布了代码:http://www.byteauthor.com/2010/08/sudoku-solver/
我最近用 Python 编写了一个可以解决数独谜题的程序。它基本上是一种蛮力搜索空间的回溯算法。我在此线程中发布了有关实际算法的更多详细信息。
然而，在这里我想更多地关注优化过程。更准确地说，我探索了不同的方法来最小化求解时间和迭代次数。这更多是关于可以进行的算法改进，而不是编程改进。
所以仔细想想，回溯蛮力算法中可以优化的东西并不多（很高兴在这里被证明是错误的）。可以进行的两个真正改进是：第一，选择下一个空白单元格的方法，第二，选择下一个可能数字的方法。这两个选择可以区分沿着死胡同的搜索路径还是沿着以解决方案结尾的搜索路径。
接下来，我坐下来尝试为上述两种选择想出不同的方法。这是我想出的。
可以通过以下方式选择下一个空白单元格：
可以通过以下方式选择下一位：
所以我把上面的方法都编进了程序中。前面的数字和字母可以作为参数传递给程序，它会使用相应的优化方法。更重要的是，因为有时两个或多个单元格可能具有相同的分数，所以可以选择提供第二个排序参数。例如，参数“EC”意味着从所有可用选项最少的单元格中随机选择一个单元格。
第一个函数将分配乘以 1000 的权重，第二个函数将添加乘以 1 的新权重。 因此，例如，如果第一个函数中的三个单元格具有相同的权重，例如 3000、3000 3000，则第二个函数将添加其自己的体重。例如 3111、3256、3025。排序将始终选择最低的权重。如果需要相反，则使用 -1000 amd -1 调用权重函数，但排序仍然选择最低权重。
在继续之前值得一提的是，该程序将始终选择一个空白单元格（而不是填充的单元格），并且将始终选择一个在单元格当前数独限制范围内的数字（否则这样做是不合理的）。
有了上述内容，然后我决定使用每种可能的参数组合运行程序，看看会发生什么，哪些表现最好 - 基本上是蛮力的蛮力:) 有 12 种单元格选择方法和 11 种数字选择方法所以理论上有 17,424 种组合可以尝试，但我删除了一些不必要的（例如“AA”、“BB”等，也排除了随机方法，因为它们都非常低效），因此组合的数量最后是 12,100。每次运行都在同一个数独谜题上完成，这很简单：
0,3,0,0,9,0,6,1,0
6,0,8,5,0,3,4,9,7
0,9,0,6,7,0,0,0,3
0,5,0,8,0,4,0,0,1
1,6,0,3,0,0,9,8,2
0,0,2,9,6,0,3,0,0
0,8,0,1,3,0,2,0,6
3,0,5,0,4,6,0,7,9
0,4,6,0,8,0,1,0,0
...搜索空间为 36,691,771,392。这只是给定谜题的每个空白单元格的选择数量的简单乘积。这是一种夸大的说法，因为一旦填充了一个单元格，这就会减少其他单元格的选择数量，但这是我能想出的最快和最简单的分数。
我写了一个简短的脚本（当然是 Python），它自动化了整个测试过程——它为每组参数运行求解器，记录完成时间并将所有内容转储到一个文件中。此外，我决定每次运行 20 次，因为我从 time.time() 函数中获得了 0 次单次运行。而且，如果任何组合的完成时间超过 10 秒，脚本将停止并移至下一个。
该脚本在配备 Intel Core i7-4712MQ 2.30GHz 的笔记本电脑上在 13:04:31 小时内完成，使用的内核不超过 8 个内核中的 2 个，平均 CPU 负载约为 12%。12,100 个组合中有 8,652 个在 10 秒内完成。
获胜者是：（*针对单次运行时间/迭代调整回来的数字）
1) 最快时间 1.55 ms：“A0”和“A1”具有 84 次迭代和 46 次回溯迭代以及“B0”、“B01”、“B1”、“B10”、“BA01”、“BA1”、“BD01” , "BD1" 和 "BD10" 65 次迭代和 27 次回溯迭代 最快的方法是最简单的方法，如 A、B 和 D。另一种方法直到排名位置 308 才出现，即“E0”。
2) 38 次和 0 次回溯迭代的最少迭代：令人惊讶的是，许多方法都设法实现了这一点，最快的方法是“B17”、“B6”、“B7”、“BA16”、“BA60”、“BA7”、“BD17”和“BD70”的时间为2.3毫秒，最慢的是“IK91”、“JK91”、“KI91”、“KJ91”、“KJ9a”、“IK9a”、“JK9a”和“KI9a”，时间约为107多发性硬化症。同样令人惊讶的是，方法 F 在这里有一些不错的位置，例如 7 毫秒的“FB6”（???）
总体而言，A、B、D、E、G 和 K 的表现似乎明显优于 C、F、H 和 L，而 I 和 J 介于两者之间。此外，数字的选择似乎并不重要。
最后，让我们看看这些赢家方法如何处理世界上最难的数独谜题，如本文所述http://www.telegraph.co.uk/news/science/science-news/9359579/Worlds-hardest-sudoku-can -you-crack-it.html * 考虑到算法并非普遍快速，也许某些算法在某些数独谜题上做得更好，但在其他数独谜题上则不然......谜题是：
8,0,0,0,0,0,0,0,0
0,0,3,6,0,0,0,0,0
0,7,0,0,9,0,2,0,0
0,5,0,0,0,7,0,0,0
0,0,0,0,4,5,7,0,0
0,0,0,1,0,0,0,3,0
0,0,1,0,0,0,0,6,8
0,0,8,5,0,0,0,1,0
0,9,0,0,0,0,4,0,0
...搜索空间为 95,865,912,019,648,512 x 10^20。
获胜者是“A0”，在 1092 毫秒内完成了 49,559 次迭代和 49,498 次回溯迭代。其他的大部分都做得不太好。“A0”、“A1”、“B0”、“B01”、“B1”、“B10”、“BA01”、“BA1”、“BD01”、“BD1”和“BD10”在大约 2500 ms 和 91k 内完成迭代，其余 30+ 秒，400k+ 次迭代。
但这还不够，所以我也对最难数独的所有参数集进行了全面测试。这次做单跑不是20，也是2.5秒的截止时间。脚本在 8:23:30 小时内完成。12,100 个组合中有 149 个在 2.5 秒内完成。两个类别的获胜者是“E36”、“E37”、“EA36”和“EA37”，时间为 109 ms，362 次迭代和 301 次回溯迭代。此外，前 38 个位置以开头的“E”为主。
总体 E 位居图表之首，毫无疑问，只需查看汇总电子表格即可。A、B、I 和 J 有一些排名，但没什么，其余的甚至没有在 2.5 秒内完成一次。
总而言之，我认为可以肯定地说，如果数独谜题很简单，那么用最简单的算法对其进行暴力破解，但如果数独谜题很难，那么花费选择方法的开销是值得的。
希望这可以帮助 ：）
您可能应该使用分析器来查看哪个语句花费的时间最多，然后考虑如何优化它。
如果不使用探查器，我的建议是您每次都从头开始创建一个新的 PuzzleGenerator，并将槽作为参数传递给 possibleValuesInGrid 方法。我认为这意味着 PuzzleGenerator 每次都会从头开始重新计算每个位置和每个插槽配置的所有内容；相反，如果它记住以前的结果并逐步改变，它可能会更有效。