数独求解器评估函数
所以我试图写一个简单的遗传算法来解决一个数独(不是最有效的方法,我知道,但它只是为了练习演化算法)。我遇到了一些问题,提出了一个有效的评估函数来测试难题是否得到解决,以及有多少错误。我的第一本能是检查矩阵中的每一行和列(以八度为单位,与matlab类似)是否具有唯一的元素,通过排序来检查重复项,然后将它们重新放回原来的样子,这似乎很长纠缠不清。有什么想法吗?数独求解器评估函数
抱歉,如果这已经问...
我会使用网格的号码作为索引,并递增的9个元素长度数组的各个元素=> s_array [X] ++其中x
是数取自电网。 在检查一行结束时,数组中的每个元素都必须是1。如果0发生在数组中的某个位置,则该行是错误的。
但是,这只是一个简单的完整性检查,如果没有问题,线路明智。 PS:如果是10年前,我会建议使用位操作的组合解决方案(值1,2或3的第1位,第2位,第3位等),并检查结果是否为2^10-1。
听起来不错,除了'把他们放回'部分。您可以将任意行,列或方块中的数字放入列表中,然后以任何您想要的方式检查双打。如果有双打,则会出现错误。如果所有的数字都是唯一的,那就没有。你不需要把实际的数字从难题中解放出来,所以不需要再把它们放回去。
此外,如果你正在编写一个解算器,它不应该做任何无效的移动,所以根本不需要这个检查。
加速:
使用按位操作代替排序。
我在c中制作了100行数独解算器,速度相当快。对于或超级速度,你需要实现DLX算法,在matlab交换中也有一些文件。
http://en.wikipedia.org/wiki/Exact_cover
http://en.wikipedia.org/wiki/Dancing_Links
http://en.wikipedia.org/wiki/Knuth“s_Algorithm_X
#include "stdio.h"
int rec_sudoku(int (&mat)[9][9],int depth)
{
int sol[9][9][10]; //for eliminating
if(depth == 0) return 1;
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
sol[i][j][9]=9;
for(int k=0;k<9;k++)
{
if(mat[i][j]) sol[i][j][k]=0;
else sol[i][j][k]=1;
}
}
}
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
if(mat[i][j] == 0) continue;
for(int k=0;k<9;k++)
{
if(sol[i][k][mat[i][j]-1])
{
if(--sol[i][k][9]==0) return 0;
sol[i][k][mat[i][j]-1]=0;
}
if(sol[k][j][mat[i][j]-1])
{
if(--sol[k][j][9]==0) return 0;
sol[k][j][mat[i][j]-1]=0;
}
}
for(int k=(i/3)*3;k<(i/3+1)*3;k++)
{
for(int kk=(j/3)*3;kk<(j/3+1)*3;kk++)
{
if(sol[k][kk][mat[i][j]-1])
{
if(--sol[k][kk][9]==0) return 0;
sol[k][kk][mat[i][j]-1]=0;
}
}
}
}
}
for(int c=1;c<=9;c++)
{
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
if(sol[i][j][9] != c) continue;
for(int k=0;k<9;k++)
{
if(sol[i][j][k] != 1) continue;
mat[i][j]=k+1;
if(rec_sudoku(mat,depth-1)) return 1;
mat[i][j]=0;
}
return 0;
}
}
}
return 0;
}
int main(void)
{
int matrix[9][9] =
{
{1,0,0,0,0,7,0,9,0},
{0,3,0,0,2,0,0,0,8},
{0,0,9,6,0,0,5,0,0},
{0,0,5,3,0,0,9,0,0},
{0,1,0,0,8,0,0,0,2},
{6,0,0,0,0,4,0,0,0},
{3,0,0,0,0,0,0,1,0},
{0,4,0,0,0,0,0,0,7},
{0,0,7,0,0,0,3,0,0}
};
int d=0;
for(int i=0;i<9;i++) for(int j=0;j<9;j++) if(matrix[i][j] == 0) d++;
if(rec_sudoku(matrix,d)==0)
{
printf("no solution");
return 0;
}
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
printf("%i ",matrix[i][j]);
}
printf("\n");
}
return 1;
}
的检查很容易,你会为行,列创建套,和3x3的加入了许多,如果它不存在,并相应地改变你的健身,如果它才不是。
然而,真正的伎俩是“相应地改变你的健康”。有些问题看起来非常适合GA和ES(进化策略),也就是说我们寻找宽容的解决方案,数独有一个确切的答案......非常棘手。
我的第一个破解可能是创建可变长度染色体的解决方案(以及它们可以是固定长度,但9x9的空白)。健身功能应该能够确定解决方案的哪一部分是有保证的,哪一部分不是(有时候你必须在一个非常艰难的数独游戏中在黑暗中进行猜测,如果不成功则返回),它会为每个可能的分支创建孩子是一个好主意。
然后这是一个递归解决方案。不过,您可以从电路板上的不同位置开始扫描。重组将结合具有重叠解决方案的未验证部分的解决方案。
只要在这个高水平的随和时尚中思考一下,我就能看到这个想法是如何实现的!
只有当有多条路径需要采用时,才会应用突变,毕竟突变是一种猜测。
当我解决了这个问题时,我只计算了每行,每列和子网格中的重复次数(事实上,我只需要计算列和子网格中的重复次数,因为我的进化算子从未设计过重复成行)。我只是使用HashSet来检测重复项。有更快的方法,但这对我来说足够快。
您可以在my Java applet中看到这种可视化(如果速度太快,请增加人口数量以减慢速度)。彩色正方形是重复的。黄色正方形与另一个正方形发生冲突,橙色与另外两个正方形发生冲突,红色发生三次或更多正方形。
如果你是在一个小整数集的排序可以操作使用桶分类在
O(n)
中完成。-
可以使用
tmp
阵列做这个任务在MATLAB:函数TF = checkSubSet(板,SEL) % %给出一个9x9的板和选择(使用逻辑9x9的SEL矩阵) %验证板(sel)有9个独特元素 % %假设作出: % - 董事会是9x9与数字1,2,...,9 % - sel只有9个“真实”条目:nnz(sel) = 9 % tmp =零(1,9); tmp(board(sel))= 1; %穷人的桶分类 tf = all(tmp == 1)& & nnz(sel)== 9 & & numel(tmp)== 9; %检查有效性
现在我们可以使用checkSubSet
验证板是正确的
function isCorrect = checkSudokuBoard(board)
%
% assuming board is 9x9 matrix with entries 1,2,...,9
%
isCorrect = true;
% check rows and columns
for ii = 1:9
sel = false(9);
sel(:,ii) = true;
isCorrect = checkSubSet(board, sel);
if ~isCorrect
return;
end
sel = false(9);
sel(ii, :) = true;
isCorrect = checkSubSet(board, sel);
if ~isCorrect
return;
end
end
% check all 3x3
for ii=1:3:9
for jj=1:3:9
sel = false(9);
sel(ii + (0:2) , jj + (0:2)) = true;
isCorrect = checkSubSet(board, sel);
if ~isCorrect
return;
end
end
end