Решение 8 королев, использующее пространственный граф состояний в Прологе, не работает

Я изучаю Пролог по книге Ивана Братко: Программирование для искусственного интеллекта, и в книге я нашел эту версию задачи 8 Queens, в которой для решения этой проблемы используется "граф состояний пространства":

s(Queens, [Queen|Queens]) :- member(Queen, [1,2,3,4,5,6,7,8]),
                             noattack(Queen, Queens).

goal([_,_,_,_,_,_,_,_]).

noattack(_,[],_).

noattack(Y,[Y1|Ylist],Xdist) :-
                                  Y1-Y =\= Xdist,
                      Y-Y1 =\= Xdist,
                                  Dist1 is Xdist + 1,
                                  noattack(Y,Ylist,Dist1).

solve(N,[N]) :- goal(N).

solve(N, [N|Sol1]) :- s(N,N1),
                      solve(N1,Sol1).

Он сочетает в себе решение задачи 8 Queens, основанное на перестановке (используйте его отношение noattack / 3) и предикат s / 2, который, как мне кажется, создает состояние возможных состояний-преемников ( узлы моего графа). Так что у меня что-то вроде:

s (ActualState, SuccessorState)

Я думаю, что предикат цель / 1 указывает только на то, что я должен поставить ровно 8 ферзей.

В книге я скажу, что при выполнении этого запроса: resolve ([], Solution) он создаст список позиций на доске с увеличивающимся числом ферзей, и что этот список закончится безопасной конфигурацией восьми королевы.

Но если я попытаюсь выполнить этот запрос, это не сработает, и я получу следующий результат:

?- solve([],Solution).
ERROR: s/2: Undefined procedure: noattack/2
ERROR:   However, there are definitions for:
ERROR:         noattack/3

Потому что, правильно, предикат noattack, вызываемый в строке 2, принимает только 2 параметра, но предикат noattack должен иметь 3 параметра ... в этой книге дано неверное значение. путь и я не знаю, как решить эту проблему ...

Почему? Что мне не хватает?


prolog n-queens
person AndreaNobili    schedule 08.05.2013    source источник
comment
В этой программе есть множество предупреждений во время компиляции, вы уверены, что ввели их правильно? (Я почти уверен, что нет)   -  person    schedule 08.05.2013
comment
Я исправил ошибку TYPO, но теперь у меня есть другие проблемы ... к сожалению, кажется, что решение, данное в книге, неверное или неполное   -  person AndreaNobili    schedule 08.05.2013

Ответы (1)


arrow_upward
3
arrow_downward

несколько ошибок:

s(Queens, [Queen|Queens]) :- member(Queen, [1,2,3,4,5,6,7,8]),
                             noattack(Queen, Queens, 1).

noattack(_,[],_) :- !.
noattack(Y,[Y1|Ylist],Xdist) :-   Y =\= Y1,
                                  Y1-Y =\= Xdist,
                                  Y-Y1 =\= Xdist,
                                  Dist1 is Xdist + 1,
                                  noattack(Y,Ylist,Dist1).

Потом,

18 ?- solve([],_X), last(_X,S).
S = [4, 2, 7, 3, 6, 8, 5, 1] ;
S = [5, 2, 4, 7, 3, 8, 6, 1] ;
S = [3, 5, 2, 8, 6, 4, 7, 1] ;
S = [3, 6, 4, 2, 8, 5, 7, 1] ;
S = [5, 7, 1, 3, 8, 6, 4, 2] ;
S = [4, 6, 8, 3, 1, 7, 5, 2]

и,

25 ?- findall( X, solve([],X), _S), length(_S,N).
N = 92.
person Will Ness    schedule 08.05.2013
comment
Хорошо, спасибо, насколько обычно, ваше вмешательство оказало мне большую помощь (к сожалению, я не смог пройти этот курс в прошлом семестре, потому что я был на работе и иногда изучал только Пролог, мне это было трудно ...) Теперь я постараюсь глубоко понять этот код. А пока у меня к вам только общий вопрос. В предыдущем примере программа, исследуемая DFS, обращается к графу состояний пространства. Каждый узел графа представляет допустимое состояние, поэтому: 1) В этом случае допустимым состоянием является конфигурация с 8 ферзями, при которой нет атаки? - person AndreaNobili; 08.05.2013
comment
2) Я никогда явно не объявлял график, могу ли я увидеть, что он автоматически строится предикатом s / 2, который переводит меня из допустимого состояния в другое действительное состояние с некоторыми ходами? Если вы дадите мне несколько советов, чтобы лучше разобраться в этой ситуации, я буду вам очень признателен :-) Tnx - person AndreaNobili; 08.05.2013
comment
не совсем. обратите внимание, в s(X,Y) Y всегда является элементом списка на 1 длиннее, чем X (также, список). Итак, s/2 представляет собой ход, скажем, игрока, помещающего одну ферзя на шахматную доску, чтобы она не атаковала уже находящихся там ферзей. - person Will Ness; 08.05.2013
comment
s/2 - ход; но мы пробуем новые комбинации через возврат, поэтому предыдущие назначения отменяются (забываются). Вам придется его изменить: найти все возможные ходы в списке - тогда этот список содержит все узлы для исследования. Кстати, это конкретное решение неэффективно - оно пробует всех ферзей от 1 до 8 на каждом ходу. но нам не нужно пробовать те, которые мы уже разместили ранее. Братко развивает это понимание в очень красивом и эффективном решении 4D, несколькими страницами позже IIRC. - person Will Ness; 08.05.2013
comment
и последнее состояние после последнего хода - это решение. (поэтому пришлось позвонить last/2). попробуйте просто solve([],X), write(X),nl, вы это увидите. - person Will Ness; 08.05.2013