V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
oy9r
V2EX  ›  算法

如何快速的判断(证明)一个数独是否有且仅有唯一解?

  •  
  •   oy9r · 2022-05-22 09:52:49 +08:00 · 1920 次点击
    这是一个创建于 934 天前的主题,其中的信息可能已经有所发展或是发生改变。
    5 条回复    2023-07-02 04:42:07 +08:00
    Ultraman
        1
    Ultraman  
       2022-05-22 10:54:33 +08:00 via Android
    ershierdu
        2
    ershierdu  
       2022-05-22 13:59:14 +08:00
    先枚举所有“有且仅有唯一解”的情况,存起来,判断的时候再去查表。
    至于保存的结构,我觉得可以用树,第一层表示第 1 个格子的内容( 0-9 ,或空白),第二层表示第 2 个格子的内容,以此类推,一共有 根节点+81 层。因为大部分的分叉都能被剪枝,所以树应该不会特别大…吧?

    不知道是否可行
    GuuJiang
        3
    GuuJiang  
       2022-05-22 16:22:10 +08:00 via iPhone
    @ershierdu 是不太大,也就 6670903752021072936960 种而已:doge:
    ershierdu
        4
    ershierdu  
       2022-05-23 13:09:33 +08:00
    @GuuJiang #3 那没事了:)
    element90
        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
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2854 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 21ms · UTC 12:43 · PVG 20:43 · LAX 04:43 · JFK 07:43
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.