Пролог Решение проблемы N ферзей с проверкой диагонали

Это из Prolog Programming for Artificial Intelligence четвертого издания Ивана Братко (WorldCat)

стр. 111 - Рисунок 4.12 Программа 2 для задачи восьми ферзей.

solution(Queens) :-
    permutation([1,2,3,4,5,6,7,8], Queens),
    safe(Queens).

% safe(Queens): Queens is a list of Y-coordinates of non-attacking queens

safe([]).

safe([Queen|Others]) :-
    safe(Others),
    noattack(Queen,Others,1).

% noattack(Queen, Queens, Dist):
%   Queen does not attack any queen in Queens at horizontal distance Dist

noattack(_,[],_).
noattack(Y,[Y1|Ylist],Xdist) :-
    Y1 - Y =\= Xdist,            % Not upward diagonal attack
    Y - Y1 =\= Xdist,            % Not downward diagonal attack
    Dist1 is Xdist + 1,
    noattack(Y,Ylist,Dist1).

Пример запуска.

solution(Queens).
Queens = [1, 5, 8, 6, 3, 7, 2, 4] ;
Queens = [1, 6, 8, 3, 7, 4, 2, 5] ;
Queens = [1, 7, 4, 6, 8, 2, 5, 3] ;
Queens = [1, 7, 5, 8, 2, 4, 6, 3] ;
Queens = [2, 4, 6, 8, 3, 1, 7, 5] ;
Queens = [2, 5, 7, 1, 3, 8, 6, 4] ;
Queens = [2, 5, 7, 4, 1, 8, 6, 3] ;
Queens = [2, 6, 1, 7, 4, 8, 3, 5] ;
Queens = [2, 6, 8, 3, 1, 4, 7, 5] ;
Queens = [2, 7, 3, 6, 8, 5, 1, 4] ;
Queens = [2, 7, 5, 8, 1, 4, 6, 3] ;
Queens = [2, 8, 6, 1, 3, 5, 7, 4] ;
Queens = [3, 1, 7, 5, 8, 2, 4, 6] ;
Queens = [3, 5, 2, 8, 1, 7, 4, 6] ;
Queens = [3, 5, 2, 8, 6, 4, 7, 1] ;
Queens = [3, 5, 7, 1, 4, 2, 8, 6] ;
Queens = [3, 5, 8, 4, 1, 7, 2, 6] ;
Queens = [3, 6, 2, 5, 8, 1, 7, 4] 
Action (h for help) ? abort

Хотя этот код может выглядеть не так, как ваш, если вы знаете, как реорганизовать код пролога, а затем измените имена предикатов и имена переменных и поверните доску так, чтобы строки были столбцами, а столбцы были строками, вы увидите, что этот ответ совпадает с вашей идеей и кодом.

Вот вторая часть ответа.

solution_2(N,Queens) :-
    numlist(1,N,List),
    permutation(List, Queens),
    safe(Queens).

Пример работает.

?- solution_2(1,Queens).
Queens = [1] ;
false.

?- solution_2(2,Queens).
false.

?- solution_2(3,Queens).
false.

?- solution_2(4,Queens).
Queens = [2, 4, 1, 3] ;
Queens = [3, 1, 4, 2] ;
false.

?- solution_2(5,Queens).
Queens = [1, 3, 5, 2, 4] ;
Queens = [1, 4, 2, 5, 3] ;
Queens = [2, 4, 1, 3, 5] ;
Queens = [2, 5, 3, 1, 4] ;
Queens = [3, 1, 4, 2, 5] ;
Queens = [3, 5, 2, 4, 1] ;
Queens = [4, 1, 3, 5, 2] ;
Queens = [4, 2, 5, 3, 1] ;
Queens = [5, 2, 4, 1, 3] ;
Queens = [5, 3, 1, 4, 2] ;
false.

?- solution_2(6,Queens).
Queens = [2, 4, 6, 1, 3, 5] ;
Queens = [3, 6, 2, 5, 1, 4] ;
Queens = [4, 1, 5, 2, 6, 3] ;
Queens = [5, 3, 1, 6, 4, 2] ;
false.

