优化解决Sudoku的回溯算法
我希望优化我的数独求解器的回溯算法。
它现在做什么：
递归求解器函数对各种给定值进行数独拼图。
我将通过拼图中的所有空插槽进行搜索，寻找具有最小可能性的插槽，并获取值列表。
从值列表中，我将遍历它，方法是将列表中的一个值放在插槽中，并递归解决它，直到整个网格被填充。
这个实现对于一些难题仍然需要很长的时间，我希望能够进一步优化。 有没有人有任何想法，我可能会进一步优化呢？
如果你有兴趣，这是我的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/
很长一段时间，我写了一个Sudoku求解器（几年前，但我保留了所有我写的代码）。 它没有被普遍地解释为比通常的数独更大的尺寸，但它非常快。
它在103毫秒（在Core 2 Duo 1.86 Ghz上）解决以下问题，并且还没有进行优化：
{0,0,0,0,7,0,9,4,0},
{0,7,0,0,9,0,0,0,5},
{3,0,0,0,0,5,0,7,0},
{0,8,7,4,0,0,1,0,0},
{4,6,3,0,0,0,0,0,0},
{0,0,0,0,0,7,0,8,0},
{8,0,0,7,0,0,0,0,0},
{7,0,0,0,0,0,0,2,8},
{0,5,0,2,6,8,0,0,0},
你的速度有多快，哪个板子速度慢？ 你确定你不是经常重新访问不应该重新访问的路径吗？
这是算法的肉：
private static void solveRec( final IPlatform p ) {
if (p.fullBoardSolved()) {
solved = p;
return;
}
boolean newWayTaken = false;
for (int i = 0; i < 9 && !newWayTaken; i++) {
for (int j = 0; j < 9 && !newWayTaken; j++) {
if (p.getByteAt(i, j) == 0) {
newWayTaken = true;
final Set<Byte> s = p.avail(i / 3, j /3);
for (Iterator<Byte> it = s.iterator(); it.hasNext();) {
final Byte b = it.next();
if (!p.columnContains(j, b) && !p.lineContains(i, b)) {
final IPlatform ptemp = duplicateChangeOne(p, b, i, j);
solveRec(ptemp);
if (solved != null) {
return;
}
}
}
}
}
}
}
和IPlatform抽象（请写得很好，这是很多年前写的，在我知道在Java中添加'I'之前并不是所有的界面名称都是这样）：
public interface IPlatform {
byte getByteAt(int i, int j);
boolean lineContains(int line, int value);
boolean columnContains(int column, int value);
Set<Byte> avail(int i, int j);
boolean fullBoardSolved();
}
在每个非确定性步骤之前做一些约束传播。
在实践中，这意味着你有一些检测强制值并插入它们的规则，并且只有当这些规则不再取得进展时，才会求助于通过可能的值进行回溯搜索。
人类大多数数独谜题的设计都是为了让他们根本不需要回溯。
链接地址: http://www.djcxy.com/p/96153.html