所以我正在尝试编写一个简单的遗传算法来解决数独问题（我知道这不是最有效的方法，但这只是为了练习进化算法）。我在想出一个有效的评估函数来测试这个谜题是否得到解决以及有多少错误时遇到了一些问题。我的第一直觉是检查矩阵的每一行和每一列（以八度音程进行，类似于 matlab）通过对它们进行排序、检查重复项然后将它们放回原样来检查它们是否具有唯一元素，这似乎很长缠绕。有什么想法吗？
抱歉，如果之前有人问过这个问题...
问问题
2049 次
8 回答
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;
}
于 2010-12-23T00:59:30.460 回答
1
检查很简单，您将为行、列和 3x3 创建集合，如果不存在则添加一个数字，如果不存在则相应地更改您的适应度。
然而，真正的诀窍是相应地“改变你的健康”。有些问题似乎很适合 GA 和 ES（进化策略），即我们在容忍度上寻找解决方案，数独有一个准确的答案......棘手。
我的第一个破解可能是创建具有可变长度染色体的解决方案（它们可以是固定长度，但 9x9 带有空白）。适应度函数应该能够确定解决方案的哪一部分得到保证，哪一部分没有保证（有时你必须在一个非常困难的数独游戏中在黑暗中猜测，然后如果它不成功则回溯），它会为每个可能的分支创建子代是个好主意。
这是一个递归解决方案。但是，您可以从板上的不同位置开始扫描。重组将结合具有重叠解决方案的未验证部分的解决方案。
只要以这种高级随和的方式思考它，我就可以看出这将是多么令人费解！
只有当有多个路径可供选择时才会应用突变，毕竟突变是一种猜测。
于 2010-12-23T01:01:38.977 回答
0
当我解决这个问题时，我只计算了每行、列和子网格中的重复数（实际上我只需要计算列和子网格中的重复数，因为我的进化算子被设计为从不将重复引入行） . 我只是使用 HashSet 来检测重复项。有更快的方法，但这对我来说已经足够快了。
您可以在我的 Java 小程序中看到这一点（如果速度太快，请增加人口规模以减慢速度）。彩色方块是重复的。黄色方格与另一个方格冲突，橙色方格与其他两个方格冲突，红色方格与三个或更多方格冲突。
于 2010-12-27T23:34:02.297 回答
0
如果您对一小组整数进行操作，则可以
O(n)使用桶排序来完成排序。您可以
tmp在 matlab 中使用数组来执行此任务：函数 tf = checkSubSet(board, sel) % % 给定一个 9x9 板和一个选择（使用逻辑 9x9 sel 矩阵） % 验证 board(sel) 有 9 个唯一元素 % 假设：% - 板是 9x9，数字为 1， 2,...,9 % - sel 只有 9 个“真”条目：nnz(sel) = 9 % tmp = zeros(1,9); tmp(板(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
于 2013-01-04T12:02:43.840 回答
0
这是我使用 set的解决方案。如果对于一条线、一个块或一列，您的设定长度为（比如说）7，那么您的适应度将是 9 - 7。
于 2013-01-04T07:01:16.913 回答
0
我将使用网格的数字作为索引，并增加一个 9 元素长度数组的相应元素 => s_array[x]++ 其中x是从网格中获取的数字。在检查一行结束时，数组中的每个元素都必须为 1。如果 0 出现在数组中的某处，则该行是错误的。
然而，如果没有问题，这只是一个简单的完整性检查，按行。
PS：如果是 10 年前，我建议使用位操作（值 1,2 或 3 的第 1 位、第 2 位、第 3 位等）的装配解决方案并检查结果是否为 2^10-1 .
于 2010-12-23T00:52:28.707 回答
0
听起来不错，除了“把它们放回去”部分。您可以将拼图中任何行、列或方格中的数字放入列表中，并以您想要的任何方式检查双打。如果有双打，就有错误。如果所有数字都是唯一的，则不是。您无需将实际数字从拼图中取出，因此也无需将它们放回原处。
此外，如果您正在编写求解器，它不应做出任何无效的移动，因此根本不需要此检查。
于 2010-12-23T00:52:35.597 回答
0
这是我的解决方案。用 C++ 解决数独问题
于 2011-07-18T11:25:30.323 回答