avatar

光和尘

有花满渚、有酒盈瓯

目录检索关于我

🔖 gamesudoku

前言

前一阵子想要整理一下精确覆盖问题和 DLX 算法,为了验证对算法理解的准确性写了一道数独的题目。想起大学时用 C++ 写过一个回溯版的,当时还兴致冲冲地拿它去求解手机上的数独游戏。想到这里时还特意在电脑上翻了好久也没能找到当时的代码;想起那时在 codevs.cn 上做过提交,本来还想去嫌弃下自己当年写的代码的,结果发现 codevs.cn 好像死掉了。

时间过得可真快,转眼间又是几个春秋。而我仿佛总是在迟到,好几件事情都没能在最希望完成的时候做到,却又在过后耿耿于怀,不甘心地追逐着过去的时空里所发生的期待。不是在原地踏步,可还是开始动摇,想必继续往前的地方是没有尽头的。

什么是数独

一个经典的数独游戏由 x^2 \times x^2 的网格构成,游戏的规则就是在网格上填数直到满足下述四个约束:

  1. 网格中所有的格子都恰好填上一个数字
  2. 每一行中需要出现 [1, x^2] 之间的所有整数
  3. 每一列中需要出现 [1, x^2] 之间的所有整数
  4. 每一个子方阵中需要出现 [1, x^2] 之间的所有整数

如下所示是一个经典的 9 \times 9 的数独面板,其中粗线围成了 x^2=9 个子方阵 [1]

生成一个数独谜题

要写一个离线游戏首先要解决数据的问题,对于数独要考虑的问题有:

  • 如何确保存在解
  • 如何确保唯一解
  • 如何区分难度
  • 如何获得更好的随机性

如何确保存在解

  • 先生成一个填满的数独面板 G(r, c)

    在数独面板上选取若干个位置,无冲突地填入值,然后跑求解数独的算法,若无解,则从之前选取填入的位置中选取一个,将其上面的值擦除,再运行求解数独的算法,不断重复此过程,必然能得到一个填满的数独[2]

    如何求解数独可参见 精确覆盖问题和 DLX 算法

  • 在一个填满的数独面板中选取若干个位置,依次枚举这些位置 (r, c),尝试将上面的值 v=G(r, c) 擦除,则得到一个必定存在解的数独谜题。

如何确保唯一解

  • 在上一步选取待擦除位置的操作中增加一个校验的逻辑:尝试擦除位置 (r, c) 上的值 v = G(r, c) 时,枚举 [1, x^2] 之间除 v 外的所有整数 v',并将格子 (r, c) 的值设置为 v',对于每次枚举都分别跑一次求解数独的算法,若存在解,说明此位置上的值不能擦除[3];否则,擦除此格子上的值。

如何区分难度

  • 一个直观的印象是:数独面板中缺失的格子越多,想要解决的困难度越大。所以难度可以映射为在生成数独谜题时尽可能多地尝试擦除格子。

下面是一个示例,拖动滑块以切换难度。

如何获得更好的随机性

  • 在初始填充的数独面板时:

    • 随机选取填充的位置

      将所有的格子排成一排,为方便叙述不妨将其记为 T,应用 Knuth Shuffle 算法将其顺序打乱。则在随机选取格子时直接遍历打乱顺序后的 T 就可以了。一方面 Knuth Shuffle 保证了每个格子以相同的概率排在任一位置上;另一方面直接遍历 T 相比随机枚举格子,不存在重复枚举的可能性。

    • 按随机顺序枚举某个位置上可填入的值

      枚举 v' 时可以先求出一个候选项列表[4],同样地,将候选项列表打乱顺序后进行遍历。

  • 在尝试擦除格子时:

    • 随机选取待擦除的位置

      类似地,在尝试擦除格子时,可以通过遍历 T 达到随机枚举格子的效果。检查擦除此位置时是否存在多解时,直接按顺序遍历即可。

      为了体现难度,可以只对前 \displaystyle \left\lceil difficulty \times \big\lvert T \big\rvert \right\rceil 个格子进行擦除尝试。

交互设计

除了数据外还需要考虑几个交互问题:

  • 切换难度和数独面板的大小
  • 暂停(暂停时用模糊滤镜遮住谜题)、继续游戏、重新开始游戏
  • 计时器:支持暂停、恢复、重置
  • 区分谜题预填充的格子和玩家填充的格子
  • 格子的输入
  • 输入冲突的值时高亮提醒
  • 选中非空格子时高亮与之值相同的格子
  • 完成游戏时的简易提示
  • 简易的提示和小抄
  • 完成某行、列或子方阵时的提示动画

附录

下面我实现的一个简易数独,求解数独以及生成数独所需的数据的算法我封装到了 @algorithm.ts/sudoku 中,有兴趣的朋友可以自取。ui 组件打算之后做好整理再开源。

© 2017-2021 光和尘有花满渚、有酒盈瓯

Comments