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

第39卷第21期 数学的实践与认识 V01．39No．21 2009年11月 Nove．，2009 MATHEMATICSINPRACTICEANDTHE()RY ～～ ．t^●^^～～建～ ～～～模～一_，， 基于“挖洞思想的数独游戏生成算法 薛源海， 蒋彪彬， 李永卓 指导老师：闫桂峰， 孙华飞 (北京理工大学理学院数学系，北京 100081) 摘要： 设计一个算法用以生成各种难度等级的数独题，通过对游戏规则的分析，首先从以下三个方面定 义难度等级：已知格总数、已知格的分布和穷举有哪些信誉好的足球投注网站复杂度．本算法采用“挖洞”思想。经过以下两步生成数独 题：1)运用拉斯维加斯随机算法生成一个终盘；2)采用以下五个操作“抹去”一部分数字来生成数独题：① 根据所需要的难度等级选取一种挖洞顺序；②制定两个约束来控制已知格的分布；③通过深度优先有哪些信誉好的足球投注网站来 求解，从而保证“挖去”一个数字后该数独题仍有唯一解l④引入剪枝技术来避免无效的“挖洞”尝试；⑤对 “挖”好。洞”的数独题进行等效对称变换。以增加题目的多样性．可以生成游戏者所需要的任意5种难度的数 独题．经过对算法时间和空间复杂度的分析．论证了本算法的有效性．对“挖洞法”的研究成果可总结为以下 三个方面：1)通过对“挖洞”顺序的大量试探．找到了可生成高难度数独题的“挖洞”顺序}2)采用反证法来 判断一个数独题解的唯一性；3)通过避免“回溯”和“重填”来降低算法的运行时间． 关键词： 挖洞法；拉斯维加斯算法；剪枝；反证法 1 问题的提出 数独是一种源自18世纪末的瑞士．后在美国 一 一 m 叶 吐 也 卜 ∞ a 发展，并在日本得以发扬光大的数学智力拼图游 霰幕幕最霄幕 京幕幕 戏【1]．其游戏规则为：在由9个小九宫格组成的 行l 大九宫格(9格×9格)里，已填有若干数字；需用 行2 l 2 3 数字1～9填满剩下的空格，使得每一行和每一列 行3 行4 都包含数字1～9，每个小九宫格里也均是数字1～ 行5 4 5 5 9，并且每个数字在它所在的行、列以及小九宫格 行6 里面都只出现一次．该游戏环境如图1所示． 行7 近年来，数独游戏正吸引着世界上无数的 行8 7 8 9 游戏挑战者．他们水平各异，所以一些计算机学 行9 者们正致力于设计算法使其在尽可能短的时间 图1数独游戏环境 内生成不同难度等级的数独题，以满足不同水 平游戏者的需求…．在此，本文提出了一种基于“挖洞”思想的数独题生成算法，同时考虑到 三个方面要求：可变化的难度、解的唯一性和算法复杂度最小化． 收稿日期：2008—07·04 注：2008年美国数学建模竞赛(MCM)--等奖(MeritoriousWinner) 万方数据 2 数学的实践与认识 39卷 2问题的分析