Я пробовал писать двоичный решатель sudoku в swi-prolog. (объясняется двоичный файл sudoku here)proog sudoku solver закончился из глобального стека
Проблема в том, что я теперь исчерпал глобальный стек. Я даю ему 2 ГБ, которого должно быть более чем достаточно. Использую ли я испорченный алгоритм? Есть ли что-то, что я мог бы сделать лучше, чтобы избежать столкновения с отсутствием глобальной ошибки стека с такими маленькими головоломками?
Немного больше информации: Я уже исчерпал стек на головоломках 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,[[_,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]]).
Как вы запрашивая для решения? Почему вы определяете свой собственный 'all_diff' вместо того, чтобы использовать' all_different/1' или 'all_distinct/1' уже имеющиеся? Почему вы не устанавливаете «все разные» ограничения раньше? –
Я должен был добавить, что это первое, что я когда-либо делал в прологе, и все для меня кажется неуклюжим/волшебным, исходящим из C .... all_distinct не работал, потому что он ограничивает целые числа разными, в то время как я хочу списки от целых чисел. Независимо от того, что all_diff не является проблемой, очень мало решений с неповторимыми строками/столбцами. Насколько я могу судить, проблема с моей двойной петлей foreach. – camel
Итак, вы получаете решение на плате 2x2? Как вы запрашиваете его? –