?- solution_2(7,Queens).
Queens = [1, 3, 5, 7, 2, 4, 6] ;
Queens = [1, 4, 7, 3, 6, 2, 5] ;
Queens = [1, 5, 2, 6, 3, 7, 4] ;
Queens = [1, 6, 4, 2, 7, 5, 3] ;
Queens = [2, 4, 1, 7, 5, 3, 6] ;
Queens = [2, 4, 6, 1, 3, 5, 7] ;
Queens = [2, 5, 1, 4, 7, 3, 6] ;
Queens = [2, 5, 3, 1, 7, 4, 6] ;
Queens = [2, 5, 7, 4, 1, 3, 6] ;
Queens = [2, 6, 3, 7, 4, 1, 5] ;
Queens = [2, 7, 5, 3, 1, 6, 4] ;
Queens = [3, 1, 6, 2, 5, 7, 4] ;
Queens = [3, 1, 6, 4, 2, 7, 5] ;
Queens = [3, 5, 7, 2, 4, 6, 1] ;
Queens = [3, 6, 2, 5, 1, 4, 7] ;
Queens = [3, 7, 2, 4, 6, 1, 5] ;
Queens = [3, 7, 4, 1, 5, 2, 6] ;
Queens = [4, 1, 3, 6, 2, 7, 5] ;
Queens = [4, 1, 5, 2, 6, 3, 7] ;
Queens = [4, 2, 7, 5, 3, 1, 6] ;
Queens = [4, 6, 1, 3, 5, 7, 2] ;
Queens = [4, 7, 3, 6, 2, 5, 1] ;
Queens = [4, 7, 5, 2, 6, 1, 3] ;
Queens = [5, 1, 4, 7, 3, 6, 2] ;
Queens = [5, 1, 6, 4, 2, 7, 3] ;
Queens = [5, 2, 6, 3, 7, 4, 1] ;
Queens = [5, 3, 1, 6, 4, 2, 7] ;
Queens = [5, 7, 2, 4, 6, 1, 3] ;
Queens = [5, 7, 2, 6, 3, 1, 4] ;
Queens = [6, 1, 3, 5, 7, 2, 4] ;
Queens = [6, 2, 5, 1, 4, 7, 3] ;
Queens = [6, 3, 1, 4, 7, 5, 2] ;
Queens = [6, 3, 5, 7, 1, 4, 2] ;
Queens = [6, 3, 7, 4, 1, 5, 2] ;
Queens = [6, 4, 2, 7, 5, 3, 1] ;
Queens = [6, 4, 7, 1, 3, 5, 2] ;
Queens = [7, 2, 4, 6, 1, 3, 5] ;
Queens = [7, 3, 6, 2, 5, 1, 4] ;
Queens = [7, 4, 1, 5, 2, 6, 3] ;
Queens = [7, 5, 3, 1, 6, 4, 2] ;
false.

РЕДАКТИРОВАТЬ

Из комментария The logic Bratko is using does not make sense to me.

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

solution_3(N,Queens) :-
    numlist(1,N,List),
    permutation(List, Queens),
    safe_3(Queens).

safe_3([]).

safe_3([Queen|Others]) :-
    safe_3(Others),
    noattack_3(Queen,Others,1).

noattack_3(_,[],_).
noattack_3(Y,[Y1|Ylist],Xdist) :-
    write('noattack_3 - Y:'),write(Y),write(', Y1: '),write(Y1),write(', Ylist: '),write(Ylist),write(', Xdist: '),writeln(Xdist),
    Dist1 is Xdist + 1,
    noattack_3(Y,Ylist,Dist1).

Бег на доске 3x3 дает:

?- solution_3(3,Queens).
noattack_3 - Y:2, Y1: 3, Ylist: [], Xdist: 1
noattack_3 - Y:1, Y1: 2, Ylist: [3], Xdist: 1
noattack_3 - Y:1, Y1: 3, Ylist: [], Xdist: 2
Queens = [1, 2, 3] ;
noattack_3 - Y:3, Y1: 2, Ylist: [], Xdist: 1
noattack_3 - Y:1, Y1: 3, Ylist: [2], Xdist: 1
noattack_3 - Y:1, Y1: 2, Ylist: [], Xdist: 2
Queens = [1, 3, 2] ;
noattack_3 - Y:1, Y1: 3, Ylist: [], Xdist: 1
noattack_3 - Y:2, Y1: 1, Ylist: [3], Xdist: 1
noattack_3 - Y:2, Y1: 3, Ylist: [], Xdist: 2
Queens = [2, 1, 3] ;
noattack_3 - Y:3, Y1: 1, Ylist: [], Xdist: 1
noattack_3 - Y:2, Y1: 3, Ylist: [1], Xdist: 1
noattack_3 - Y:2, Y1: 1, Ylist: [], Xdist: 2
Queens = [2, 3, 1] ;
noattack_3 - Y:1, Y1: 2, Ylist: [], Xdist: 1
noattack_3 - Y:3, Y1: 1, Ylist: [2], Xdist: 1
noattack_3 - Y:3, Y1: 2, Ylist: [], Xdist: 2
Queens = [3, 1, 2] ;
noattack_3 - Y:2, Y1: 1, Ylist: [], Xdist: 1
noattack_3 - Y:3, Y1: 2, Ylist: [1], Xdist: 1
noattack_3 - Y:3, Y1: 1, Ylist: [], Xdist: 2
Queens = [3, 2, 1] ;
false.

Обратите внимание, что с удаленными ограничениями он не генерирует допустимые решения, но показывает генерацию значений для выполнения предиката, что я и хотел.