英语原文共 5 页，剩余内容已隐藏，支付完成后下载完整资料

窗体顶端

窗体顶端

一种混合AC3-tabu搜索算法解决数独谜题

Ricardo Soto ^a,b,*, Broderick Crawford ^a,c, Cristian Galleguillos ^a, Eric Monfroy ^d, Fernando Paredes ^e

^a Pontificia Universidad Catoacute;lica de Valparaiacute;so, Av. Brasil 2950, Valparaiacute;so, Chile

^b Universidad Autoacute;noma de Chile, Av. Pedro de Valdivia 641, Santiago, Chile

^c Universidad Finis Terrae, Av. Pedro de Valdivia 1509, Santiago, Chile

^d CNRS, LINA, University of Nantes, 2 rue de la Houssiniegrave;re, Nantes, France

^e Escuela de Ingenieriacute;a Industrial, Universidad Diego Portales, Manuel Rodriacute;guez Sur 415, Santiago, Chile

摘要

数独问题在于填充n²times;n²网格，使每列、每行和每一个ntimes;n子网格包含从1到n²的不同数字。这是一个很复杂的问题，已知具备NP完备性。文献报道了用于解决这个问题的不同的不完全搜索方法，遗传计算是表现出最好结果的方法。 在本文中，我们提出一个新的混合AC3-tabu搜索算法为数独问题。我们将经典禁忌搜索过程与弧一致性3（AC3）算法合并，以有效地减少组合空间。这里的AC3的作用不仅仅是作为单个预处理阶段，而且作为在每次禁忌搜索的迭代时应用的完全集成的过程。这种集成导致更有效的域滤波并因此导致更快的分辨率处理。我们呈现了实验评估，其中我们的方法胜过使用不完全搜索方法的最好结果。

关键词:启发式 禁忌搜索 约束满足 数独

1.简介

数独难题包括一个通常大小为9times;9的棋盘，细分为大小为3times;3的子网格包括预填充空白格，其中数字不能被改变或移动（参见图1）。解决这个问题是当棋盘被填充，使得每行，每列和每个子网格包含从1到9的不同数字。一般n²times;n²的数独问题棋盘尺寸包括n²times;n²个子网格是已知的具有NP完备性（Yato，Seta，＆Ito，2003）。然后使用特定的方法可以在指数时间内解决问题。数独通常按照难度分类。问题的相关性和定位可能会改变其难度，但是预填充的空白格数量具有很少或没有影响范围。Mantere and Koljonen（2007）将数独分类为树类：简单，中等和困难。

在过去几年中提出了各种方法来解决数独难题。大多数作品范围从完全搜索

方法如约束规划（Moon＆Gunther，2006;Rossi，van Beek，＆Walsh，2006; Simonis，2005）和布尔可满足性（Lynce＆Ouaknine，2006）到不完全搜索方法，如遗传规划（Asif，2009; Mantere＆Koljonen，2007）和一般的元启发式（Moraglio，Togelius，＆Lucas，2006; Lewis，2007; Moraglio＆Togelius，2007; Mantere＆Koljonen，2008a）等。在这种情况下，其他更少运用传统技术的方法，如重写规则（Santos-Garciacute;a＆Palomino，2007），Sinkhorn平衡（Moon，Gunther，＆Kupin，2009）和熵最小化（Gunther＆Moon，2012）也被提出来解决这个问题。

在本文中，我们专注于不完全的搜索方法。我们提出了一个新的混合算法数独拼图通过组合a经典禁忌搜索与arc-consistency 3（AC3）算法充当域减少器。这个想法是应用AC3程序作为一个预处理阶段，而且也应用在禁忌搜索的每次迭代以便主动过滤域。这种集成明显减少了禁忌搜索迭代的次数，加快了求解速度处理。我们将说明我们的方法的实验结果要优于在不完全方法文献中所提及的方法。

