当你想来一把数独
前言
¶前一阵子想要整理一下精确覆盖问题和 DLX 算法，为了验证对算法理解的准确性写了一道数独的题目。想起大学时用 C++ 写过一个回溯版的，当时还兴致冲冲地拿它去求解手机上的数独游戏。想到这里时还特意在电脑上翻了好久也没能找到当时的代码；想起那时在 codevs.cn 上做过提交，本来还想去嫌弃下自己当年写的代码的，结果发现
codevs.cn 好像死掉了。
时间过得可真快，转眼间又是几个春秋。而我仿佛总是在迟到，好几件事情都没能在最希望完成的时候做到，却又在过后耿耿于怀，不甘心地追逐着过去的时空里所发生的期待。不是在原地踏步，可还是开始动摇，想必继续往前的地方是没有尽头的。
什么是数独
¶一个经典的数独游戏由
- 网格中所有的格子都恰好填上一个数字
- 每一行中需要出现
- 每一列中需要出现
- 每一个子方阵中需要出现
如下所示是一个经典的
生成一个数独谜题
¶要写一个离线游戏首先要解决数据的问题，对于数独要考虑的问题有：
- 如何确保存在解
- 如何确保唯一解
- 如何区分难度
- 如何获得更好的随机性
如何确保存在解
¶先生成一个填满的数独面板
在数独面板上选取若干个位置，无冲突地填入值，然后跑求解数独的算法，若无解，则从之前选取填入的位置中选取一个，将其上面的值擦除，再运行求解数独的算法，不断重复此过程，必然能得到一个填满的数独[2]。
如何求解数独可参见 精确覆盖问题和 DLX 算法
在一个填满的数独面板中选取若干个位置，依次枚举这些位置
如何确保唯一解
¶- 在上一步选取待擦除位置的操作中增加一个校验的逻辑：尝试擦除位置
如何区分难度
¶- 一个直观的印象是：数独面板中缺失的格子越多，想要解决的困难度越大。所以难度可以映射为在生成数独谜题时尽可能多地尝试擦除格子。
下面是一个示例，拖动滑块以切换难度。
如何获得更好的随机性
¶在初始填充的数独面板时：
随机选取填充的位置
将所有的格子排成一排，为方便叙述不妨将其记为
按随机顺序枚举某个位置上可填入的值
枚举
在尝试擦除格子时：
随机选取待擦除的位置
类似地，在尝试擦除格子时，可以通过遍历
为了体现难度，可以只对前
交互设计
¶除了数据外还需要考虑几个交互问题：
- 切换难度和数独面板的大小
- 暂停（暂停时用模糊滤镜遮住谜题）、继续游戏、重新开始游戏
- 计时器：支持暂停、恢复、重置
- 区分谜题预填充的格子和玩家填充的格子
- 格子的输入
- 输入冲突的值时高亮提醒
- 选中非空格子时高亮与之值相同的格子
- 完成游戏时的简易提示
- 简易的提示和小抄
- 完成某行、列或子方阵时的提示动画
附录
¶下面我实现的一个简易数独，求解数独以及生成数独所需的数据的算法我封装到了 @algorithm.ts/sudoku 中，有兴趣的朋友可以自取。ui 组件打算之后做好整理再开源。
Related
¶