除回溯外,有哪些比較好用且效率高的解數獨演算法?
樓主最近在解數獨,發現除了回溯外還有另一個演算法叫Propagation (Local Consistency)是一個AI類的演算法,由於沒有學過類似的機器學習、所以想請教這個演算法用比較通俗的語言是怎麼樣實現的呢?或者有沒有其他效率高的解數獨演算法?ps樓主用的語言是Haskell
我看 SAT solver 用的 DPLL 演算法就很適合用來解數獨,雖然其實也是一種回溯(逃
用 Haskell 的話,你可以用 sbv 生成一個數獨的約束,然後調 Z3 之類的 SMT solver 求 satisfiability 獲得一個解。或者用 ersatz/picosat 也行,調 cryptominisat 之類的 SAT solver,不過 SAT 沒有 linear arithmetic/bit-vector arithmetic,需要自己寫 bit-blasting 表示整數加法。
補充 @Canto Ostinato 的,用z3 Python API實現。
建模可以用z3的Integer Theory, Bit Vector Theory, Finite Domain Theory等(當然只用Boolean Logic也是可以的)。
#coding: utf-8
from z3 import *
# 9x9 matrix of integer variables
X = [ [ Int("x_%s_%s" % (i+1, j+1)) for j in range(9) ]
for i in range(9) ]
# each cell contains a value in {1, ..., 9}
cells_c = [ And(1 &<= X[i][j], X[i][j] &<= 9)
for i in range(9) for j in range(9) ]
# each row contains a digit at most once
rows_c = [ Distinct(X[i]) for i in range(9) ]
# each column contains a digit at most once
cols_c = [ Distinct([ X[i][j] for i in range(9) ])
for j in range(9) ]
# each 3x3 square contains a digit at most once
sq_c = [ Distinct([ X[3*i0 + i][3*j0 + j]
for i in range(3) for j in range(3) ])
for i0 in range(3) for j0 in range(3) ]
sudoku_c = cells_c + rows_c + cols_c + sq_c
# sudoku instance, we use 0 for empty cells
instance = ((0,0,0,0,9,4,0,3,0),
(0,0,0,5,1,0,0,0,7),
(0,8,9,0,0,0,0,4,0),
(0,0,0,0,0,0,2,0,8),
(0,6,0,2,0,1,0,5,0),
(1,0,2,0,0,0,0,0,0),
(0,7,0,0,0,0,5,2,0),
(9,0,0,0,6,5,0,0,0),
(0,4,0,9,7,0,0,0,0))
instance_c = [ If(instance[i][j] == 0,
True,
X[i][j] == instance[i][j])
for i in range(9) for j in range(9) ]
s = Solver()
s.add(sudoku_c + instance_c)
if s.check() == sat: # the constraints are satisfiable
m = s.model()
r = [ [ m.evaluate(X[i][j]) for j in range(9) ]
for i in range(9) ]
print_matrix(r)
else:
print "failed to solve"
http://norvig.com/sudoku.html
你說的是這樣的constraint propagation么?你說這不算回溯的話,我保留意見。你要說DPLL不是回溯的話,我也保留意見。
參看:人工智慧:一種現代的方法(第3版),用SAT(約束滿足問題)秒解數獨
可以用Dancing Link實現精確覆蓋演算法,比直接搜會快不少
感謝評論區 @TooYoungTooSimp dalao給出的鏈接https://http://arxiv.org/abs/cs/0011047感覺樓主跑偏了。請先把自己一知半解的概念都忘掉吧。我怕你這樣下去早晚會沉迷知乎live的。
dancing link舞蹈鏈
不禁想起poj上的題目,當時還備了個Dancing Links 板子。圍觀大佬回答:)
目前沒有多項式演算法。
題主ANU的吧23333我也在做這個呢
自己做過解數獨的小程序 如果只是為了壓縮時間 我覺得最有效的方式應該是並行化吧 自己做遊戲里「大師級」數獨的時候 最後都不得不人肉回溯
只知道Dancing Links比較快(但是這個也算回溯)。
不太清楚回溯的具體意思,但我可以不用遞歸,直接用一個while循環搞定
推薦閱讀:
※Kotlin 版圖解 Functor、Applicative 與 Monad
※為什麼這段 Haskell 代碼比 C 慢那麼多?
※搭建 Emacs 的 Haskell/Idris 環境教程
※Haskell 的 Typeclass 怎麼理解?
※為什麼haskell里需要monoid?