序言數獨求解問題

Question

我正在嘗試編寫一個數獨9 x 9求解器。我已經使用這個下面的代碼：

:-use_module(library(clpfd)). 
solve(X, Grid):- 

X = [A1, A2, A3, A4, A5, A6, A7, A8, A9, 
    B1, B2, B3, B4, B5, B6, B7, B8, B9, 
    C1, C2, C3, C4, C5, C6, C7, C8, C9, 
    D1, D2, D3, D4, D5, D6, D7, D8, D9, 
    E1, E2, E3, E4, E5, E6, E7, E8, E9, 
    F1, F2, F3, F4, F5, F6, F7, F8, F9, 
    G1, G2, G3, G4, G5, G6, G7, G8, G9, 
    H1, H2, H3, H4, H5, H6, H7, H8, H9, 
    I1, I2, I3, I4, I5, I6, I7, I8, I9], 

member(Grid, X), 

%rows have to be unique and from 1 to 9 
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [A1, A2, A3, A4, A5, A6, A7, A8, A9]), 
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [B1, B2, B3, B4, B5, B6, B7, B8, B9]), 
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [C1, C2, C3, C4, C5, C6, C7, C8, C9]), 
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [D1, D2, D3, D4, D5, D6, D7, D8, D9]), 
    permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [E1, E2, E3, E4, E5, E6, E7, E8, E9]), 
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [F1, F2, F3, F4, F5, F6, F7, F8, F9]), 
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [G1, G2, G3, G4, G5, G6, G7, G8, G9]), 
    permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [H1, H2, H3, H4, H5, H6, H7, H8, H9]), 
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [I1, I2, I3, I4, I5, I6, I7, I8, I9]), 


%coloums have to be unique and from 1 to 9 
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [A1, B1, C1, D1, E1, F1, G1, H1, I1]), 
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [A2, B2, C2, D2, E2, F2, G2, H2, I2]), 
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [A3, B3, C3, D3, E3, F3, G3, H3, I3]), 
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [A4, B4, C4, D4, E4, F4, G4, H4, I4]), 
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [A5, B5, C5, D5, E5, F5, G5, H5, I5]), 
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [A6, B6, C6, D6, E6, F6, G6, H6, I6]), 
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [A7, B7, C7, D7, E7, F7, G7, H7, I7]), 
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [A8, B8, C8, D8, E8, F8, G8, H8, I8]), 
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [A9, B9, C9, D9, E9, F9, G9, H9, I9]), 

%3X3 boxes have to be unique and from 1 to 9 
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [A1, A2, A3, B1, B2, B3, C1, C2, C3]), 
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [A4, A5, A6, B4, B5, B6, C4, C5, C6]), 
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [A7, A8, A9, B7, B8, B9, C7, C8, C9]), 
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [D1, D2, D3, E1, E2, E3, F1, F2, F3]), 
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [D4, D5, D6, E4, E5, E6, F4, F5, F6]), 
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [D7, D8, D9, E7, E8, E9, F7, F8, F9]), 
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [G1, G2, G3, H1, H2, H3, I1, I2, I3]), 
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [G4, G5, G6, H4, H5, H6, I4, I5, I6]), 
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [G7, G8, G9, H7, H8, H9, I7, I8, I9]). 

然而，當我運行查詢：

