Пролог Решение задачи N Queens с диагональю проверки

Question

Отказ от ответственности: матрица представлена ​​в виде списка, где номер - это строка, а индекс (1 - 8) - номер столбца.

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

Мой код:

    eightQueens(Board) :-
        permutation([1,2,3,4,5,6,7,8], Board),
        checkDiagonals(Board).

    /* Check Diagonal and AntiDiagonal (Diagonal not implemented yet) 
        checkD checks antidiagonal */
    checkDiagonals([H|T]) :-
        checkD([H|T]).

    /* Value is the index of H so it acts as the column value.
       dValue is the sum of H, which represents row value, and Value.
       If any two queens have the same dValue this means they are in 
       the same anti-diagonal.
       checkD gets the dValue of the first element in the list and 
       passes it to checkDHelper which compares the dValue against 
       the dValue's of the other elements in the list. */
    checkD([]).
    checkD([H|T]) :-
        indexOf([H|T], H, RowValue),
        findValue(RowValue, H, DValue),
        checkDHelper(T, DValue),
        checkD(T).

    /* checkDHelper compares the dValue against 
       the dValue's of the other elements in the list. */ 

    checkDHelper([], DValue). 
    checkDHelper([H|T], DValue) :-
        indexOf([H|T], H, RowValueIndex),
        findValue(IndexValue, H, DValueIndex),
        %check if dValue of current index is equal to Value provided
        notEqual(DValue, DValueIndex),
        checkDHelper(T, DValue).

     %Finds index of the element
    indexOf([Element|_], Element, 1).
    indexOf([_|Tail], Element, Value) :-
         indexOf(Tail, Element, Value1),
         Value is Value1 + 1.

    %Checks if values are not equal 
    notEqual(X, Y) :-
        X =\= Y.

    %Finds dValue
    findValue(RowValue, ColumnValue, dValue) :-
        dValue is X + Y.

Вот пример платы, которая будет работать (представлена ​​как checkDiagonals ([5,1,8,4,2,7,3,6]).)

Answer 1

Это из 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.

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

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).

Запуск для доски 3х3 дает:

?- 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.

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