先附上維基說明( 懶 OuO )
Exact cover
(精確覆蓋問題)
Knuth's Algorithm X
Dancing Links
(舞蹈鏈)
這個演算法應該是解數獨最快的 吧
我錯了，好像還有更快的QAQ
我覺得算是以空間換取時間
中心思想就是把數獨轉成精確覆蓋問題
怎麼轉?
首先有四個約束條件(跟線性規劃有點像)
1.每個格子只能填一個數字
2.每行每個數字只能填一遍
3.每列每個數字只能填一遍
4.每宫每個數字只能填一遍
各自都對應的81大行到DLX的表格中
翻譯一下
1.-->在哪格填入數字(0,0)~(8,8)共81大行
2.-->在哪一列填入數字幾，共9X9=81大行
3.-->在哪一行填入數字幾，共9X9=81大行
4.-->在哪一九宮格填入數字幾，共9X9=81大行
填入範例:
因為(0,0)是8
所以會有四個 1 出現在第 0 大列
1.-->在第 0 大列的第 0 個(第 1大行)填 1 (代表在(0,0)這個地方填了數字)
2.-->在第 0 大列的第 81+0+8個(第 89 大行)填 1 (代表在數獨的第一列填了 8 )
3.-->在第 0 大列的第162+0+8個(第 170 大行)填 1 (代表在數獨的第一行填了 8 )
4.-->在第 0 大列的第 243+0+8個(第 251 大行)填 1 (代表在第一個九宮格填了 8 )
紀錄有點簡陋請見諒
真的有空會來補充QAQ
可以去看參考資料的介紹，我覺得都不錯
我有嘗試要用 Excel 填看看，不過真的是太大了，就放棄了OuO
再來就是用 Dancing Links 求出精確覆蓋問題的解了
一樣
程式碼就不說明了
範例程式可在简单易懂的Dancing links讲解（4）得到
實際實作就連到我的Github囉 ( 自己的作業自己寫OuO )
README有說明一下要怎麼使用
不是直接編譯 Sudoku.cpp就可以喔!!!!
怎麼編譯就請看Makefile裡的東西吧
超不負責記錄●完
連後面都是複製貼上OuO
不過Github是連到不同的 repository 喔
參考資料:
简单易懂的Dancing links讲解（4）
算法实践——舞蹈链（Dancing Links）算法求解数独
跳跃的舞者，舞蹈链（Dancing Links）算法——求解精确覆盖问题
DLX精确覆盖解数独问题
沒有留言:
張貼留言