基于挖洞思想的数独游戏生成算法

《基于挖洞思想的数独游戏生成算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据第39卷第21期数学的实践与认识V01．39No．212009年11月MATHEMATICSINPRACTICEANDTHE()RYNove．，2009基于“挖洞"思想的数独游戏生成算法薛源海，蒋彪彬，李永卓指导老师：闫桂峰，孙华飞(北京理工大学理学院数学系，北京100081)摘要：设计一个算法用以生成各种难度等级的数独题，通过对游戏规则的分析，首先从以下三个方面定义难度等级：已知格总数、已知格的分布和穷举搜索复杂度．本算法采用“挖洞”思想。经过以下两步生成数独题：1)运用拉斯维加斯随机算

2、法生成一个终盘；2)采用以下五个操作“抹去”一部分数字来生成数独题：①根据所需要的难度等级选取一种挖洞顺序；②制定两个约束来控制已知格的分布；③通过深度优先搜索来求解，从而保证“挖去”一个数字后该数独题仍有唯一解l④引入剪枝技术来避免无效的“挖洞”尝试；⑤对“挖”好。洞”的数独题进行等效对称变换。以增加题目的多样性．可以生成游戏者所需要的任意5种难度的数独题．经过对算法时间和空间复杂度的分析．论证了本算法的有效性．对“挖洞法”的研究成果可总结为以下三个方面：1)通过对“挖洞”顺序的大量试探．找到了

3、可生成高难度数独题的“挖洞”顺序}2)采用反证法来判断一个数独题解的唯一性；3)通过避免“回溯”和“重填”来降低算法的运行时间．关键词：挖洞法；拉斯维加斯算法；剪枝；反证法1问题的提出数独是一种源自18世纪末的瑞士．后在美国发展，并在日本得以发扬光大的数学智力拼图游戏【1]．其游戏规则为：在由9个小九宫格组成的大九宫格(9格×9格)里，已填有若干数字；需用数字1～9填满剩下的空格，使得每一行和每一列都包含数字1～9，每个小九宫格里也均是数字1～9，并且每个数字在它所在的行、列以及小九宫格里面都只出

4、现一次．该游戏环境如图1所示．近年来，数独游戏正吸引着世界上无数的游戏挑战者．他们水平各异，所以一些计算机学者们正致力于设计算法使其在尽可能短的时间内生成不同难度等级的数独题，以满足不同水行l行2行3行4行5行6行7行8行9一m叶吐也卜∞a霰幕幕最霄幕京幕幕l2345789图1数独游戏环境平游戏者的需求⋯．在此，本文提出了一种基于“挖洞”思想的数独题生成算法，同时考虑到三个方面要求：可变化的难度、解的唯一性和算法复杂度最小化．收稿日期：2008—07·04注：2008年美国数学建模竞赛(MCM)-

5、-等奖(MeritoriousWinner)一_，----，～模～～～建～．t^●^^～万方数据2数学的实践与认识39卷2问题的分析要能保证算法生成的数独题具有可变化的难度和唯一解，该算法内部应该包含有对数独题的求解和评级功能．本文将该算法的设计工作分为评级、求解和生成3部分工作．首先，根据游戏者需求的难度等级，我们从已知格的总数和分布以及穷举求解的搜索次数这三个方面特性，通过赋权求和来评估一个数独题的难度等级．然后，运用“反证法”思想，并结合“深度优先搜索求解器”一起论证一个“洞”被“挖去”后是

6、否能保证该题有唯一解．最后，论证了可通过避免“重填”一个被“挖去”的格子，或者“回溯”到一个曾经无法“挖去”的格子，来降低算法的复杂性．3模型的假设和定义1)在本文中，我们将数独游戏的格盘大小定为9格X9格，不涉及其他大小的格盘．2)文中所有关于运行时间的统计数据都是通过我们的计算机得到的；在同等的计算环境下，这些数据足可靠而具有可比性的．4难度等级的度量在本节中。我们从人类的逻辑推理和计算机的穷举搜索两方面来评估一道数独题的难度．由于游戏者对未知格的推理建立在已知格所提供的信息上．而已知格的数量

7、和分布决定了它们能为游戏者所提供信息的多少E33．已知格数量越少，其分布越不均匀、不对称，该数独题通过逻辑推理的求解难度就越大．由此针对某一道数独题(见图2)，我们给出如下三个评定项目(见表1)，对其进行0～5分的评估，并给这三项指标赋予相应的权重，进而求和得到该题的得分(亦为0～5分)．将该分数的整数部分用以权衡游戏者需求的难，0tI，●1‘●I‘7彳I●，●图2数独题评分样例度等级如下：等级一，低级，o～1分；等级二。初级，1～2分；等级三，中级，2～3分；等级四，高级，3～4分；等级五，骨灰

8、级，4～5分．表l数独题评分表5算法详述整个生成数独题的算法分为两步执行：先随机生成一个填满数字且符合游戏约束的终盘。而后根据所需求的难度等级“抹去”一些数字。每“抹去”一个数字就验证一次解的唯一性．如此往复直至满足所需的难度要求为止．最后通过适当的等价对称变换后输出该题．万方数据21期薛源海。等：基于“挖洞”思想的数独游戏生成算法35．1求解算法：深度优先搜索为了让生成算法可以判断任意一个数独题是否有唯一解，我们建立一个可以搜遍所有可行解的数独求解器．由于我们定义的数独格盘的大小