精确覆盖算法如下，这个测试是正常的，但是改成解数独，大部分题目能正常解出来，少部分解不出来，求算法大神出手！
import console;
//精确覆盖问题是指，给定一个集合{1,2,3,4,5,6,7}，以及若干个子集
//"A" = {"2", "6"};"B" = {"4", "5", "6"};"C" = {"2", "3", "7"};"D" = {"1", "4", "7"};"E" = {"1", "4"};"F" = {"3", "5", "7"};
//找出若干个子集刚好覆盖住给定的集合{1,2,3,4,5,6,7}，比如"A" = {"2", "6"}、"E" = {"1", "4"}、"F" = {"3", "5", "7"}就是一组解
//https://oi-wiki.org/search/dlx/
//https://blog.csdn.net/whereisherofrom/article/details/79220897
//DLX算法是使用双向十字链表，数据结构太过麻烦，我们使用哈希表代替即可，根据给定的集合Y，构造集合X，通过哈希表直接代替双向十字链表的删除和恢复，
//数据结构上更加简单
//第一组测试数据
X = {
"1" = {"D", "E"};
"2" = {"A", "C"};
"3" = {"C", "F"};
"4" = {"B", "D", "E"};
"5" = {"B", "F"};
"6" = {"A", "B"};
"7" = {"C", "D", "F"};
}
Y = {
"A" = {"2", "6"};
"B" = {"4", "5", "6"};
"C" = {"2", "3", "7"};
"D" = {"1", "4", "7"};
"E" = {"1", "4"};
"F" = {"3", "5", "7"};
}
//第二组测试数据
X = {
"1" = {"A", "B"};
"2" = {"E", "F", "G"};
"3" = {"D", "E"};
"4" = {"A", "B", "C"};
"5" = {"C", "D"};
"6" = {"D", "E"};
"7" = {"A", "C", "E", "F", "G"};
}
Y = {
"A" = {"1", "4", "7"};
"B" = {"1", "4"};
"C" = {"4", "5", "7"};
"D" = {"3", "5", "6"};
"E" = {"2", "3", "6", "7"};
"F" = {"2", "7"};
"G" = {"2", "7"};
}
//辅助函数，返回哈希表键值对的数量
hashCount = function(tab){
var count = 0
for(k,v in tab){
count++
}
return count;
}
//辅助函数，返回一个哈希表中，长度最小的键值对的索引
findShortest = function(tab){
var count = 9
var result = ""
for(k,v in tab){
if(#v != 0 and #v <= count){
result = k
count = #v
}
}
return result;
}
var count = 0;
var loop = 0;
//递归求解
// 定义一个名为solve的函数
// 该函数接受三个参数：X，Y和solution
function solve(X, Y, solution){
count++;
console.dump("第"++count++"次递归");
console.dump("hashCount(X):"++hashCount(X));
if(hashCount(X) == 0){ // 如果X的哈希计数为0
return table.slice(solution); // 返回solution的切片
}
else { // 否则
var c = findShortest(X) // 寻找X中最短的元素并赋值给c
var result = {}; // 声明一个空对象result
for(k,v in X[c]){ // 遍历X[c]中的键值对
loop++;
console.dump("第"++loop++"次循环");
table.push(solution, v) // 将v添加到solution中
console.dump("v:", v, "X中最小的列:", c, "solution:", solution, "删除前的X:", X);
var cols = xselect(X, Y, v); // 调用xselect函数，并将返回值赋值给cols
console.dump("删除后的X:", X);
table.push(result, solve(X, Y, solution)) // 将solve(X, Y, solution)的返回值添加到result中
console.dump("result:", result);
deselect(X, Y, v, cols) // 调用deselect函数，传入X、Y、v和cols作为参数
console.dump("恢复的X:", X);
table.pop(solution) // 从solution中弹出最后一个元素
console.dump("solution:", solution);
}
return result; // 返回result
}
}
//删除
// 定义一个名为xselect的函数，接受三个参数X、Y、r
xselect = function(X, Y, r){
var cols = {}; // 创建一个空的cols对象
for(k,v in Y[r]){ // 遍历Y[r]中的键值对
for(k2,v2 in X[v]){ // 遍历X[v]中的键值对
for(k3,v3 in Y[v2]){ // 遍历Y[v2]中的键值对
if(v3 != v){ // 如果v3不等于v，则从X[v3]中移除v2
table.removeByValue(X[v3], v2)
}
}
}
table.push(cols, X[v]); // 将X[v]添加到cols中
X[v] = null // 将X[v]设置为null
}
return cols; // 返回cols
}
//恢复
// 定义一个名为deselect的函数，接受四个参数X、Y、r、cols
deselect = function(X, Y, r, cols){
table.reverse(Y[r]) // 反转Y[r]
for(k,v in Y[r]){ // 遍历Y[r]中的键值对
X[v] = table.pop(cols) // 从cols中弹出一个元素，并将其赋值给X[v]
for(k2,v2 in X[v]){ // 遍历X[v]中的键值对
for(k3,v3 in Y[v2]){ // 遍历Y[v2]中的键值对
if(v3 != v){ // 如果v3不等于v，则将v2添加到X[v3]中
table.push(X[v3], v2)
}
}
}
}
}
var result = solve(X, Y, {})
console.dump("result:", result);
console.pause(true);
精确覆盖解数独的算法：
import console;
//核心函数只有4个
//第一个solveSudoku(grid)负责将grid转为约束条件X、Y，并调用solve()函数求解
//第二个solve()递归解决精确覆盖问题
//第三个xselect()删除相关的行列
//第四个deselect()恢复相关的行列
// 定义一个名为solveSudoku的函数，接受一个参数grid
solveSudoku = function(grid){
var answer = table.clone(grid) // 克隆输入的grid并赋值给answer
var X = {}; // 创建空的X对象
var Y = {}; // 创建空的Y对象
// 构建X和Y对象
for(i=1;9;1){
for(j=1;9;1){
for(n=1;9;1){
var b = ..math.floor((i-1)/3)*3 + ..math.floor((j-1)/3) + 1 // 计算当前单元格所在宫的索引b
// 生成行-列-数字对应的键
var rc = ..string.format("%s%s%s", "rc", i, j);
var rn = ..string.format("%s%s%s", "rn", i, n);
var cn = ..string.format("%s%s%s", "cn", j, n);
var bn = ..string.format("%s%s%s", "bn", b, n);
var key = ..string.format("%s%s%s", i, j, n);
// 初始化X对象中对应的属性
X[rc] = X[rc] || {};
X[rn] = X[rn] || {};
X[cn] = X[cn] || {};
X[bn] = X[bn] || {};
// 将key添加到X对应属性的值中
..table.push(X[rc], key);
..table.push(X[rn], key);
..table.push(X[cn], key);
..table.push(X[bn], key);
// 将key对应的行、列、宫信息添加到Y对象中
Y[key] = {rc, rn, cn, bn};
}
}
}
//console.dump(X);
// 遍历输入的grid
for(i=1;9;1){
for(j=1;9;1){
var n = grid[i][j] // 获取当前位置的数字n
var key = ..string.format("%s%s%s", i, j, n); // 生成对应的键key
// 如果n不为零，则执行xselect操作
if(n){
xselect(X, Y, key)
}
}
}
console.dump(Y);
var solutions = solve(X, Y, {}) // 调用solve函数求解数独
// 如果存在解决方案
/*
if(solutions){
// 将解决方案应用到answer中
for(k,v in solutions){
var temp = string.split(v)
var i = tonumber(temp[1])
var j = tonumber(temp[2])
var n = tonumber(temp[3])
answer[i][j] = n
}
}
*/
var str = GridToString(answer)
return solutions, answer, str; // 返回解决方案和answer
}
var count = 0;
var loop = 0;
// 定义一个名为solve的函数，接受四个参数X、Y、solution、result
solve = function(X, Y, solution){
count++;
console.dump("第"++count++"次递归");
console.dump("hashCount(X):"++hashCount(X));
// 如果X中的元素数量为0，即已经没有需要处理的元素，返回solution的副本
if(hashCount(X) == 0){
return table.slice(solution);
}
else {
var c = findShortest(X) // 找到X中剩余元素最少的列c
var result = {}
// 遍历X[c]中的元素
for(k,v in X[c]){
loop++;
console.dump("第"++loop++"次循环");
table.push(solution, v) // 将当前元素v添加到solution中
//console.dump("v:", v, "X中最小的列:", c, "solution:", solution);
var cols = xselect(X, Y, v); // 选择并删除相关列，并继续递归求解
//console.dump("删除后的X:", X);
table.push(result, solve(X, Y, solution)) // 将递归结果添加到tempResult中
console.dump("result:", result);
deselect(X, Y, v, cols) // 恢复相关列的选择，并将solution中的最后一个元素弹出
//console.dump("恢复X:", X);
table.pop(solution)
//console.dump("solution:", solution);
}
return result;
}
}
//删除相关的行和列
xselect = function(X, Y, r){
var cols = {};
for(k,v in Y[r]){
for(k2,v2 in X[v]){
for(k3,v3 in Y[v2]){
if(v3 != v){
table.removeByValue(X[v3], v2)
}
}
}
table.push(cols, X[v]);
X[v] = null
//console.dump(X);
}
return cols;
}
//恢复行和列
deselect = function(X, Y, r, cols){
..table.reverse(Y[r])
for(k,v in Y[r]){
X[v] = table.pop(cols)
for(k2,v2 in X[v]){
for(k3,v3 in Y[v2]){
if(v3 != v){
table.push(X[v3], v2)
}
}
}
}
}
//辅助函数，返回哈希表键值对的数量
hashCount = function(tab){
var count = 0
for(k,v in tab){
count++
}
return count;
}
//辅助函数，返回一个哈希表中，长度最小的键值对的索引
findShortest = function(tab){
var count = 9
var result = ""
for(k,v in tab){
if(#v != 0 and #v <= count){
result = k
count = #v
}
}
//console.dump(result);
return result;
}
//辅助函数，将字符串转为二维数组
stringToGrid = function(str){
var grid = {{}, {}, {}, {}, {}, {}, {}, {}, {}}; // 创建一个9x9的空二维数组grid
var temp = ..string.split(str) // 通过string.split将输入的str字符串转换为数组temp
// 循环遍历1到9的行
for(i=1;9;1){
// 循环遍历1到9的列
for(j=1;9;1){
var pos = (i-1)*9 + j // 计算当前位置在一维数组temp中的索引
// 如果temp[pos]为"."，则在grid中将对应位置值设为0，否则转换为数字后存入grid
if(temp[pos] == "."){
grid[i][j] = 0
}
else {
grid[i][j] = tonumber(temp[pos])
}
}
}
return grid; // 返回转换后的grid
}
GridToString = function(grid){
var str = "";
for(i=1;9;1){
for(j=1;9;1){
if(grid[i][j] == 0){
str = str ++ '.'
}
else {
str = str ++ tostring(grid[i][j])
}
}
}
return str;
}
var question = {
".................1.....2.3......3.2...1.4......5....6..3......4.7..8...962...7..3";
".................1.....2.3......3.2...4....5...6.1.....3......6.7..8...952.7.....";
".................1.....2.3......425...6.......17....8.....7...64...6....9..8...1.";
".................1.....2.3......45....1.6.....4......7....8.4....9...2..3.61...9.";
".................1.....2.3......45.6..3.......17...8.....16......8....4..6.5..2..";
".................1.....2.3.....1...4..3.5.....26....7.14...8...5........7....6.2.";
".................1.....2.3.....4...5..2.1...6..3..78.....9.32...1.....4..5.......";
".................1.....2.3.....4...5..3.1.....26....7.15...8...4........7....6.2.";
".................1.....2.3.....4.2.5..6..7.....8.9...4...8.3.6..4.....9..5.......";
".................1.....2.3...1..4.....5.....6..6..378..4.....2..7..5.....9..1....";
".................1.....2.3...1..4.....5.....6..6..782..4.....7..8..5.....9..1....";
".................1.....2.3...2...4....3.5......41....6.5.6......7.....2..8.91....";
".................1.....2.3...2...4....3.5......46....7.5.1......8.....2..9.76....";
".................1.....2.34.....3.....5...16...7..4....4..1.....8..9....23.....8.";
".................1.....2.34.....4.....5...6....6.3.....3..5.....7..6.8..24......7";
".................1.....2.34.....4.....5...6....6.3.....3..6.....7..5.8..24......7";
".................1.....2.34.....4.2...1........5.6.7...2........8..7.9..34..9....";
".................1.....2.34.....42....1..3.....5.....6....1..7..2..6....38....5..";
".................1.....2.34.....42....1..3.....5.....6....1..7..2..6....48....5..";
".................1.....2.34.....5.....1...6....7..38......6.7...4..1....35.4.....";
}
//速度测试
speedTest = function(tab){
var tick = time.tick()
for(k,v in tab){
var grid = stringToGrid(v)
solution, answer = solveSudoku(grid)
console.dump(answer);
}
console.dump("用时"++(time.tick()-tick)++"ms");
}
//speedTest(question)
var sudokuStr = ".................1.....2.3......3.2...1.4......5....6..3......4.7..8...962...7..." //解不出来
var sudokuStr = ".................1.....2.3......3.2...4....5...6.1.....3......6.7..8...952.7....." //解得出来
var sudokuStr = "8.3761.42562834791417592836746953128381246957295178463138629574.7438521962941738."
var sudokuStr = "..3.6...2.62.3...1..7..2.367.6..3.2.2.164....3.5....6..3....674.743862.962.4.7..."
var sudokuStr = ".................1.....2.3......3.2...1.4......5....6..3......4.7..8...962...7..." //解不出来
var grid = stringToGrid(sudokuStr)
var solution, answer, str = solveSudoku(grid)
console.dump(solution, answer, str);
console.pause(true);
太高级了，绕晕了