我准备自己在家做一个数独游戏，主要分二步：
- 生成一个数独游戏
- 认证游戏玩家填写数字正确与否
生成一个数独游戏能够有省力的方法，是直接从数独库中任意选一个（甚至可以直接将空缺都给你挖好）。还可以用暴力行为方式（回溯法），一行一行去填，开展不下去了就回溯到上一步。
形成数独游戏最有效的算法是：跳舞链，事实上跳舞链是一种算法设计，就是为了X 优化算法而引起的，而 X 算法是用于处理一类难题：精准覆盖问题
插个有意思的话，我同学说，东野圭吾的小说集《嫌疑犯 X 的献身》，的凶犯就在那科学研究这种情况，有兴趣的可以顺便看一下，这小说集挺著名的。
精准覆盖问题是一个 NP 彻底难题，NP 难题这个概念我差不多忘光了，得再次看一下
精准覆盖问题
简单的说就是给出一个合集 X，和多个子集合 S，从子集中化挑选出 N 个，他们拼接下去正好（没有多余的原素，例如某一原素发生了两次）相当于合集 X。
X 优化算法
wiki百科的讲解我看不懂，还行 OI-Wiki 上说的充足详尽：X 优化算法
处理精准覆盖问题，简单来说分成以下几种流程：
模型
找出问题模型，模型成一个 01 引流矩阵，每一行代表一个结合，1 意味着包括了结合 X 某个原素（1 位置，是该原素在结合 X 中的地位），0 意味着没包括
优化算法流程
简单化难题（变小引流矩阵，删除不会再要考虑的一部分），递归算法处理子问题。
- 选行：选 1 重复次数最小的一列，随后从列有 1 的行中随便选一行
- 删剪：寻找这一行的有 1 的这些列，除掉这种列，寻找这种列上有 1 的行，除掉这种行
- 现已经得到一个缩小版的引流矩阵，再次之上这类删剪实际操作
- 一次深层检索完毕标示：获得一个空引流矩阵。是不是有解：最后一次删除掉行全部都是 1，则表明难题有解，不然难题难解。总程序结束标示：回朔完全部很有可能分支
这一优化算法非常好的缩小难题经营规模，十分最典型的方法
优化算法含意
每挑选一行，代表了准备用这一行去精准遮盖合集，那样对应的：
- 每排仅用一次，故删掉挑选的那一行
- 这一行中存在的所有元素（每一个 1 意味着一个元素发生），后面都也不用再考虑到，故删掉有关列
- 和它起争执的行（同一列上面有 1，意味着有同样元素，不符精准遮盖），无法列入解中，因此后面都也不用再考虑到，故删掉这种行
之上三步可以确保每一次挑选的行，行之间有不会有反复元素。
完毕标示也很容易理解，最后一次删除掉行，假如全部都是 1，则意味着我们所有列都恰好弥补上原素。
这样大家就做到了极致全面覆盖 精准遮盖，这两项规定。
算法的实际完成
实际代码编写，也有一些细节不太清楚，参考文献：
- 弹跳的舞蹈家，跳舞链（Dancing Links）优化算法——求得精准覆盖问题
通过二天的设计与艰辛调节，自己完成了一份 TypeScript 所写的编码：
github.com/liuqinh2s/A…
与上面那个完成不一样，我这个完成不仅有列头，还有排头，总之如何便捷如何来。
数独游戏如何转化为精准覆盖问题
参考文献：zhuanlan.zhihu.com/p/67447747
在网络上查看了很多材料，但一开始看不明白，且发现她说的大部分一模一样（天下文章一大抄），就和前边跳舞链一样，连配图图片都是一样的。
如何把数独游戏这一引流矩阵转化为精准覆盖问题的 01 引流矩阵，本身就是要想好，行和列的含义是什么？
行实际意义
精准遮盖根本矛盾要素是：一个合集 X，多个子集合 S
那样我们先来想一想合集是啥？
合集一定是一幅完整的正确数独游戏回答
那每一个子集合是啥？
子集合应当是单独格子解，最后我们拿正好 81 个子集合，凑成合集。
每一个方格有 9 种填法，81 个方格有 729 种填法，所以我们需要从 729 身高集中化选 81 个出去。
列实际意义
最先思考一下要往一个数独游戏的格子里填写一个数字受什么样的条件管束：
最先，这一格子里不能出现数据，即为空
次之，同一行不可以有同样数据
再度，同一列不可以有同样数据
最终，同一个九宫格不可以有同样数据
每一个方格都是有 4 个管束，81 个方格有 324 个管束，因此有 324 列，具体每一列的内涵如下所示：
第 0 列表明数独游戏（0,0）部位是否存在数据
第 1 列表明（0,1）部位是否存在数据
……
第 8 列表明（0,8）是否存在数据
第 9 列表明（1,0）是否存在数据
……
第 80 列表明（8,8）是否存在数据
之上 81 列表明数独游戏的格子里是不是有数字的约束，然后
81 列表明第 0 行是否存在数据 1
82 列表明第 0 行是否存在数据 2
……
89 列表明第 0 行是否存在数据 9
90 列表明第 1 行是否存在数据 1
91 列表明第 1 行是否存在数据 2
……
161 列表明第 8 行是否存在数据 9
以上为行约束
162 列表明第 0 列是否存在数据 1
……
242 列表明第 8 列是否存在数据 9
最终，是九宫格的约束：
243 列表明第 0 个九宫格是否存在数据 1
244 列表明第 0 个九宫格是否存在数据 2
……
323 列表明第 8 个九宫格是否存在数据 9
实际事例
大家拿 4*4 的数独游戏做事例（仅用到 1 到 4 四个数，可以算是 2 级别独吧，比我们喜欢玩的三阶数独游戏小一阶）：
0 4 0 0
0 0 0 0
0 0 0 0
0 0 0 0
这张图转换成精准覆盖问题的引流矩阵是什么样子的呢？
第二个格子里填了数，别的没填 | 第一行填了数据4 | 第2列填了数据4 | 第1个4宫格填了数据4
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 | 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
上边用|划分了四个地区，每个区域的内涵都详细介绍了
从以上 01 行也可以直接发布数独游戏图，它们都是互相上线的！
当然你也可以用复合型数独游戏图，发布复合型行，可是复合型行可能不能发布单独实际数独游戏图，因为存在一对多的是状况，一个很典型的例子便是全 1 的行，对应着抽象的数独游戏解，而数独游戏解是有 N 个的。
数独游戏的所有解一共有多少个？
数独游戏的总体数量是这样得出的。9!×722×27× 27,704,267,971=6,670,903,752,021,072,936,960（大约是 6.67×10 的 21 三次方）种组成，2005 年于 Bertram Felgenhauer 和 Frazer Jarvis 算出该数据，如果把反复（如数据互换、对称性等）不计算，这样有 5,472,730,538 个组成。那样有意思的来啦，有一个 9!=362880，这个我相当于 9 的全排列，是否可以从这里出发做突破点呢？如果我可以随机事件形成 362880 个完整的数独游戏引流矩阵，随后随机事件每排挖去 4 到 5 个那便是
362880/24/120*9*362880=411505920个，这个数够大伙儿此生玩儿了。--摘录自数独游戏-- 一个高效化形成数独游戏的算法 真实有效尚需进一步考察
数独游戏求得
随意给出一个数独游戏图，其实就是等同于提出了跳舞链里的一行，就以这一行为通道，即可开始精准覆盖问题的求得，解空间是 729，相对应的 01 引流矩阵尺寸是：729*324，但是好在是一个稀疏矩阵。
有一个提升务必说起一下：每一次选行情况下，选 1 最小的列里的某一行。
选 1 最小的列意义是：探寻出现在了全部子集中化频次最小的原素，即然大家都非常缺这一原素，那样大部分代表着凑全结合，非常需要这一原素，那就要首先选择这些元素
不加这一改善的情况下，我回朔一直在搞排列与组合，无头苍蝇，溜了 60 多万元次 dance 也没结论（数分钟都过去了），添加了这一提升原地起飞，1 秒左右不到就解出来了。
我数独游戏求得编码：github.com/liuqinh2s/A…
可以直接用浏览器上跑的代码：github.com/liuqinh2s/A…
数独游戏形成
之上只说了怎样解数独，我们该如何形成数独游戏呢：数独游戏的生成全过程是怎么样的？ - 单想得回应 - 知乎问答
简单的说就是：任意放进 11 数量，求得出终盘，随后挖地洞。