英语原文共 8 页

用遗传算法解决、评估和生成数独谜题

摘要—本文研究了利用遗传算法（GA）解决，评定和生成数独谜题所涉及的问题。 数独是一个数字拼图，最近成为一个世界范围的热潮。 数独可以被视为约束满足问题。 当用遗传算法求解时，它可以作为多目标优化问题来处理。 本研究的三个目标是：1）测试遗传算法优化是否是解决数独谜题的有效方法; 2）GA可否用于有效地生成新谜题; 3）GA可否用作评估机器对给定数独谜题的难度进行评估。 通过测试是否对于人类解答者而言难以理解的谜题对于遗传算法来说也是困难的，从而达成这些目标中的最后一点。本文提出的结果似乎支持这样的结论，即遗传算法优化可以很好地满足这些目标。

一，绪论

本文研究是否可以用遗传算法有效地解决，评定和生成数独谜题。遗传算法（GA）是一种模拟自然界中发生的达尔文进化[1]的优化方法。

根据维基百科[2]，数独是一种日本逻辑游戏，最近在欧洲和北美洲广受欢迎。然而，第一个谜题发表在1979年的美国拼图杂志上，随后席卷日本，1986年开始流行，后来它在2005年左右成为西方世界的热潮[3]。数独被声称非常受欢迎和令人上瘾，因为它非常具有挑战性，但有非常简单的规则[4]。

数独谜题由9times;9网格组成，共81个位置，分为9个3times;3子网格。数独谜题的解决方案是每个行，列和子网格包含每个整数{1,2，...，9}一次且仅有一次。

数独谜题是准备好的，所以开始时在网格中有一些静态数字，这些数字是预先给出的，不能更改或移动。给予的数字数量并不能决定难题的难度[4]，[5]。格子拼图是数独拼图创作中最困难的事情之一，大约有15到20个因素会对难度等级产生影响[2]。

给定的数字可以是对称的或非对称的。在对称情况下，存在相对于中心位置对称定位的对。

图1显示了由GA生成的数独谜题的一个示例。

它包含38个给定的数字，并且应解决其他43个位置的正确数字。这个谜题具有非对称的数量，因为数字不是相对于中心点对称的。这个数独的解决方案如图2所示。开头给出的静态数字（图1）与原来的位置完全相同。

在这项研究中，我们试图评估遗传算法如何有效地解决报纸和www.sudoku.com [6]中提出的数独难题。此外，我们评估GA效率是否与这些数独谜题的所谓难度等级相关。第三个目标是利用从前两个目标中获得的信息，用GA生成新的谜题，并评估新谜题的难度。

在第一部分中，我们介绍了问题，遗传算法和相关工作，第二部分介绍了提出的方法，第三部分介绍了获得的结果，第四部分讨论了研究结果及其含义。

图 1数独谜题的起点，其中38个位置包含给定的静态数字

A.遗传算法

所有遗传算法[7]都是基于计算机的优化方法，它们使用自然界的达尔文进化论[1]作为模型和灵感。问题的解决方案基础被编码为由几个基因组成的染色体的个体。与自然相反，GA的个体（表型）通常是从染色体（基因型）确定性地衍生的。在GA个体“生命时间”期间，年龄或环境不会改变表型。针对表示为适应度函数的问题测试这些虚拟个体。个人获得的健康价值越好，被选为新个体父母的机会就越大。为了给新一代腾出空间，最差的个体被杀死了。使用交叉和变异操作GA创建新的个体。在交叉中，我们采取一些提前选择的举措，从父母中选择新染色体的基因，例如，一点，两点或均匀交叉。在突变中，我们随机地或使用一些预定义的策略改变染色体的随机基因。 GA策略通常是精英主义，因此遵循达尔文进化论的“适者生存”原则。

图 2 图1中给出的数独谜题的解决方案。给定的数字用粗体标出。

B.相关工作

数独问题在约束规划和可满足性研究中被广泛研究[8]，[9]和[10]。这些方法对于解决数独也很有效，但不为每个数独谜题提供解决方案。然而，在这项研究中，我们专注于用进化方法解决数独。使用GA解决数独的主要原因是为了更多地了解GA在受约束的组合问题中的能力，并希望学习新技巧以使其在这个问题领域更有效。

似乎有一些关于使用EA方法的数独的科学论文。如Moraglio等。[5]使用GA和产品几何交叉解决了数独。他们声称他们的几何交叉比登山者和单独的突变表现得更好。他们的方法有效地解决了[6]中容易的数独，但是对于中等难度的数独有困难。他们还承认，进化算法不是解决数独的最有效技术，但是数独是一个有趣的算法开发研究案例。

