优化回溯算法解决数独 [英] Optimizing the backtracking algorithm solving Sudoku
问题描述
我希望能优化我的回溯算法为我的数独解算器。
现在它做什么：
递归求解器函数采用一个数独谜题各种给定的值。
我会通过冲刷谜题中的空插槽，寻找具有最小的可能性插槽，并获得值的列表。
从值的列表中，我会遍历它放置在列表中的插槽中的一个值，并递归解决它，直到整个网格填充。
本实施仍需要极长的一些困惑，我希望能进一步优化此。没有人有任何想法如何，我也许可以进一步优化呢？
下面是我的code在Java中，如果你有兴趣。
公众诠释[] []解决（INT [] []插槽）{
//递归解决V2：优化改版
INT []至少=新INT [3];
至少[2] = Integer.MAX_VALUE的;
PuzzleGenerator value_generator =新PuzzleGenerator（）;
链表＆LT;整数GT; least_values = NULL;
// 1：找到用最少的可能解决方案的槽
// 2：递归解决。
// 1 - 冲刷过的所有插槽。
INT I = 0;
INT J = 0;
而（ⅰ＆10 9）{
J = 0;
而（J＆LT; 9）{
如果（插槽[I] [J] == 0）{
INT [] grid_posi = {I，J};
链表＆LT;整数GT; possible_values = value_generator
.possibleValuesInGrid（grid_posi，插槽）;
如果（（possible_values.size（）＆其中;至少[2]）
＆功放;＆安培; （possible_values.size（）！= 0））{
至少[0] = I;
至少[1] = j的;
至少[2] = possible_values.size（）;
least_values = possible_values;
}
}
J ++;
}
我++;
}
// 2 - 工作中的插槽
如果（least_values！= NULL）{
对于（INT X：least_values）{
INT [] [] tempslot =新INT [9] [9];
ArrayDeepCopy（插槽，tempslot）;
tempslot [至少[0] [至少[1] = X;
/ * ConsoleInterface打印机=新gameplay.ConsoleInterface（）;
printer.printGrid（tempslot）; * /
INT [] [] possible_sltn =解答（tempslot）;
如果（noEmptySlots（possible_sltn））{
的System.out.println（解决）;
返回possible_sltn;
}
}
}
如果（this.noEmptySlots（槽））{
的System.out.println（解决）;
返回插槽;
}
时隙[0] [0] = 0;
返回插槽;
}
我有一个分配来做到这一点：建立在Java中速度最快的数独解算器。我最终赢得0.3毫秒一次的较量。
我没有用舞蹈链的算法，并没有与它相比，但有些参赛者必须尝试过了，但我最接近的竞争对手花了大约15毫秒。
我只是用一个递归回溯算法，具有4规则（这令回溯不必要的，几乎每一个谜）增强并保持了位字段的合法值的每个位置的列表。
我写了一个关于它的博客文章，并张贴了code在这里：<一href="http://www.byteauthor.com/2010/08/sudoku-solver/">http://www.byteauthor.com/2010/08/sudoku-solver/
I'm hoping to optimize my backtracking algorithm for my Sudoku Solver.
What it does now:
The recursive solver function takes a sudoku puzzle with various given values.
I will scour through all the empty slots in the puzzle, looking for the slot that has the least possibilities, and get the list of values.
From the list of values, I will loop through it by placing one of the values from the list in the slot, and recursively solve it, until the entire grid is filled.
This implementation still takes incredibly long for some puzzles and I hope to further optimize this. Does anyone have any ideas how I might be able to further optimize this?
Here's my code in Java if you're interested.
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;
}
I had an assignment to do just that: build the fastest sudoku solver in Java. I ended up winning the contest with a time of 0.3 millisecond.
I didn't use the dancing links algorithm and didn't compare with it, but some contestants must have tried it, yet my closest competitor took about 15 milliseconds.
I simply used a recursive backtracking algorithm, augmented it with 4 "rules" (which made backtracking unnecessary for almost every puzzle) and kept a bit field as a list of legal values for each position.
I wrote a blog post about it and posted the code here : http://www.byteauthor.com/2010/08/sudoku-solver/
这篇关于优化回溯算法解决数独的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
