数独求解器评估函数

Question

所以我试图编写一个简单的遗传算法来解决数独（我知道这不是最有效的方法，但这只是练习进化算法）。我在想出一个有效的评估函数来测试谜题是否已解决以及有多少错误时遇到了一些问题。我的第一直觉是检查矩阵的每一行和每一列（以八度进行，类似于 matlab）是否具有独特的元素，方法是对它们进行排序，检查重复项，然后将它们放回原样，这看起来很长气喘吁吁。有什么想法吗？

抱歉，如果之前有人问过这个问题...

Answer 1

1. 如果您正在操作一小组整数，则可以使用桶排序在O(n)内完成排序。

2. 您可以使用 tmp 数组在 matlab 中完成此任务：

   函数 tf = checkSubSet( board, sel )
   %
   % 给定一个 9x9 板和一个选择（使用逻辑 9x9 sel 矩阵）
   % 验证 board(sel) 有 9 个独特的元素
   %
   做出的假设百分比：
   % - 棋盘为 9x9，数字为 1,2,...,9
   % - sel 只有 9 个“真实”条目：nnz(sel) = 9
   %
   tmp = 零(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

Answer 2

加速：
使用按位运算而不是排序。

我用 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 3

检查很简单，您将为行、列和 3x3 创建集合，如果数字不存在，则添加一个数字，如果不存在，则相应地改变您的适应度。

然而，真正的技巧是相应地“改变你的健康状况”。有些问题似乎很适合GA和ES（进化策略），那就是我们在容忍度中寻找解决方案，数独有一个确切的答案......棘手。

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

这就是一个递归解决方案。但是，您可以从板上的不同位置开始扫描。重组将组合解决方案，这些解决方案组合具有重叠解决方案的未经验证的部分。

只要以这种高水平的轻松时尚的方式思考它，我就能明白这将是多么令人费解的实施！

只有当有多条路径可供选择时，才会应用突变，毕竟突变是一种猜测。

Answer 4

听起来不错，除了“把它们放回去”的部分。您可以将拼图中任意行、列或方格中的数字放入列表中，然后按照您想要的方式检查双数。如果有双打，就会出现错误。如果所有数字都是唯一的，则没有。您不需要将实际数字从拼图中取出，因此也无需将它们放回去。

此外，如果您正在编写一个求解器，它不应该做出任何无效的移动，因此根本不需要此检查。

Answer 5

我将使用网格的数字作为索引，并增加 9 个元素长度数组的相应元素 => s_array[x]++，其中 x 是从网格中获取的数字。
在检查一行结束时，数组中的每个元素都必须为 1。如果 0 出现在数组中的某个位置，则该行是错误的。

然而，如果没有问题的话，这只是一个简单的健全性检查。

PS：如果是 10 年前，我会建议使用位操作的汇编解决方案（第 1 位、第 2 位、第 3 位等，对于值 1,2 或 3）并检查结果是否为 2^10-1 。

Answer 6

当我解决这个问题时，我只计算了每行、列和子网格中的重复项数量（事实上，我只需要计算列和子网格中的重复项，因为我的进化运算符被设计为永远不会在行中引入重复项） 。我只是使用 HashSet 来检测重复项。有更快的方法，但这对我来说已经足够快了。

您可以在 我的 Java 小程序 中看到这一点（如果速度太快，请增加总体规模以减慢速度）。彩色方块是重复的。黄色方块与其他方块冲突，橙色方块与另外两个方块冲突，红色方块与三个或更多方块冲突。

Answer 7

这是我的解决方案。 C++ 数独解决方案

Answer 8

这是我使用 set 的 解决方案 。如果对于一条线、一个块或一列，您的设定长度为（假设）7，那么您的适应度将为 9 - 7。