本文结构如下所述。相关工作介绍在第2节，其次是初步工作。新的数独混合AC3-tabu搜索算法在第4节中描述。实验在第5节中说明。在最后，是我们得出结论和给出未来工作的一些方向。

窗体顶端

相关工作

文献提出了几种解决方法来解决、评级和产生数独问题。数独问题可以被完全解决，通过使用强力算法，回溯式过程来解决或一般的完整搜索方法（Crawford，Aranda，astro，＆Monfroy，2008; Lynce＆Ouaknine，2006;Moon＆Gunther，2006; Simonis，2005）。在本文中，我们关注在这种问题特别难处理的实例中用不完全搜索方法来解决数独谜题。在这方面，不同的方法都被提及了。例如，Asif（2009）提出了一个蚁群解决数独问题的优化算法。作者使用作为正确数字的启发式信息放置在板上。然而，达到的最佳值是76，81便是全局最优。在Moraglio and Togelius（2007）中提出了几何粒子群优化（GPSO）算法。他们的目标是验证GPSO的使用对于不重要组合空间对比于比性能的结果。事实上他们实现72％的成功;对于50次尝试中的36尝试达到全局最优。

登山者也经过测试来解决数独难题（Moraglio et al.，2006），他们能够成功完成容易数独，而中等和困难数独则失败了。在Moraglio et al.（2006）中，遗传算法（GA）也用于求解数独谜题。在特定汉明空间交叉和交换空间交叉中，几何交叉的行为被研究。两种方法都比爬山者和突变单独表现更好。但是，他们不能解决中等数独，并只能通过使用交换空间交叉，30个困难数独中的15个被解决。在Mantere and Koljonen（2007）提出了另一种GA方法。用来解决不同类别的数独：简单，中等，和困难。该算法是一个致力于解决魔方问题的扩展。解决容易和中等数独展现出良好的结果，能够解决30个困难数独中的2个。在Mantere and Koljonen（2008a）中提出了一种使用传统算法的类似方法，但是通常被GA先前提及的所取代。

Lewis（2007）提出了数独的模拟退火算法。这个想法是将谜题模型化为优化问题，其中的目标是最小化放置在棋盘上错误的数字数量。然而，该方法主要集中在创建可解决的问题实例，而不是解决困难数独谜题。

小单元 列

行

图1. 数独问题求解规则

初步工作

3.1 禁忌搜索

禁忌搜索（TS），由Glover引进，是一种元启发式，尤其致力于解决组合优化问题。它已经成功地用于解决不同类型的现实生活问题以及学术文献中的知名问题，如旅行推销员问题，背包问题，二次分配问题或时间表问题。

TS的核心思想依赖于采用局部搜索过程使其允许从一个潜在解决方案迭代地移动到另一个有希望的解决方案，直到已经达到一些停止标准。这个过程补充了称为禁忌列表的存储器结构，这可能是从许多不完全的方法中区分TS的主要特征。这个内存结构的目标是双重的：（1）帮助TS逃离不良评分区域，（2）

并避免返回最近访问的状态。

算法1描述了禁忌搜索的经典过程达到最小化。作为输入，它接收禁忌列表的大小和输出返回它达到的最佳解。然后，初始解决方案被创建，其通常是随机选择的。在第3行，while循环管理过程的迭代，直到满足给定的停止条件。 停止条件的一些示例是多个迭代限制或解决方案成本的阈值。在第7行，相邻解仅在它们被添加到候选列表时才被添加但不包含禁忌列表上的元素。然后，选择潜在的最佳候选，其通常对应于最佳质量解决方案成本。在第11行，所选择候选的成本将被评估。如果它优于S_best，它的特征被添加到禁忌列表中并且候选变成新S_best。最后，一些元素通常被允许按照添加的顺序从禁忌列表中终结。

算法1：禁忌搜索

窗体顶端

3.2 弧一致性

