使用 Python 解開數獨

Posted on 2022-01-29

分享使用 Python 開發數獨解題程式的經驗。本文探討如何運用候選數與遞迴搜尋等演算法優化效能，並比較不同策略對計算時間的影響，最終實現能在 0.2 秒內解開世界最難題目的高效能解法，並提供完整程式碼參考。

不知道從什麼時候開始
我就很喜歡數獨這個遊戲形式

它很美

如何決定一個唯一解的原因更是神祕的讓人著迷

所以大學時代我就有寫過數獨的程式
更是我在 github 上面第一個上傳的題目

而我又情不自禁地用我最喜歡的 Python 重寫了一次

與之前不同的是，更簡潔的寫法
整體策略可以歸納成兩件事：約束傳播（constraint propagation）與回溯搜尋（backtracking）

就可以將世界上最難的數獨題目壓到 0.05 秒內解決
https://www.newtalk.tw/news/view/2012-06-30/26670

有些中等以下的題目甚至不需要進入遞迴搜尋
計時 0.0 秒解完

演算法

以下測試使用世界最難題目下去測試
https://newtalk.tw/news/view/2012-06-30/26670

紀錄一下演算法之間的差異

演算法 0 挑選第一個遇到的空格遞迴

0.42 秒
0.43 秒

演算法 1 挑選候選數字最少的格子遞迴
（這就是常見的 MRV，Minimum Remaining Values 啟發式，挑分支度最小的格子）

0.26 秒
0.26 秒

所以我們可以很明顯的得到一個結論
挑選候選數字最少(分支度最少)的格子可以有效降低計算時間

因為這樣挑中正確答案機率最大

下面兩種其實就是約束傳播裡最基本的兩個推理規則
這裡的測試都已經加上了前面的 MRV 選格策略

演算法 3 唯一候選數（Naked Single）
某一格在規則內只剩一個候選數字，那它就只能是這個數字

0.09 秒
0.09 秒

演算法 4 隱性單一候選（Hidden Single）
某個候選數字在某一行、某一列或某個九宮格中只出現在唯一一格，那這格就只能填它

0.04 秒
0.04 秒

3 + 4（兩個推理規則一起跑）

0.03 秒
0.03 秒
0.03 秒

看起來大部分找到數字的工作都被 Hidden Single 做完了
而真正進入遞迴猜測的次數，也因為前面的約束傳播被壓到很低

把同一題（世界最難）重複跑 100 次取平均，各策略的差異就更清楚了

每加一層策略就快一個檔次：MRV 快約 1.6 倍、再加 Naked Single 快約 3 倍、改用 Hidden Single 又快一倍，兩者合一最快

如果你對更多數獨演算法有興趣可以參考
https://www.easyatm.com.tw/wiki/數獨技巧

最新版本把程式拆成幾個模組：cell.py（單一格子）、line.py（行與列）、jiugongge.py（九宮格），核心解題邏輯在 sudoku.py，並補上了 test_sudoku.py 測試

回溯的部分也做了優化：每次猜測前用 _snapshot() 只保存各格的值與候選清單，猜錯時用 _restore() 還原，不必對整個物件做深拷貝，回溯成本因此低很多

https://github.com/PttCodingMan/PracticeProgram/tree/master/Sudoku