I tried writing a binary sudoku solver in swi-prolog. (a binary sudoku is explained here)
The problem is that I am now running out of global stack. I am giving it 2 gb which should be more than enough. Am I using a flawed algorithm? Is there something I could be doing better to avoid running in to the lack of global stack error with such small puzzles?
A bit more information : I am already running out of stack on 4X4 puzzles which have with the first constraint applied only 6^4 possibilities. You can query this problem with :
problems(2,Field),binary_sudoku(Field).
code here :
:-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,[[_,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]]).
all_diff
instead of usingall_different/1
orall_distinct/1
already available? Why are you not setting the "all different" constraint earlier?