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

基于“挖洞”思想的数独游戏生成算法 薛源海, 蒋彪彬, 李永卓 指导老师: 闫桂峰, 孙华飞 ( )北京理工大学理学院 数学系, 北京 100081 摘要: 设计一个算法用以生成各种难度等级的数独 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 , 通过对游戏规则的 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 , 首先从以下三个方面定 义难度等级: 已知格总数、已知格的分布和穷举搜索复杂度. 本算法采用“挖洞”思想, 经过以下两步生成数独 题: ) ) 1运用拉斯维加斯随机算法生成一个终盘; 2采用以下五个操作“抹去”一部分数字来生成数独题: ? 根据所需要的难度等级选取一种挖洞顺序; ? 制定两个约束来控制已知格的分布; ? 通过深度优先搜索来 求解, 从而保证“挖去”一个数字后该数独题仍有唯一解; ? 引入剪枝技术来避免无效的“挖洞”尝试; ? 对 “挖”好“洞”的数独题进行等效对称变换, 以增加题目的多样性. 可以生成游戏者所需要的任意5 种难度的数 独题. 经过对算法时间和空间复杂度的分析, 论证了本算法的有效性. 对“挖洞法”的研究成果可 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 为以下 三个 ) ) 方面: 1通过对“挖洞”顺序的大量试探, 找到了可生成高难度数独题的“挖洞”顺序; 2采用反证法来 判断 ) 一个数独题解的唯一性; 3通过避免“回溯”和“重填”来降低算法的运行时间. 关键词: 挖洞法; 拉斯维加斯算法; 剪枝; 反证法 1 问题的提出 数独是一种源自18 世纪末的瑞士, 后在美国 发展, 并在日本得以发扬光大的数学智力拼图游 1 戏. 其游戏规则为: 在由 9 个小九宫格组成的 ( ) 大九宫格9 格×9 格里, 已填有若干数字; 需用 数字1, 9 填满剩下的空格, 使得每一行和每一列 都包含数字1, 9, 每个小九宫格里也均是数字1, 9, 并且每个数字在它所在的行、列以及小九宫格 里面都只出现一次. 该游戏环境如图1 所示. 近年来, 数独游戏正吸引着世界上无数的 游戏挑战者. 他们水平各异, 所以一些计算机学 者们正致力于设计算法使其在尽可能短的时间 图 1 数独游戏环境 内生成不同难度等级的数独题, 以满足不同水 2 平游戏者的需求. 在此, 本文提出了一种基于“挖洞”思想的数独题生成算法, 同时考虑到 三个方面要求: 可变化的难度、解的唯一性和算法复杂度最小化. 2 问题的分析 要能保证算法生成的数独题具有可变化的难度和唯一解, 该算法内部应该包含有对数 独题的求解和评级功能. 本文将该算法的设计工作分为评级、求解和生成 3 部分工作. 首先, 根据游戏者需求的难度等级, 我们从已知格的总数和分布以及穷举求解的搜索次数这三个方面特性, 通过赋权求和来评估一个数独题的难度等级. 然后, 运用“反证法”思想, 并结合“深度优先搜索求解器”一起论证一个“洞”被“挖去”后是否能保证该题有唯一解. 最 后, 论证了可通过避免“重填”一个被“挖去”的格子, 或者“回溯”到一个曾经无法“挖去”的格 子, 来降低算法的复杂性. 3 模型的假设和定义 ) 1在本文中, 我们将数独游戏的格盘大小定为 9 格×9 格, 不涉及其他大小的格盘. ) 2文中所有关于运行时间的统计数据都是通过我们的计算机得到的; 在同等的计算环 境下, 这些数据是可靠而具有可比性的. 4 难度等级的度量 在本节中, 我们从人类的逻辑推理和计算机的穷举 搜索两方面来评估一道数独题的难度. 由于游戏者对未 知格的推理建立在已知格所提供的信息上. 而已知格的 数量和分布决定了它们能为游戏者所提供信息的多 3 少. 已知格数量越少, 其分布越不均匀、不对称, 该数 独题通过逻辑推理的求解难度就越大. () 由此针对某一道数独题 见图 2, 我们给出如下三个 () 评定项目 见表 1, 对其进行 0, 5 分的评估, 并给这三项 图 2 数独题评分样例 ( 指标赋予相应的权重, 进而求和得到该题的得分 亦为 0 ) , 5 分. 将该分数的整数部分用以权衡游戏者需求的难 度等级如下: 等级一, 低级, 0, 1 分; 等级二, 初级, 1, 2 分; 等级三, 中级, 2, 3 分; 等级四, 高级, 3, 4 分; 等级五, 骨灰级, 4, 5 分. 表 1 数独题评分表 评分项目 详细描述 权重 得分 已知格总数 总共 22 个已知, 在等级五范围内 0. 4 5 行、列中已知格数的低限0. 3 5 第一行中有 0 个已知, 达到等级五的低限 穷举搜索次数0. 3 4 263734 次, 等级四 总评总分4. 7 等级五, 骨灰级 5 算法详述 整个生成数独题的算法分为两步执行: 先随机生成一个填满数字且符合游戏约束的终 盘, 而后根据所需求的难度等级“抹去”一些数字, 每“抹去”一个数字就验证一次解的唯一 性. 如此往复直至满足所需的难度要求为止. 最后通过适当的等价对称变换后输出该题. 5. 1 求解算法: 深度优先搜索 为了让生成算法可以判断任意一个数独题是否有唯一解, 我们建立一个可以搜遍所有 可行解的数独求解器. 由于我们定义的数独格盘的大小仅为 9 格×9 格, 所以我们采用穷举 搜索的办法, 按照深度优先的搜索顺序, 找出一个数独题的所有可行解. 求解器由上至下, 从左至右对每个空格进行填数尝试, 即填入一个 1, 9 的数字, 同时检 (验填入的数字是否满足数独游戏对每个格内数字的三个约束数字 1, 9 分别有且仅有一次 ) 出现在每行、每列和每个小九宫格中, 若能满足则视此次填入的数字可行. 若在一个空格的 尝试中, 1, 9 均无法填入, 则回溯到前一个所尝试的空格中并将其中已填入的数字替换成 其他未尝试过的数字. 如此往复直至找遍所有可行解. 5. 2 生成算法 借助先前建立的两个工具: 难度评定准则和遍历搜索求解器, 我们用以生成数独题的算 ) ) ) 法分为如下三步进行: 1生成一个终盘; 2在终盘上“挖洞”; 3对“挖”好的题进行等效 变换. () 5. 2. 1 生成终盘: 拉斯维加斯算法 源代码见附录 ( 我 们采用拉斯维加斯算法随机生成一个数独题的终盘 所谓“终盘”, 即数独题的答 )案. 首先, 在一个数独“空盘”中随机选中个格子, 在这些格子内随机填入数字1, 9; 然后, n () 调用先前的求解器对这个已知 格的数独题进行求解. 完成上述两步操作的代码段为 n S n () () 如果有解, 则返回否则返回拉斯维加斯算法的思 : ; . BOOL la s - vega s n S n TRUEFAL SE4 () 想便是不断重复执行 直至其返回 为止, 用编程语言表示如下:, la s - vega s n TRUE (() ) ! ;w h ile la s - vega s n ) () (代码段返回即成功生成一个“终盘”的概率与值有关. 通过对 la s - vega s n TRUE p n 值进行大量的尝试和调整, 我们发现当= 11 时, 概率已能达到99. 7% , 且随着的减 n n p p n 小而增大, 但运行时间延长. 故我们将设为 11.n ()5. 2. 2 “挖洞”算法 源代码见附录 “挖洞法”的基本思想就是“挖去”一个数独终盘上的一些格子, 使其成为有唯一解的数 独题. 然而“挖洞”的机制是多种多样的, 为了加快出题算法的速度, 我们将“贪心”机制引入 到我们的“挖洞”策略当中. 整个“挖洞”算法的 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 图如图 3 所示. () 以下我们将对“挖洞”流程中的 5 个关键操作 如流程图中标记所示进行详细说明.操作 1 “挖洞”顺序 “挖洞”顺序即在一个终盘 上, 决定哪个位置 表 2 难度等级对应的“挖洞”顺序 的格子先被“挖去”, 哪个格子是下一个. 该顺序对难度等级 “挖洞”顺序 生成的题目中已知格的分布起决定性作用. 我们 ) ( 1 低级全盘随机 通过大量尝试, 选取了以下四个较为有效的顺序 ) ( 2 初级全盘随机 () 图 4, 并根据四者的效果将其分配给 5 个难度等 ) ( 3 中级间隔 ()级表 2. ) ( 4 高级蛇形 ) ( (() ) 5 骨灰级从左到右, 至顶向下 顺序 1 从左到右, 至顶向下 见图 4 a (() ) 顺序 2 蛇形 见图 4 b (() ) 顺序 3 间隔 见图 4 c 顺序 4 全盘随机 操作 2 “挖洞”约束 根据难度等级的定义, 我们对“挖洞”操作加 入两个约束来影响已知格的分布态势: ) ( 约束 1 已知格的总数已知格数最多为 80 格, 将 0, 80 大致均分为五个区间, 对应到 5 个难 度等级. 已知格越少则题越难. 若游戏者需要某个 难度的数独题, 则在其对应的区间内随机一个数 作为已知格数的下界, 即当“挖洞”至剩余格数达 到下界时停止. ) ( 约束 2 行、列中已知格数的低限同理约束 1, 每行、每列剩余的格数必须多于难度等级所规 定的下界, 否则禁止此次“挖洞”操作. 每尝试“挖去”一个格子, 都要检验一次“挖 去”该格后是否与这两个约束冲突. 一旦冲突则禁 止此次“挖洞”. 操作 3 反证法判断解的唯一性 我们借助“反证 法”的思想提出了一个新的策略 来随时检验当一个格子中的数字被“挖去”后, 是否能 保证此题还有唯一解. 该策略按步解释如下. 假设在一次“挖洞”尝试中, 我们试图抹去一 个填有数字 6 的格子. 图 3 “挖洞”算法流程图 步骤1 将数字6 依次替换为除6 以外1, 9 的 其他八个数字, 检查是否违反游戏规则. 图 4 “挖洞”顺序图示 步骤 2 调用求解器对完成步骤 1 后的数独题进行求解. 步骤 3 一旦求解器能得到一个解, 便立即终止求解器, 同时宣布抹去 6 后得到的题至 少有两解. 因为针对这一空格, 原本填入 6 时已有一个来自初始终盘的解. 步骤 4 只有当所有除 6 外的八个数依次经过步骤 1 的检验, 同时步骤 2 中求解器遍历搜索后回复无解, 才能保证抹去数字6 后的数独题的解具有唯一性, 即判定此次“挖洞”操作 是合法的. 操作 4 剪枝优化 我们通过剪枝优化来降低耗费在“挖洞”尝试中的运行时间. 该优化过程如图 5 所示. 图 5 剪枝优化过程图示 (( ) () )假设我们刚完成了位于 行 1, 列 1的“挖洞”, 在此将空格用 0 表示 见图 5 . 接下来 a () (() ) 我们按顺序尝试抹去 行1, 列2格子中的数字2 见图5 , 随后我们通过求解器发现抹去 b 数字 2 后的数独题至少有两解. 既然抹去数字 2 后留下的题是多解的, 我们论定再抹去更多 ((() ) () ) 的格子 如再抹去 行2, 列1中的数字3后留下的题 见图5 仍是多解的. 因此, 我们保留 c ( () ) 行1, 列2中的数字2, 继续进行随后的“挖洞”尝试. 接着我们尝试抹去 行2, 列1中的数字 (() ) 3 见图5 , 而后发现抹去3 后的题仍有唯一解. 按照先前的描述, 我们应该对下一个格子 d (()) 进行“挖洞”尝试. 此时, 我们禁止选取曾经尝试过的格子, 行1, 列2. 因为一旦 行1, 列2中 () 的数字 2 再次被抹去, 则将再次回到图 5 中多解的局面. 因此, 我们限定成功抹去数字 3 c (() ) 后, 禁止选取曾经被尝试过的格子 行 1, 列2和已经被“挖”成空格的格子 行1, 列1作为下 一个“挖洞”尝试格. 综上可知, 我们规定初始终盘上的每个满格只允许做一次“挖洞”尝试, 即我们至多需要做 81 次“挖洞”尝试, 而且任何空格将不会被重填, 这一点不同于现有的“回 溯”思想. 为了论证以上剪枝优化技术的有效性, 我们做了大量的对比实验, 以生成一道骨灰级难 度的题所需要的运行时间为 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 , 得到统计结果如表 3 所示, 从而说明了引入剪枝优化可以 大大降低出题的运行时间. 表 3 剪枝对运行时间的影响 操作 5 等效变换 是否加入剪枝优化 平均运行时间 为了增加所出题目的多样性, 我们对完成以上 没有剪枝 55106. 23m s ( 操作后得到的数独题进行如下 4 种等效变换 变换 加入剪枝 1088. 35m s )后不违反游戏规则. (变换1 互换任意两种数字的位置 例如将格盘 )中所有的“1”和所有的“9”互换位置. (变换 2 整体互换任意两个小九宫格行或小九宫格列 例如行1、行2 和行3 组成一个小 )九宫格行整体 () () () 变换 3 在同一个小九宫格行 列中重排 互换行列. 变换 4 全盘行、列互换, 即矩阵转置. 6 结 果 运用以上建立的生成算法, 我们得到了五种不同难度等级的数独题如图 6 所示: 7 复杂度分析 我们建立的数独题生成算法的数据存储空间是可忽略的. 因此我们着重分析时间复杂 ()图 6 结果示例 粗体为已知格 度, 看其是否能在游戏者可忍受的时间范围内生成所需要的题. ()在整个生成算法中, 随机生成终盘只耗费常数级时间, 可表示为 O 1. 而在“挖洞”算 法中, 我们知道加入剪枝优化后的算法只需要做至多 81 次“挖洞”尝试, 这其中调用了深度 5 () 优先搜索求解器. 深度优先搜索的时间复杂度为 ( V + E . 而我们粗略估计整个数独求 () 解问题的复杂度 ( V + E 会低于 1500000. 8 结 论 为了生成多难度等级的数独题, 我们建立了数独题难度评定准则, 并借用“挖洞”思想设 计了数独生成算法. 现将本文中所提出的“挖洞”新机制总结如下: 结论 1 从左到右、至顶向下的“挖洞”顺序有助于生成高难度等级的数独题; 而全盘随 机“挖洞”有利于生成低难度等级的题目. 结论 2 运用“反证法”来验证数独题解的唯一性比遍历搜索所有解更为简便和快捷. 结论3 通过避免“回溯”到一个曾经尝试过的格和“重填”一个空格, 可以大大降低算法 的运行时间, 这便是我们引入的剪枝优化技术. 与现代优化算法, 如“遗传算法”相比, 我们基于“挖洞”思想的数独生成算法耗费了较少的运算时间和存储空间. 下面给出我们的算法和文献6 所用的“遗传算法”在求解同一组数 7 (独的对比实验. 文献6 在试验部分求解了来自网站所提供的 27 道数独题 共 9 级不同的 )难度, 每个难度等级 3 个题. 我们使用2. 664 处理器的机同样求解了这些 G H z P en t ium PC 题目. 结果我们的算法只用了4. 509 秒, 平均每题耗时为01167 秒. 而文献6 的“遗传算法” 6 () 310 4求解这些题却用了111 秒, 平均每题4111 秒. 在数据存储方面, 我们 GH z P en t ium 的算法只需要存储 5 个 9×9 的二维数组. 而文献6 的“遗传算法”在每次迭代中需要存储 21 个“染色体”, 每个“染色体”长度为81 个单位, 这还未包括其余在“交叉”、“变异”操作中的 临时存储. 所以可以看出, 我们的算法在运算时间和存储空间上要优于文献6 所提出的 “遗传算法”. 参考文献: () 1 2. [. , 2006.W e iM eng L eeP ro g ramm ing Sudo k u T ech no lo gy in A c t io n M A p re ss 2 [ ƒƒƒƒ, ƒƒ.. : . . . 1B e r t ram F e lgenh aue r and F raze r J a rv is EB OL h t tpwwwsh efacuk pm af jsudo k u 3 . [ ƒƒƒƒƒ. : . . . . . Go rdo n Ro y leM in im um Sudo k u EB OL h t tpp eop lec sseuw aeduau go rdo nsudo k um inp hp 4 A lsuw a iye l M H. A lgo r ithm s D e sign T ech n ique s and A na ly sis [ M . L o ndo n: W o r ld Sc ien t if ic P ub lish ing Com p any, 1998. 5 , , . T hom a s H Co rm en C h a r le s E L e ise r so n Ro na ld L R ive st and C liffo rd S te inIn t ro duc t io n T o A lgo r ithm s () [. , : , 2002.Secco nd E d it io nM C am b r idgeU SA T h e M IT P re ss 6 , . , [ ] ? T im o M an te reJ anne Ko ljo nenSo lv ingra t ing and gene ra t ing sudo k u p uzzle w ith GA C IE E E Co ng re ss o n , 2007, 25228, 138221389.E vo lu t io na ry Com p u ta t io n 7 : [ ƒ. : ƒƒ. . ƒƒA am u leh t iSudo k u o n line EB OL h t tpwwwaam u leh t if isudo k u : Sudoku Puzz le s Gen era t in gFrom Ea sy to Ev il 222, , XU E Y u an h a iJ IA N G B iao b in L I Yo n gzh uo 22: , A dv iso rYA N Gu ifen g SU N H u afe i (), , 100081, D ep a r tm en t o f M a th em a t ic sB e ijing In st itu te o f T ech no lo gyB e ijing C h ina : A bstrac tSudo k u p uzzle becom e s w o r ldw ide pop u la r am o ng m any p laye r s in d iffe ren t . in te llec tua l leve lsT h e ta sk is to dev ise an a lgo r ithm th a t c rea te s Sudo k u p uzzle s in va ry ing . , leve l o f d iff icu ltyW ith th e ana ly sis o f th e gam e ru le sw e f ir st def ine th e d iff icu lty leve l f rom : , fo u r a sp ec t s a sto ta l g iven ce llsd ist r ibu t io n o f g iven ce lls and com p lex ity o f enum e ra t ing .sea rch , B y th e gu idance f rom th e def in it io n o f d iff icu lty leve lth e a lgo r ithm fo r gene ra t ing p uzzle s “2”. , is deve lop ed w ith th ed igho lest ra tegy o n a va lid g r idT h u sth e a lgo r ithm deve lop ed in tw o : , step sto c rea te a va lid g r id by L a s V ega s a lgo r ithm and th en to gene ra t ing p uzzle s by e ra sing :som e d ig it s u sing f ive op e ra to r s ?, D e te rm ine a sequence o f d igg ing ho le s acco rd ing to th e de sirab le d iff icu lty leve l ?,Se t tw o re st r ic t io n s to gu ide th e d ist r ibu t io n o f g iven ce lls ?2J udge w h e th e r a p uzzle be ing dug o u t h a s a un ique so lu t io n by a so lve r bu ilt u sing D ep th ,F ir st Sea rch ?, A dd p run ing tech n ique to avo id d igg ing an inva lid ce lland ?2.P e rfo rm p rop aga t ing a t a dugo u t p uzzle to ra ise th e d ive r sity o f th e o u tp u t p uzzle , . U sing o u r deve lop ed a lgo r ithm w e gene ra te Sudo k u p uzzle s in any f ive d iff icu lty leve ls T h e d iff icu lty leve l o f o u tp u t p uzzle s can be ad ju sted by a de sirab le d iff icu lty va lue inp u t by . p laye r sT h e com p lex ity o f th e a lgo r ithm s in sp ace and t im e is ana lyzed to dem o n st ra te th e .effec t ivene ss o f th e a lgo r ithm s O u r m a in co n t r ibu t io n s in exp lo r ing th e“d ig2ho le ”st ra tegy a re summ a r ized a s fo llow ing : th ree w o rk sto do a m a ssive re sea rch o n th e sequence o f d igg ing ho le s and how it affec t s th e 2, a lgo r ithm to c rea te a ev illeve l p uzzle w ith m in im a l g iven ce llsto inven t a sk ill fo r judg ing th e ′, so lu t io ns un iquene ss o f a p uzzle be ing dug o u t by th e reduc t io n to ab su rd ityand to reduce th e .com p u ta t io na l t im e by avo id ing back t rack ing to an exp lo red ce ll and ref illing an em p ty ce ll 2: ; ; ; Keywordsd igho le st ra tegyla s vega s a lgo r ithm p run ingreduc t io n to ab su rd ity