Nicolau和Ryan [11]使用了一种不同的方法来解决数独：他们的GAuGE（使用语法演化的遗传算法）优化了逻辑运算的顺序，然后应用于查找解决方案。

Gold [12]使用GA来生成新的数独谜题，但该方法似乎效率低下，因为在他们的例子中，他们的GA需要35700代才能想出一个新的开放式数独解决方案。在我们的结果中，我们创建了一个新的开放数独解决方案，平均有101代（2020年试验）。

还有一个可用的Sudoku Maker [13]软件，据说内部使用遗传算法并声称生成的数独通常很难解决。遗憾的是，没有详细说明如何使用GA以及生成新数独的速度。

数独的规则意味着解决方案的每列和每行中的数字之和是相等的。因此，数独显然与古代魔方问题（拉丁方）有关，其中必须填充给定的正方形大小，使每列和每行的总和相等。之前已经用GA [14]，[15]解决了魔方问题，并且Evonet Flying circus [16]也演示了一个魔方解算器。

数独也可以被视为约束满足问题，其中所有行和列总和必须等于45.受约束的优化问题已经用进化算法有效地优化，例如在[17]，[18]，[19]。

另一个相关问题是生成半色调灰度图像的阈值矩阵[20]。在半色调中，通过将每个像素的值与阈值矩阵中的对应位置的值进行比较，将图像的灰度值转换为黑色或白色两个值。阈值矩阵中的值应均匀分布;阈值矩阵的每一行和每列中的阈值和应该几乎相等。 Bayer [21]最着名的阈值矩阵在一个维度（行或列）中具有相等的阈值和，而在另一维度（分别为列或行）中它们以常规方式不同。此外，阈值的均匀性要求也在本地保持，即任何固定大小的子区域应该具有几乎均匀分布的阈值和。这可以保证结果图像不包含黑色或白色像素的大簇。阈值矩阵先前已由GA优化，例如在[15]，[22]，[23]，[24]和[25]中。

二、 提出的方法

为了测试所提出的方法，我们决定使用整数编码的精英GA。GA染色体的大小为81个整数，分为9个9个子块。均匀交叉操作仅在子块之间应用，交换突变的序列仅在子块内部应用。

交换突变概率为0.6（尝试突变的数量，不等于在这种情况下进行的实际突变，参见随后的突变细节）。

图 3数独游戏在我们的GA中的表现。一种可能的解决方案（个体）是一个由81个数字组成的数组，它被分成九个9个数字的子块。交叉点只能出现在子块之间（标记为垂直线）。帮助数组用于检查固定位置，如果有一个不等于零的数字，在优化期间无法更改该数字，只有零的位置可以自由更改。

人口规模（POP）为21，精英比率（ELIT）为1.最佳个体通过以下算法选择交配个体x1和x2而受到青睐：

for（i = POP-1; igt; = ELIT; i - ）{

x1 =（int）（i * Math.random（））;

x2 =（int）（i * Math.random（））;

...

}

通过首先应用交叉然后突变到交叉结果来生成所有新个体。但是，有可能选择x1 = x2，其中只有突变操作改变新的个体基因型。找到的解决方案是唯一的停止条件，因为我们的方法永远都找不到解决方案。

除了数独的基本规则外，在解决过程中必须遵守固定数字（“给定”）。 因此，Sudoku解决方案遵循四个条件：

1）每行必须包含1到9的每个整数，

2）每列必须包含1到9的每个整数，

3）每个3x3子网格必须包含1到9的每个整数，

4）给定的数字必须保留在原始位置。

条件4）可以省略用于创建新数独谜题的新的开放式数独解决方案。当给定的数独谜题解决时，条件4）必须始终满足。通过适当的解决方法，可以控制条件1）至3）中的一个，因此仅三个条件经受优化。

我们选择对GA进行编程，以便自动满足条件3）和4），并且仅优化条件1）和2）。 数独有9行9列，因此我们有18个相等约束，当我们有解决方案时必须满足这些约束。

本研究中使用的GA是针对此问题或其他网格类型组合问题而定制的。这个GA是最初为魔方解算器[15]和其他组合问题编程的组合GA的修改。

该GA不使用可能为3x3子网格生成非法情况的直接突变或交叉。相反，行和列可以包含多个整数

一旦处于非最佳状态。遗传算子不允许移动问题开始时给出的固定数字。 这由help数组保证，该数组指示数字是否固定。

我们决定将数独难题解决方案表示为81个数字的整数数组。 该阵列被分成九个数字的九个子块（构建块），对应于从左到右和从上到下的3times;3子网格。 Crossovers仅在个体之间操作这些整个子块。因此，交叉点不能位于构建块内（图3）。

A.变异算子