solve(X,[_,7,2,4,_,_,_,_,1,_,8,_,7,_,_,3,2,_,6,3,1,_,_,_,7,_,_,_,_,_,5,2,_,_,1,4,_,_,5,9,_,4,6,_,_,8,4,_,_,3,7,_,_,_,_,_,9,_,_,_,2,5,3,_,6,8,_,_,5,_,7,_,2,_,_,_,_,9,4,6,_]）。

該程序只是掛起。任何人都可以看到我犯了什麼錯誤嗎？謝謝。

編輯：是否注意到了錯誤的查詢，但是程序仍修復

Answer 1

之後掛機運行獨立的排列是一個非常繁重的計算。打開您的系統監視器，並查看CPU使用率級別。 100％？

每個獨立呼叫permutation/2工作分離。我們應該首先創建結構來保存我們的結果 - 列表 - 與共享變量。然後，排列將在共享結構上工作，並且重複將很早被拒絕，從而簡化了計算。

sudoku(Rows):- 
    Rows = [ [A1,B1,C1,D1,E1,F1,G1, ...], 
      [A2,B2,C2,D2,E2,F2,G2, ...], 
      [A3,B3,C3,D3,E3,F3,G3, ...] ...], 
    Cmns = [ [A1,A2,A3 ...], 
      [B1,B2,B3 ...] ...], 
    Boxs = [ [A1,B1,C1,A2,B2,C2,A3,B3,C3], 
      [D1,E1,F1,D2,E2,F2,D3,E3,F3] ...], 
    findall(X, between(1,9,X), L), 
    Rows = [R1,R2,R3 ...], 
    Cmns = [K1,K2,K3 ...], 
    Boxs = [X1,X2,X3 ...], 
    maplist(permutation(L), [R1,X1,R2,X2,K1,R3,X3,K2, ...]). 

這會快得多，因爲失敗的排列在流程的早期被駁回。

---

編輯：不，它似乎沒有太大的幫助。獨立permutation的開銷太高。這需要更加細化。使用permute代替permutation，

selecting([], S, S). 
selecting([A|B], S, R):- select(A,S,S2), selecting(B,S2,R). 

permute(L,X):- partition(var, X, Vs, Ns), 
    selecting(Ns,L,L2), permutation(L2,Vs). 

似乎幫助一點點，但數量不多。我現在可以比較容易地得到maplist(permute(L), [X1,X2,R1,R2,R3,X3,K1,K2,K3,X4,R4,K4,X5,X6])，但是加入R5加倍運行時間，並且在進一步加入K5之後它不會在7倍時間內完成。

Answer 2

Permute往往是一個昂貴的操作，CLPFD實際上有一些其他操作是完美的數獨解決。請注意，CLPFD代表約束限制通過有限域編程。 CLPFD旨在讓您寫下有關很多變量領域的事實，然後嘗試一次性解決所有這些問題。

這與您所寫的內容相反，其中每個permutation實際上都是一個獨立的命令性陳述。這意味着它找到了第一行，然後是第二行......的解決方案，直到它最終到達失敗的列，並且在嘗試不同的組合之前必須進行大量的回溯和重試，僅用於第一行 ...然後它將嘗試所有已經失敗的行的組合。我想你可以很快看到它變得非常昂貴。

就像我說的，CLPFD比這更聰明。您可以將大量鬆散域約束語句應用於您的變量，然後嘗試使用label同時解決所有這些問題。這是懶惰評估的縮影。要編寫類似於使用置換的方法，您需要命令in/ins和all_different。

1. in/ins：這使您可以將數字域變量（在單變量，對插件列表）。X ins 1..9告訴CLPFD X的所有成員必須具有介於1和9之間的值。
2. all_different：約束給定列表中每個元素的域，使其不等於給定列表的所有其他元素。基本上，列表中的每個元素都有所不同。

（第三次我說這個，但它仍然非常重要）這些操作都沒有告訴解釋器做任何形式的花哨/現場計算。他們只是告訴CLPFD把關於變量約束的一些事實放入約束存儲器中，並將其保存在那裏，直到最後要求答案。

對於數獨，你想：

1. 應用X插件1..9
2. 爲每位列，行和方形的清單，並申請all_different每個。
3. 使用標籤（X）告訴CLPFD停止這麼神祕的懶惰，並開始嘗試將值應用於變量。這最後一步是非常排列的，只有它在整個數獨板上纔會完成，並在排列時考慮所有的約束條件。更簡單的說，它意味着'解決'。

我已經在過去寫的同一個程序，所以你可以尋求我如何使用ins，all_different和labelhere。雖然我會問你自己實施之前是否確定瞭解使用情況。

爲了更好地理解CLPFD是如何應用所有那些整齊的約束條件併爲它們解決的，我建議使用wikibook。