Решатель судоку пролога исчерпывает глобальный стек

Я пробовал написать бинарный решатель судоку в swi-prolog. (бинарный судоку объясняется здесь)

Проблема в том, что у меня заканчивается глобальный стек. Я даю ему 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,[[_,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]]).

sudoku prolog clpfd swi-prolog
person camel    schedule 09.12.2013    source источник
comment
Как вы ищите решение? Почему вы определяете свой собственный all_diff вместо использования уже имеющихся all_different/1 или all_distinct/1? Почему вы не устанавливаете все ограничения раньше?   -  person    schedule 10.12.2013
comment
Я должен был добавить, что это первое, что я когда-либо делал в прологе, и мне все кажется неуклюжим / волшебным, исходящим от C .... all_distinct не работал, потому что он ограничивает целые числа, чтобы они были разными, в то время как я хочу, чтобы списки целых чисел были будь другим. Тем не менее, all_diff здесь не проблема, есть очень мало решений с неуникальными строками / столбцами. Насколько я могу судить, у него проблема с моим двойным циклом foreach.   -  person camel    schedule 10.12.2013
comment
Так получается решение на плате 2х2? Как сделать запрос, чтобы получить его?   -  person    schedule 10.12.2013
comment
да, извините, забыл добавить. задачи (1, Поле), binary_sudoku (Поле), список карт (Writeln, Поле). дает (пару раз) правильное решение. задачи (2, Поле), binary_sudoku (Поле), список карт (Writeln, Поле). не   -  person camel    schedule 10.12.2013

Ответы (2)


arrow_upward
3
arrow_downward

Есть пара проблем с вашим кодом. Если вы действительно новичок в Prolog / clpfd, вы можете подумать о том, чтобы начать с чего-то более простого.

Идея программ CLP состоит в том, чтобы сначала установить ограничения (которые являются детерминированными), а затем выполнить поиск решений (который не является детерминированным). В вашем коде valid_row / 1 и all_diff / 1 можно рассматривать как ограничения, но valid / 3 недетерминирован и делает множество вариантов.

Итак, первое изменение, которое вы должны сделать, - это переместить ваш вызов на valid / 3 в самый конец.

Затем вы должны изменить valid / 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, а все решения были разными. Тогда вы обязательно пройдете поисковое пространство только один раз, и у вас будет шанс найти решение в разумные сроки.

person jschimpf    schedule 10.12.2013
comment
Значит, в прологе я должен попытаться вернуть дискретные решения вместо отношений между переменными? - person camel; 11.12.2013
comment
Насколько я могу судить, valid / 3 не устанавливает никаких отношений между переменными. Он состоит из нескольких альтернативных предложений, каждый из которых создает экземпляры разных переменных. Что ему лучше сделать, так это создать экземпляр одной переменной со всеми ее возможными значениями. - person jschimpf; 12.12.2013

arrow_upward
5
arrow_downward

Вот компактное решение в ECLiPSe (Пролог с ограничениями и расширениями моделирования, http://eclipseclp.org). Он использует ограничения суммы для количества 0/1 на строку / столбец, ограничения последовательности / 4 для условия no-three-1 и lex_ne / 2 для обеспечения различия между строками. Поиск решения осуществляется с помощью вызова labeling / 1 в конце. Также используется матричная нотация, что в таких настройках удобнее списков.

:- 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)
person jschimpf    schedule 10.12.2013