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 |