prolog數獨求解器耗盡全局堆棧

我嘗試在swi-prolog中編寫一個二進制數獨求解器。（二進制數獨解釋爲here）prolog數獨求解器耗盡全局堆棧

問題是我現在用完了全局堆棧。我給它2 GB應該是綽綽有餘。我是否使用有缺陷的算法？有沒有什麼我可以做得更好，以避免遇到這樣的小拼圖缺乏全球堆棧錯誤？

更多信息：我已經在4X4拼圖上用完了，第一個約束只應用了6^4種可能性。你可以查詢這個問題：

problems(2,Field),binary_sudoku(Field).

代碼在這裏：

:-use_module(library(clpfd)). 

valid_row(Row) :- 
    Row ins 0..1, 
    length(Row,L), 
    sum(Row,#=,L/2). 

matrixNth1(Matr,X,Y,El) :- 
    nth1(Y,Matr,CurRow), 
    nth1(X,CurRow,El). 

all_diff([]). 
all_diff([X|Y]) :- 
    maplist(dif(X),Y), 
    all_diff(Y). 


valid(_,1,1). 
valid(Rows,1,Y) :- 
    length(Rows,Y). 
valid(Rows,X,1) :- 
    length(Rows,X). 
valid(Rows,X,X) :- 
    length(Rows,X). 

valid(Rows,X,Y) :- 
    matrixNth1(Rows,X,Y,0). 
valid(Rows,X,Y):- 
    AboveY is Y-1, 
    matrixNth1(Rows,X,AboveY,0). 
valid(Rows,X,Y):- 
    BelowY is Y+1, 
    matrixNth1(Rows,X,BelowY,0). 
valid(Rows,X,Y):- 
    LeftX is X-1, 
    matrixNth1(Rows,LeftX,Y,0). 
valid(Rows,X,Y):- 
    RightX is X+1, 
    matrixNth1(Rows,RightX,Y,0). 

binary_sudoku(Rows) :- 
    length(Rows,Height), 
    transpose(Rows,Cols), 
    length(Cols,Height), 
    maplist(valid_row,Rows), 
    foreach(between(1,Height,X),foreach(between(1,Height,Y),valid(Rows,X,Y))), 
    all_diff(Rows),all_diff(Cols). 


problems(1,[[_,_],[_,_]]). 

problems(2,[[_,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]]).

來源

2013-12-09 camel

你是如何查詢的解決方案嗎？你爲什麼定義自己的'all_diff'而不是使用'all_different/1'或'all_distinct/1'已經可用？爲什麼你不提前設置「全部不同」限制？ – 2013-12-10 06:03:03

我應該補充說，這是我在序言中第一次做的，對我來說，所有對我來說似乎都很笨重/神奇...... all_distinct沒有工作，因爲它限制整數不同，而我想要列表整數是不同的。無論如何，all_diff在這裏並不是問題，對於非唯一行/列的解決方案非常少。就我所知，它對我的雙foreach循環有一個問題。 – camel

那麼你在2x2電路板上有解決方案嗎？你如何查詢獲得它？ – 2013-12-10 09:41:38

有幾個與你的代碼的問題。如果你真的是一個Prolog/clpfd初學者，你可以考慮從容易的事情開始。

CLP程序的想法是首先設置約束（這是確定性的），然後搜索解決方案（這是非確定性的）。在你的代碼中，valid_row/1和all_diff/1可以被認爲是約束條件，但valid/3是不確定的，並且有很多選擇。

所以你應該做的第一個改變是把你的電話轉到有效/ 3到最後。

然後，您應該更改有效/ 3，以便系統地枚舉所有可能的變量賦值。根據您當前的代碼和3x3矩陣，即

foreach(between(1,Height,X),foreach(between(1,Height,Y),valid(Rows,X,Y)))

產生最初的幾個解決方案

[[A, 0, C], [0, 0, 0], [G, 0, I]] 
[[A, 0, C], [0, 0, 0], [G, 0, 0]] 
[[A, 0, C], [0, 0, 0], [G, 0, I]] 
[[A, 0, C], [0, 0, 0], [G, 0, I]] 
[[A, 0, 0], [0, 0, F], [G, 0, I]] 
...

這是不好的，因爲他們仍然包含變量，他們甚至不互相排斥。這兩者都意味着你一次又一次地訪問相同的作業。重寫它，以便每次成功時，所有變量都設置爲0/1，並且所有解決方案都不相同。然後您將只能遍歷搜索空間一次，並且您可能有機會在合理的時間內找到解決方案。

來源

2013-12-10 23:33:59 jschimpf

所以在序言中，我應該嘗試返回離散的解決方案，而不是變量之間的關係？ – camel

據我所知，有效/ 3不建立變量之間的任何關係。它由幾個可選的子句組成，它們都實例化了不同的變量。它應該做的是將一個變量實例化爲其所有可能的值。 – jschimpf

下面是ECLiPSe（帶有約束和建模擴展的Prolog，http://eclipseclp.org）中的緊湊解決方案。它對每行/列的0/1數量使用sum-constraints，對於no-three-1s條件使用序列/ 4約束，並使用lex_ne/2來強制行之間的差異。解決方案搜索通過最終的標記/ 1調用完成。此外，還使用了Matrix-notation，這比在這些設置中的列表更方便。

:- lib(gfd). 

solve(Name, Mat) :- 
    problem(Name, Mat), 
    dim(Mat, [N,N]), 
    Mat #:: 0..1, 
    N #= 2*K, 
    (for(I,1,N), param(Mat,K,N) do 
     sum(Mat[I,1..N]) #= K, 
     sum(Mat[1..N,I]) #= K, 
     sequence(1, 2, 3, Mat[I,1..N]), 
     sequence(1, 2, 3, Mat[1..N,I]), 
     (for(J,I+1,N), param(Mat,I,N) do 
      lex_ne(Mat[I,1..N], Mat[J,1..N]), 
      lex_ne(Mat[1..N,I], Mat[1..N,J]) 
     ) 
    ), 
    labeling(Mat). 

problem(2, [](
    [](_,1,0,_,_,_,_,0,_,_,0,_), 
    [](_,1,1,_,_,1,_,_,_,_,_,_), 
    [](_,_,_,_,_,_,_,_,1,_,_,0), 
    [](_,_,0,0,_,_,_,_,_,_,_,0), 
    [](_,_,_,_,_,_,1,1,_,0,_,_), 
    [](_,1,_,0,_,1,1,_,_,_,1,_), 
    [](_,_,_,_,_,_,_,_,1,_,_,_), 
    [](1,_,_,1,_,_,_,_,_,_,0,_), 
    [](_,1,_,_,_,_,_,_,0,_,_,_), 
    [](_,_,_,_,_,_,_,0,_,_,_,_), 
    [](1,_,_,_,_,_,_,_,_,_,_,1), 
    [](_,1,_,1,_,_,_,_,_,0,0,_))).

這很快帶來了（唯一的）解決方案：

?- solve(2, M). 
M = []([](1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0), 
     [](0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1), 
     [](1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0), 
     [](1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0), 
     [](0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1), 
     [](0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0), 
     [](1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1), 
     [](1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1), 
     [](0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0), 
     [](0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0), 
     [](1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1), 
     [](0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1)) 
Yes (0.03s cpu, solution 1, maybe more)

來源

2013-12-10 23:45:17 jschimpf

prolog數獨求解器耗盡全局堆棧

回答

相關問題