如何快速的判断（证明）一个数独是否有且仅有唯一解？

[oy9r]

[Ultraman]

https://www.zhihu.com/question/30772895

[ershierdu]

先枚举所有“有且仅有唯一解”的情况，存起来，判断的时候再去查表。
至于保存的结构，我觉得可以用树，第一层表示第 1 个格子的内容（ 0-9 ，或空白），第二层表示第 2 个格子的内容，以此类推，一共有 根节点+81 层。因为大部分的分叉都能被剪枝，所以树应该不会特别大…吧？

不知道是否可行

[GuuJiang]

@ershierdu 是不太大，也就 6670903752021072936960 种而已:doge:

[ershierdu]

@GuuJiang #3 那没事了：）

[element90]

我解决过你的问题，在对一个 puzzle 进行解题时(solve)一般情况下是不需要考虑数独是否唯一解(one-solution),因为一般情况下提交的 puzzle 如果存在非唯一解,则代表这个 puzzle 存在问题，而解题器的目的仅仅是为了解决计算问题，常规的算法有回溯/DLX：
- 回溯 在处理难度不高的数独时速度是非常快且非常稳定
- DLX 在处理难度要求高的数独会相对于回溯算法有轻微的提升

但上述所表达的都是仅仅针对数独解题(solve), 但一个完整的数独也会考虑题目生成(generate),此时需要保证生成的 puzzle 具备唯一解特性,所以会在上述的回溯的算法基础上加上 "求二次解" 即单纯的 DFS

对于生成的速度来说,一个存在 55 个需填空的 one-solution puzzle ，在 nodejs 下平均 150ms ，而在 go 下普遍在 10ms 内

所以，单纯提供一个数独校验是否唯一解，仅仅就是几毫秒到几十毫秒之间

具体的算法 库/应用 你可以参考:
- sudoku-nodejs -> https://github.com/einsitang/sudoku-nodejs
- sudoku-go -> https://github.com/einsitang/sudoku-go
- sudoku-dart -> https://github.com/einsitang/sudoku-dart
- sudoku-flutter -> https://github.com/einsitang/sudoku-flutter