swi prolog中的二元數獨

作爲一個序言新手，我想嘗試實現一個二元數獨求解器（代碼如下，swi-prolog）。二進制數獨是這裏解釋：https://cstheory.stackexchange.com/questions/16982/how-hard-is-binary-sudoku-puzzle swi prolog中的二元數獨

但是，執行下面的查詢時：

binarySudoku([[1,0],[0,1]]). I get "true." 
binarySudoku([[1,_],[_,_]]). I get "false."

現在很明顯，它不應該是有解決方案返回false ......這是怎麼回事/哪能解決這個問題？

:-use_module(library(clpfd)). 

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

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

allDifferent([]). 
allDifferent([X|Y]) :- 
    not(member(X,Y)), 
    allDifferent(Y). 


invalid(Rows,X,Y) :- 
    AboveY is Y-1, 
    BelowY is Y+1, 
    matrixNth(Rows,X,Y,1), 
    matrixNth(Rows,X,AboveY,1), 
    matrixNth(Rows,X,BelowY,1). 
invalid(Rows,X,Y) :- 
    LeftX is X-1, 
    RightX is X+1, 
    matrixNth(Rows,X,Y,1), 
    matrixNth(Rows,LeftX,Y,1), 
    matrixNth(Rows,RightX,Y,1). 

binarySudoku(Rows) :- 
    length(Rows,Height), 
    transpose(Rows,Cols), 
    length(Cols,Height), 
    maplist(validRow,Rows), 
    foreach(between(1,Height,X),foreach(between(1,Height,Y),not(invalid(Rows,X,Y)))), 
    allDifferent(Rows).

來源

2013-12-09 camel

標籤（行）確實似乎修復它，但爲什麼這樣工作？在clpfd手冊中的數獨求解器的例子中，從來沒有調用標籤（可能隱含在all_distinct中？） – camel

我不會將它稱爲拉丁方形，因爲它不僅具有不同的約束，而且當您轉到更大的寬度時，它甚至不像一個... 此外，在谷歌中輸入「二進制數獨」發現我描述的同樣的難題。 – camel

代替(\+)/1，這是沒有邏輯的聲音在這種情況下，使用純約束dif/2：您的代碼按預期工作的你改變線路not(member(X,Y))到：

maplist(dif(X), Y)

例子查詢（請注意，我也使用a_more_readable_naming_convention替代混合TheCases）：

?- binary_sudoku([[1,A],[B,C]]), label([A,B,C]). 
A = B, B = 0, 
C = 1 ; 
false.

+1使用CLP（FD），非常適合這項任務。

來源

2013-12-09 07:13:46 mat

嘿嘿，你不僅解釋了爲什麼prolog正在這樣做，你還提供了一個修復，使其工作如期:) 我也繼續前進，並沒有改變（無效），以有效。現在，當我給它一個更大的難題（12X12）時，它將耗盡全局堆棧。這是我的簡單算法的限制還是有沒有快速修復，我沒有看到？ – camel

請在新問題中顯示新代碼，因爲這是一個不同的問題。 – mat

swi prolog中的二元數獨

回答

相關問題