Пролог сдается после провала один раз?

Question

Я все еще изучаю Пролог, так что прости меня, если я сделаю какую-то основную ошибку здесь. Я добавил аннотации, чтобы объяснить, что, по моему мнению, делает код, на случай, если я ошибаюсь. Простите, если я объясняю очевидное местами.

n_queens(NumQueens, Answer) :-
        length(Answer, NumQueens), %Answer must be a list of length NumQueens
        queens_are_safe(Answer). %All queens in Answer must be safe       

queens_are_safe([]). %If there are no queens, nobody's in danger
queens_are_safe([Queen | Queens]) :-
        queen_is_safe(Queen, Queens), %Is the queen safe from her peers?
        queens_are_safe(Queens). %Recursively check the other queens

queen_is_safe(_, []).
queen_is_safe(NewQueen, [Queen | Queens]) :-
        not(same_column(NewQueen, Queen)),
        not(same_row(NewQueen, Queen)),
        not(diagonal(NewQueen, Queen)),
        queen_is_safe(NewQueen, Queens). %Recursively ensure NewQueen is safe from other queens

diagonal(X/Y, X1/Y1) :- Y1 - Y = X1 - X. %If the X and Y deltas are equal, arguments are diagonal
same_column(X/_, X/_). %If the X coordinates are the same, it's the same column.
same_row(_/Y, _/Y). %If the Y coordinates are the same, it's the same row.

Я ожидаю, что Prolog создаст список Queens, свяжет его с Answer и повторяет до тех пор, пока не найдет список значений, удовлетворяющих всем условиям. Например, если NumQueens равен 2, он будет тестировать [0/0, 0/0], затем [1/0, 0/0] и т. Д.

Однако я подозреваю, что я здесь не прав. Здесь не работает стек трассировки:

Exit: (12) samecolumn(_15108/_15110, _15108/_15116) ? creep
Fail: (11) not(user:samecolumn(_15048, _15054)) ? creep

Очевидно, проблема в том, что он использует _15108 в качестве значений X для same_column. Я ожидал бы, что он тогда попробует same_column, но с другими значениями для X. Но он не пробует снова, он терпит неудачу и возвращает false для запроса n_queens(8,Ans). Почему это?

Answer 1

Я получаю следующую ошибку при попытке запустить ваш код в SWI-Prolog:

?- n_queens(8, Ans).
ERROR: not/1: Undefined procedure: samecolumn/2
ERROR:   However, there are definitions for:
ERROR:         same_column/2

Используете ли вы Prolog, который молча терпит неудачу при попытке вызвать неопределенный предикат?Вы не должны, или вы должны настроить его, чтобы выдать ошибку в этом случае.Например, в YAP поведение по умолчанию является неправильным, которое вы видите:

   ?- n_queens(8, Ans).
no

Но вы можете исправить это так:

   ?- set_prolog_flag(unknown, error).
yes
   ?- n_queens(8, Ans).
     ERROR!!
     EXISTENCE ERROR- procedure samecolumn/2 is undefined, called from context  prolog:$query/2
                 Goal was user:samecolumn(_131242,_131243)

Редактировать: Простосделайте это явным, как показывают сообщения, одна из непосредственных проблем заключается в том, что вы пытаетесь вызвать предикат samecolumn/2, который не определен;Вы, вероятно, хотели позвонить same_column/2.

После этого код все равно будет неправильным из-за цели Y1 - Y = X1 - X в diagonal/2.Вы, вероятно, захотите, например, diagonal(2/3, 3/4) добиться успеха, но цель 4 - 3 = 3 - 2 не делает не успешной в Прологе:

?- 4 - 3 = 3 - 2.
false.

Это потому, что Пролог не рассматривает такие термины как 4 - 3 в качестве арифметических выражений для вычисления числа типа 1.Возможно, вам нужен оператор =:=, который оценивает оба операнда по числам, а затем сравнивает их:

?- 4 - 3 =:= 3 - 2.
true.

Но даже после всего этого этот код не будет работать.Ваша программа нигде не указывает, что переменные в Queens должны быть связаны с целыми числами 1 до NumQueens.Пролог не просто составляет эти цифры для вас!Возможно, вы захотите взглянуть на программирование ограничений с помощью clpfd.