如Simonis（2005）所示，数独可以表示为约束网络，并且作为结果，来自约束满足的技术可以应用于它们。电弧一致性约束是最常用的约束满足过滤技术之一，用来减少问题的组合空间。 电弧一致性被正式定义为约束规划领域内的局部一致性（Rossi et al.，2006）。 局部一致性定义约束问题必须满足约束后的属性传播。约束传播只是一个过程，当给定的本地一致性强制执行到问题上。在下面，我阐述一些必要的定义（Bessiegrave;re，2006）。

定义1（约束）。 约束c是在a上定义的关系变量序列X（c）=(x_i1，...，x_i|X(c)|)，称为c的表格。C是Z^|X(c)|的子集，包含值的组合（或元组）tau;isin; Z^|X(c)|。 |X(c)|被称为c的参数数量。一个约束c与表格X（c）=(x₁，...，x_k)也被标注为c(x₁，...，x_k)。

定义2（约束网络）。约束网络也称为约束满足问题（CSP），由三元组定义：N=lt;X，D，Cgt;，其中：

X是整数变量的有限序列X=(x₁，...，x_n)。

D是X的对应域集合，也就是说，D =D(x₁ ) times;...times; D(x_n)，其中D(x_i)isin; Z是变量x_i可以采用的有限值集合。

C是一组约束C = {c₁，... ，c_e}，其中X（c_j）中的变量在X中。

定义3（投影）。c在Y上的投影表示为pi;_Y（c），其定义与包含元组的方案Y的关系可以扩展到X（c）上的元组且满足c。

如前所述，弧一致性是最多的使用传播约束的方式。最初是电弧一致性定义为二元约束（Mackworth，1977a，1977b），即涉及两个变量的约束。我们这里给出更一般的非任意约束的定义称为广义弧度（GAC）。

定义4（（广义）弧一致性）。给定一个网络N = lt;X，D，Cgt;，约束c isin; C和变量x_i isin;X（c），

 如果存在有效值，则值v_i isin;D（x_i）与c isin; D一致满足c的元组，使得v_i =tau;[{x_i}]。 这样的元组称为a在c上支持（x_i，v_i）。

 域D是（广义的）弧在c上一致，对于x_i如果所有D（x_i）中的值与D中的c一致，即，D（x_i）isin;pi;_xi（ccap;pi;_X(c)（D））。

 网络N是（广义的）弧一致性如果D是（广义的）弧对于C中的所有约束上的X中的所有变量是一致的作为示例，让我们考虑描绘在图2的左侧的非弧一致网络N。它考虑了三个变量x₁，x₂和x₃，和域D（x₁）=D（x₂）=D（x₃）={0，1，2}，约束c₁₂：（x₁lt;x₂）和c₂₃：（x₂=x₃）。强制弧一致性允许一个消除一些不一致的值。例如，当约束c₁₂被验证时，来自D（x₁）的值2被去除，因为那里是没有大于它在D（x₂）的值。D（x₂）的值为0删除，因为它不存在在D（x₁）中的支持。从中删除0，当选中c₂₃时，导致 D（x₂）从 D（x₃）中移除0。所得到的弧一致网络在图2右侧示出。

这种滤波处理可以通过使用算法2来执行。如前所述，这个过程的主要思想是修改弧，即消除与给定约束c不一致的D（x_i）中的每个值。这个概念封装在函数Revise3。该函数采用D（x_i）中的每个值v_i（第2行）并分析空间tau;isin;ccap;pi;_X(c)（D），搜索约束c（第3行）上的支持。如果支持不存在，则值v_i从D（x_i）中消除。最后，该函数通知D（x_i）是否已经通过返回true改变，否则改变false（行8）

算法2：Revise3

算法3负责确保每个域都是与约束集一致。这通过使用循环来完成验证弧直到没有变化。函数用对（x_i， c）填充列表Q为开头，使得x_i isin;

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[138668]，资料为PDF文档或Word文档，PDF文档可免费转换为Word