使用 Python 解開數獨
不知道從什麼時候開始
我就很喜歡數獨這個遊戲形式
它很美
如何決定一個唯一解的原因更是神祕的讓人著迷
所以大學時代我就有寫過數獨的程式
更是我在 github 上面第一個上傳的題目
而我又情不自禁地用我最喜歡的 Python 重寫了一次
與之前不同的是，更簡潔的寫法
並建立了兩種基本演算法
就可以將世界上最難的數獨題目壓到 0.2 秒內解決
https://www.newtalk.tw/news/view/2012-06-30/26670
有些中等以下的題目甚至不需要進入遞迴搜尋
計時 0.0 秒解完
相關名詞
在這裡稍微解釋一下，等等演算法會用到的名詞
遞迴
遞迴（英語：recursion）在電腦科學中是指一種通過重複將問題分解為同類的子問題而解決問題的方法
- 維基百科
候選數
候選數是指在某一格中，在規則內可能可以填入的數字
演算法
以下測試使用世界最難題目下去測試
https://newtalk.tw/news/view/2012-06-30/26670
紀錄一下演算法之間的差異
如何選擇格子
演算法 0 挑選第一個遇到空的格子遞迴
34.29 秒
36.01 秒
演算法 1 挑選候選數字最少的格子遞迴
16.85 秒
16.53 秒
所以我們可以很明顯的得到一個結論
挑選候選數字最少(分支度最少)的格子可以有效降低計算時間
因為這樣挑中正確答案機率最大
如何選擇候選數
這裡的測試都加上了挑選候選數字最少的演算法
演算法 3 尋找唯一可能性的格子並指定為該格答案
3.51 秒
3.29 秒
演算法 4 尋找某個候選數字只有在某行或某列或某個九宮格中出現過一次
0.45 秒
0.48 秒
3 + 4
0.37 秒
0.35 秒
0.35 秒
看起來大部分找到數字的工作給 4 號演算法做完了
如果你對更多數獨演算法有興趣可以參考
https://www.easyatm.com.tw/wiki/%E6%95%B8%E7%8D%A8%E6%8A%80%E5%B7%A7
程式碼
https://github.com/PttCodingMan/PracticeProgram/tree/master/Sudoku