我写了一个回溯算法来生成任意大小的数独。我的问题是这个生成算法的变化速度。
我添加了一些控制台输出来查看结果。我生成了大约20个16x16大小的数独，每个数独的生成时间为1到150毫秒下一个花了10多分钟，还没结束。（我停止了程序）。考虑到这一点，我认为我在回溯实现中犯了一个错误，这妨碍了算法的前进。
代码如下：
public class Generator {
public static NormalSudoku generateNormal(int size) {
NormalSudoku ns = new NormalSudoku(size);
boolean[][][] track = new boolean[size][size][size];
ArrayList<Integer> vals = new ArrayList<Integer>();
fill(vals, size);
int row = 0;
int col = 0;
int val = 0;
int count = 0;
while (row < size) {
boolean found = false;
while (!vals.isEmpty() && !found) {
val = vals.get((int) (Math.random() * vals.size()));
track[row][col][val - 1] = true;
if (ns.checkValue(row, col, val)) {
ns.setValue(row, col, val);
fill(vals, size);
col++;
found = true;
} else {
vals.remove(Integer.valueOf(val));
}
if (col >= size) {
row++;
col = 0;
}
}
if (vals.isEmpty()) {
ns.setValue(row, col, 0);
for (int i = 0; i < size; i++) {
track[row][col][i] = false;
}
col--;
if (col < 0) {
row--;
col = size - 1;
}
ns.setValue(row, col, 0);
fill(vals, track, row, col);
}
}
return ns;
}
private static void fill(ArrayList<Integer> vals, int size) {
vals.clear();
for (int i = 1; i <= size; i++) {
vals.add(i);
}
}
private static void fill(ArrayList<Integer> vals, boolean[][][] track,
int row, int col) {
vals.clear();
for (int i = 0; i < track[row][col].length; i++) {
if (!track[row][col][i]) {
vals.add(Integer.valueOf(i + 1));
}
}
}
}
代码说明：
布尔型[][[]磁道：
对已经尝试过的值使用某种检查表（以减少多次尝试相同随机值的开销）如果我已经尝试将val放在这个字段上，我就将track[行][列][值]设为true如果我回去，我必须清除该单元格的标记，使值再次成为可能。
检查值：
设置单元格上的值，检查数独是否仍然正确，再次设置旧值并返回true/false。
设定值：
只需设置单元格上的值。
增值税：
包含尚未尝试用于该单元格的值的数组列表。如果我继续前进，列表显然必须包含所有可能的数字。
如果我回溯，列表只需包含尚未尝试的数字。（我用轨迹数组来实现这一点）。
我做错什么了？
打招呼
最佳答案
好吧，首先出于某种原因，您从VAL列表中选择了一个随机数，其中大多数时间都是10+个数字，因此您在那里损失了相当多的时间。
我测试了你的代码，它实际上是相当随机的时间解决。
例如这个临时解决方案
[12, 9, 14, 7, 5, 13, 8, 2, 15, 3, 4, 6, 16, 1, 10, 11]
[1, 2, 13, 15, 12, 16, 14, 4, 11, 8, 10, 9, 5, 6, 0, 0]
....
填充单元格（2,15）和（2,16）所需的时间太长，因为它会从列表VAL中随机选择10个值（出于某种原因），但可能的值是数字3和7。
在VAL列表中，应将数字从当前行、当前列和区域中排除。
但是这并没有改善算法。
你的算法是：
1. For current cell try all values until you find one that fits.
2. If it fits track it and move on to next cell.
3. If no value fits take step back, try value on the previous cell that was not used yet.
由于随机性，如果某个值不在某个很好的位置，在第3点上花费的时间太多。