数独求解器评估函数

Question

所以我试图写一个简单的遗传算法来解决一个数独（不是最有效的方法，我知道，但它只是为了练习演化算法）。我遇到了一些问题，提出了一个有效的评估函数来测试难题是否得到解决，以及有多少错误。我的第一本能是检查矩阵中的每一行和列（以八度为单位，与matlab类似）是否具有唯一的元素，通过排序来检查重复项，然后将它们重新放回原来的样子，这似乎很长纠缠不清。有什么想法吗？

抱歉，如果这已经问...

Answer 1

我会使用网格的号码作为索引，并递增的9个元素长度数组的各个元素=> s_array [X] ++其中x是数取自电网。 在检查一行结束时，数组中的每个元素都必须是1。如果0发生在数组中的某个位置，则该行是错误的。

但是，这只是一个简单的完整性检查，如果没有问题，线路明智。 PS：如果是10年前，我会建议使用位操作的组合解决方案（值1,2或3的第1位，第2位，第3位等），并检查结果是否为2^10-1。

Answer 2

听起来不错，除了'把他们放回'部分。您可以将任意行，列或方块中的数字放入列表中，然后以任何您想要的方式检查双打。如果有双打，则会出现错误。如果所有的数字都是唯一的，那就没有。你不需要把实际的数字从难题中解放出来，所以不需要再把它们放回去。

此外，如果你正在编写一个解算器，它不应该做任何无效的移动，所以根本不需要这个检查。

Answer 3

加速：
使用按位操作代替排序。

我在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; 
} 

Answer 4

的检查很容易，你会为行，列创建套，和3x3的加入了许多，如果它不存在，并相应地改变你的健身，如果它才不是。

然而，真正的伎俩是“相应地改变你的健康”。有些问题看起来非常适合GA和ES（进化策略），也就是说我们寻找宽容的解决方案，数独有一个确切的答案......非常棘手。

我的第一个破解可能是创建可变长度染色体的解决方案（以及它们可以是固定长度，但9x9的空白）。健身功能应该能够确定解决方案的哪一部分是有保证的，哪一部分不是（有时候你必须在一个非常艰难的数独游戏中在黑暗中进行猜测，如果不成功则返回），它会为每个可能的分支创建孩子是一个好主意。

然后这是一个递归解决方案。不过，您可以从电路板上的不同位置开始扫描。重组将结合具有重叠解决方案的未验证部分的解决方案。

只要在这个高水平的随和时尚中思考一下，我就能看到这个想法是如何实现的！

只有当有多条路径需要采用时，才会应用突变，毕竟突变是一种猜测。

Answer 5

当我解决了这个问题时，我只计算了每行，每列和子网格中的重复次数（事实上，我只需要计算列和子网格中的重复次数，因为我的进化算子从未设计过重复成行）。我只是使用HashSet来检测重复项。有更快的方法，但这对我来说足够快。

您可以在my Java applet中看到这种可视化（如果速度太快，请增加人口数量以减慢速度）。彩色正方形是重复的。黄色正方形与另一个正方形发生冲突，橙色与另外两个正方形发生冲突，红色发生三次或更多正方形。

Answer 6

这是我的解决方案。 Sudoku solving solution in C++

Answer 7

这是我的solution使用集合。如果一条线，块或一列你得到的一组长度（让说）7，你的健康将是9 - 7

Answer 8

1. 如果你是在一个小整数集的排序可以操作使用桶分类在O(n)中完成。

2. 可以使用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