我尝试在swi-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,[[_,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]]).