突变仅应用于子块内。最初，我们使用了三种不同的突变策略，这些策略通常用于组合优化：交换突变，3交换突变和插入突变。然而，由于实际上3交换和插入突变实际上只是交换（双交换）突变的序列，我们后来用子块内的1到5个交换突变的序列替换它们。这样做是因为我们的测试运行表明只有交换突变的GA比交换，3交换和插入突变的GA表现更好。

在交换突变中，交换两个位置的值。每次在子块内尝试突变时，都会检查帮助数组。如果改变随机选择的位置是非法的，则省略突变。另外，如果我们随机抽取例如只有交换突变的两个位置都是合法的，我们才会进行5次突变。因此，尽管绘制1-，2-，3-，4-或5-交换序列的机会相等，但大多数时候序列被中断。有时，第一次交换尝试是非法的，并且没有执行突变，这意味着实际的突变百分比远低于前面提到的0.6。

使用不同数量的顺序交换进行的测试也显示仅具有一个交换突变的GA几乎与具有1至5个交换突变序列的GA一样好，因此大多数较长交换序列过早中止的事实是无害的。

图 4数独优化中使用的交换变异。左上方是一个子块，右上方是该子块的静态值（6和7是给定的）。应用变异，以便我们随机选择子块内的位置，然后将所选位置与帮助数组进行比较，以查看位置是否可以自由更改。

还有一个特殊规则控制突变是进行还是放弃。在此规则中，我们有另一个帮助表，告诉每个数字在每行和每列中出现的次数。尝试进行突变尝试时，它会影响一列或两列，一行或两行，总共3或4行和列向量。在最佳情况下，交换的两个数字应该总共出现在这些向量中两次。我们给系统一些松弛，并且不要求数字不能在同一行或列中出现多次。相反，如果在尝试突变后这些数字出现三次或更少，则完成突变。这意味着为了帮助GA在其他职位的帮助下交换头寸，可以原谅太多人。我们测量解算速度，如果没有松弛，它大约慢5倍。如果我们原谅两个而不是一个，那么解决速度会慢10倍。

这些规则需要一些时间来计算，但整体性能得到了提升。此规则还将实际突变百分比从0.6降低到更多。

我们添加的另一个特殊程序是重启或灾难性突变[26]。在组合问题中，优化经常被卡住，并且使用新的初始种群重新启动它比尝试从卡住的情况继续进行更有效。我们做了一个测试系列，我们在500,1000,2000,5000,10000,20000和50000代之后重新初始化人口，并得出结论，如果没有找到解决方案，最佳间隔是2000代。

B.适应度函数

设计一个有助于GA搜索的适应度函数在组合问题中通常很难[27]。 在这种情况下，我们最初[28]使用了一个有点复杂的适应度函数，不同地惩罚不同的约束违规。 在第一次测试中，我们要求每行和每列总和必须等于45，并且每行和列产品必须等于9！。 第三个要求来自集合论。 它要求每一行xi和列xj被认为是必须等于集合A的集合，集合A包含从1到9的整数; 如果没有，则对健身值添加惩罚。 该系统工作得很好，但通过从健身功能中删除部分，我们得出结论，更简单的适应函数也表现得更好。

每个3times;3子网格包含从1到9的整数的条件和固定数字本质上是保证的，并且惩罚函数用于试图强制其他条件。 本文中使用的适应度函数仅剩下设定理论部分。

考虑包含1到9的每个整数的集合A：

函数（1）计算每行（xi）集和列（xj）集中的缺失数字的位数，其中| sdot;| 表示集合的基数。

在最佳情况下，所有数字都出现在行和列集中，并且适应度函数值变为零。 否则为数字惩罚值| n-1 | 被添加到健身功能。 这意味着如果缺少某个数字，则添加惩罚值1，并且如果某个数字出现n次，其中ngt; 1，则添加惩罚值n-1。 因此，某些行或列集中的每个错误至少等于惩罚值2.适应度函数将被最小化。

我们还添加了一个特殊的惩罚项（2），如果相同的解决方案保持最佳位置，则将惩罚值1添加到每一代的最佳解。 这意味着当新解决方案变得最佳时，其值是从适应度函数获得的值。 如果它仍然是下一代的最佳解决方案，我们将其值1添加到其适应值。 这种手术可以看作是个体表型的某种衰老过程。 如果它活得更久，它就不那么健康和强壮。 添加此操作是为了对群体进行更多变化，我们的初步测试也表明它是有益的，并且它导致更快地解决数独。

三、实验结果

我们首先测试从报纸Helsingin Sanomat [29]拍摄的五个数独谜题，标记为难度等级为1-5星。这些具有2

资料编号：[4180]