數獨在序言太長解決

Question

我在想，如果有使用切割符號序言解決9x9的數獨
拼圖中的快捷方式的好辦法。我目前正在解決這個難題，而不使用！符號，但它是
花費太長時間。
有什麼建議嗎？

Answer 1

沒有看到代碼，沒有人可以真正幫助你，但這裏有一些通用的建議，你可能會發現有用的。

Prolog程序通過搜索解決方案空間來工作。大多數情況下，您將遵循生成和測試範例。讓我們對Prolog感興趣的性感示例代碼通常是性感和令人興奮的，因爲它們花費的時間太少。事實上，Prolog的表現就像市場營銷一樣。創造更好的潛在客戶價值不僅僅是加速其他過程。這是切入點。

減少了很多，比你想象的要少。這是只有有用，如果你知道你的第一個解決方案是一樣好或比其他更好。它承諾你第一次猜測。

在像Sudoku這樣的問題中，天真地生成比您需要的更多解決方案非常容易。如果你只是選擇一個數字，你會爲3x3網格生成9^9個可能的解決方案，但是你已經知道一個序列，如[9,9,9,9,9,9,9,9,9]對你沒用。你用這種方法生成的大多數解決方案都是毫無價值的。所以最好只是要求[1,2,3,4,5,6,7,8,9]的排列組合更好三個數量級！但事實證明，與數獨相比，你可以做得更好，因爲你不會想要超過9的同一行中的9或1的數目。

有鑑於此，應該清楚的是， 「只是使用切割」的一般想法有點像把小孩手術刀或者要求外科醫生用一個雕刻感恩節火雞。這可能是一個偉大的工具，但不是在錯誤的手中或錯誤的工作。因爲它對你有什麼好處，所以你首先必須瞭解一些關於你產生潛在解決方案的順序。如果你沒有按照正確的順序生成它們，這會傷害你。這就像營銷。你需要高素質的線索，但如果你把所有的錢都扔在錯誤的昂貴線索上，你就會死在水中。

通常，如果您通過Prolog程序進行追蹤，您可以看到爲什麼它浪費時間無效地生成事物。如果你想到自己，「它應該已經放棄了！」那麼你確切知道在哪裏放置剪輯。更可能的是，你會想「爲什麼你這麼愚蠢，在這之前嘗試那個？」如果你發現自己在想這些，那麼你的想法就會形式化。回過頭來寫一個更智能的生成器，你的代碼性能將會顯着提高。

從我個人的經驗軼事。一位朋友的兒子試圖擊敗一些網絡遊戲。爲此，他必須解決一系列的問題。這對於冗長的單詞來說非常單調乏味。我編寫了一個使用WordNet作爲數據庫的Prolog程序。我會把這些字母排列，直到我在數據庫中找到一個單詞，然後打印出來。它適用於小寫字母，比如說5個字母，但是它只是7或8個字慢得要命。幾年過去了，突然間我意識到：我可以做一個索引。如果我只是把字典中的所有單詞和字符排序，那麼我就可以對字符串進行排序，對它們進行排序，並查找與索引中匹配的所有單詞。構建索引需要時間，但與執行數十億個置換相比並不算多，我只需要做一次即可快速查找。原來的程序看起來更像我們夢寐以求的Prolog和巫師可以寫的，但第二個程序使我們有可能找到巨大詞彙的字典，並且讀起來並不困難（儘管「聲明式」更少）。這個故事的寓意是，削減永遠不會讓我得到這個實現或一個算法，表現和這個一樣好。算法質量仍然最重要。

Answer 2

考慮使用有限域約束。它們幾乎可用於所有現代Prolog系統，並允許聲明性地描述許多組合問題，包括數獨。

如果您使用有限域約束對此問題建模，則不需要任何!/0，仍然可以獲得非常有效的解決方案。

從SWI-Prolog的的library(clpfd)的文檔：

:- use_module(library(clpfd)). 

sudoku(Rows) :- 
     length(Rows, 9), maplist(length_(9), Rows), 
     append(Rows, Vs), Vs ins 1..9, 
     maplist(all_distinct, Rows), 
     transpose(Rows, Columns), 
     maplist(all_distinct, Columns), 
     Rows = [A,B,C,D,E,F,G,H,I], 
     blocks(A, B, C), blocks(D, E, F), blocks(G, H, I). 

length_(L, Ls) :- length(Ls, L). 

blocks([], [], []). 
blocks([A,B,C|Bs1], [D,E,F|Bs2], [G,H,I|Bs3]) :- 
     all_distinct([A,B,C,D,E,F,G,H,I]), 
     blocks(Bs1, Bs2, Bs3). 

problem(1, [[_,_,_,_,_,_,_,_,_], 
      [_,_,_,_,_,3,_,8,5], 
      [_,_,1,_,2,_,_,_,_], 
      [_,_,_,5,_,7,_,_,_], 
      [_,_,4,_,_,_,1,_,_], 
      [_,9,_,_,_,_,_,_,_], 
      [5,_,_,_,_,_,_,7,3], 
      [_,_,2,_,1,_,_,_,_], 
      [_,_,_,_,4,_,_,_,9]]). 

樣品查詢及其結果：

?- problem(1, Rows), sudoku(Rows), maplist(writeln, Rows). 
[9, 8, 7, 6, 5, 4, 3, 2, 1] 
[2, 4, 6, 1, 7, 3, 9, 8, 5] 
[3, 5, 1, 9, 2, 8, 7, 4, 6] 
[1, 2, 8, 5, 3, 7, 6, 9, 4] 
[6, 3, 4, 8, 9, 2, 1, 5, 7] 
[7, 9, 5, 4, 6, 1, 8, 3, 2] 
[5, 1, 9, 2, 8, 6, 4, 7, 3] 
[4, 7, 2, 3, 1, 9, 5, 6, 8] 
[8, 6, 3, 7, 4, 5, 2, 1, 9]