这是一个创建于 918 天前的主题，其中的信息可能已经有所发展或是发生改变。
 |
1
Ultraman 2022-05-22 10:54:33 +08:00 via Android
|
 |
2
ershierdu 2022-05-22 13:59:14 +08:00
先枚举所有“有且仅有唯一解”的情况，存起来，判断的时候再去查表。
至于保存的结构，我觉得可以用树，第一层表示第 1 个格子的内容（ 0-9 ，或空白），第二层表示第 2 个格子的内容，以此类推，一共有 根节点+81 层。因为大部分的分叉都能被剪枝，所以树应该不会特别大…吧？ 不知道是否可行 |
 |
3
GuuJiang 2022-05-22 16:22:10 +08:00 via iPhone
@ershierdu 是不太大，也就 6670903752021072936960 种而已:doge:
|
 |
5
element90 2023-07-02 04:42:07 +08:00
我解决过你的问题，在对一个 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 |
Select Language