Prolog - jigoku求解器 - 運行時間

Question

我是一個Prolog的總新手（如：我只用7種語言在7周內完成了Prolog章節），所以對以下任何代碼的一般評論都非常受歡迎。

首先：什麼是jigoku？這就像一個數獨，除了你得到一個空網格，並且在每個3×3的塊內，給出了相鄰時隙之間的不等式。示例：http://krazydad.com/jigoku/books/KD_Jigoku_CH_8_v18.pdf。您仍然需要填寫網格，以便每行，每列和每個塊包含數字1-9。

我試着實現一個基於這個數獨求解器的求解器：http://programmablelife.blogspot.co.uk/2012/07/prolog-sudoku-solver-explained.html。爲了調試原因，我開始與該作品真的很好一個4x4例如：

:- use_module(library(clpfd)). 

small_jidoku(Rows, RowIneqs, ColIneqs) :- 
    Rows = [A,B,C,D], 
    append(Rows, Vs), Vs ins 1..4, 
    maplist(all_distinct, Rows), 
    transpose(Rows, Columns),  
    maplist(all_distinct, Columns), 
    blocks(A, B), blocks(C,D), 
    maplist(label, Rows), 
    fake_check_ineqs(Rows, RowIneqs), 
    fake_check_ineqs(Columns, ColIneqs), 
    pretty_print([A,B,C,D]).  

blocks([], []).  
blocks([A,B|Bs1], [D,E|Bs2]) :-  
    all_distinct([A,B,D,E]),  
    blocks(Bs1, Bs2). 

fake_check_ineqs([],[]). 
fake_check_ineqs([Head|Tail], [Ineq1|TailIneqs]) :- 
    Head = [A,B,C,D], 
    atom_chars(Ineq1, [X1,X2]), 
    call(X1, A, B), 
    call(X2, C, D), 
    fake_check_ineqs(Tail, TailIneqs). 

pretty_print([]). 
pretty_print([Head | Tail]) :- 
print(Head), 
print('\n'), 
pretty_print(Tail). 

我再解決下面的例子：

time(small_jidoku([[A1,A2,A3,A4],[B1,B2,B3,B4],[C1,C2,C3,C4],[D1,D2,D3,D4]],[><,<>,<<,<<],[><,<<,<>,>>])). 

這運行在大約0.5秒上衣。不過，我也試圖用它來解決它

time(small_jidoku([A,B,C,D],[><,<>,<<,<<],[><,<<,<>,>>])). 

這似乎需要時間。 任何人都可以解釋爲什麼它會花費更長的時間，當我沒有指定每行有4個元素？我的天真答案是，Prolog，如果沒有告訴我的行的實際格式，也會嘗試探索更小/更大的行，從而浪費了時間。長度爲5的行，但這是真的嗎？

我的第二個問題是關於9x9版本，這非常像4x4，除了塊當然更大，並且在檢查不等式時還有更多的測試需要完成。代碼如下：

:- use_module(library(clpfd)). 

jidoku(Rows, RowIneqs, ColIneqs) :- 
    Rows = [A,B,C,D,E,F,G,H,I], 
    append(Rows, Vs), Vs ins 1..9, 
    maplist(all_distinct, Rows), 
    transpose(Rows, Columns),  
    maplist(all_distinct, Columns),   
    blocks(A, B, C), blocks(D, E, F), blocks(G, H, I),  
    maplist(label, Rows), 
    check_ineqs(Rows, RowIneqs), 
    check_ineqs(Columns, ColIneqs), 
    pretty_print([A,B,C,D,E,F,G,H,I]).  

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). 

check_ineqs([],[]). 
check_ineqs([Head|Tail], [Ineq1|TailIneqs]) :- 
    Head = [A,B,C,D,E,F,G,H,I], 
    atom_chars(Ineq1, [X1, X2, X3, X4, X5, X6]), 
    call(X1, A, B), 
    call(X2, B, C), 
    call(X3, D, E), 
    call(X4, E, F), 
    call(X5, G, H), 
    call(X6, H, I), 
    check_ineqs(Tail, TailIneqs). 

測試例如：

time(jidoku([[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]], 
     [<>>><>,<<<>><,<<<><>,<><<><,>>><><,><>><>,<>>><>,<>><><,><<>>>], 
     [<<<><>,><<>>>,<><<><,><<<>>,><><<<,<><><>,<>>>><,><><><,<>><>>])). 

，並沒有達成任何結論，在這一點上這一個已經運行在一夜之間，我完全不知道自己什麼錯誤。我期望一些縮放問題，但不是這個比例！

如果有人真的知道他們在做什麼可以照亮這一點，那將是一件好事！謝謝！

Answer 1

這裏是你的代碼，我腦子裏想的版本（其它謂詞保持不變）：

ineqs(Cells, Ineq) :- 
     atom_chars(Ineq, Cs), 
     maplist(primitive_declarative, Cs, Ds), 
     ineqs_(Ds, Cells). 

ineqs_([], _). 
ineqs_([Op1,Op2|Ops], [A,B,C|Cells]) :- 
     call(Op1, A, B), 
     call(Op2, B, C), 
     ineqs_(Ops, Cells). 

primitive_declarative(<, #<). 
primitive_declarative(>, #>). 

注意，它不會做代碼正義的普遍性調用謂詞「check_...」，因爲謂語陳述什麼持有並能在幾個方向可以使用：是的，它可如果約束抱來檢查，但它可以也用來指出制約必須擱置了一些變量。因此，我避免了使用命令，並使用更多的聲明性名稱。

您在jidoku/3使用ineqs/2有：maplist(ineqs, Rows, RowsIneqs)等

你的榜樣，並與新版本的結果，使用SWI 7.3。2：

?- length(Rows, 9), maplist(same_length(Rows), Rows), 
    time(jidoku(Rows, 
    [<>>><>,<<<>><,<<<><>,<><<><,>>><><,><>><>,<>>><>,<>><><,><<>>>], 
    [<<<><>,><<>>>,<><<><,><<<>>,><><<<,<><><>,<>>>><,><><><,<>><>>])), 
    maplist(writeln, Rows). 
% 2,745,471 inferences, 0.426 CPU in 0.432 seconds (99% CPU, 6442046 Lips) 
[1,5,4,8,7,2,6,9,3] 
[2,3,9,1,6,5,7,4,8] 
[6,7,8,3,9,4,2,5,1] 
[3,4,1,2,5,6,8,7,9] 
[9,6,5,7,1,8,3,2,4] 
[8,2,7,9,4,3,1,6,5] 
[4,9,3,6,2,1,5,8,7] 
[7,8,2,5,3,9,4,1,6] 
[5,1,6,4,8,7,9,3,2] 
Rows = [[1, 5, 4, 8, 7, 2, 6, 9|...], ...]. 

事實上，注意沒有在所有標籤需要計算在這種特殊情況下的獨特的解決方案，因爲約束求解器是強大到足以降低所有域獨居套。

在你之前的版本中，所有的時間都被不必要地浪費在生成排列上，最終被認爲是不一致的。使用新版本，約束求解器有機會早些時候應用這些知識。

因此，建議先聲明所有約束，然後才調用labeling/2來搜索具體解決方案，如CLP(FD) manual中所述。