Советы, чтобы понять великолепную программу для решения Queens

Question

In Art of Prolog of Sterling & Shapiro, упражнение Раздел 14.1 (v):

queens(N,Qs) :-
    length(Qs,N),
    place_queens(N,Qs,_,_).

place_queens(0,_Qs,_Ups,_Downs).
place_queens(I,Qs,Ups,[_|Downs]) :-
    I > 0, I1 is I-1,
    place_queens(I1,Qs,[_|Ups] ,Downs),
    place_queen(I,Qs,Ups,Downs).

place_queen(Q,[Q|_],[Q|_],[Q|_]).
place_queen(Q,[_|Qs],[_|Ups],[_|Downs] ):-
    place_queen(Q,Qs,Ups,Downs).

Это великолепная программа в 11 строк, которая быстро решает проблемупозиционирование королев на шахматной доске.Это волшебно: есть только счетчик, рекурсия и списки, которые становятся длиннее и короче.Я даже с помощью трассировки не понимаю этого.Может кто-нибудь объяснить это мне?Как вы можете написать такую ​​программу?Каков логический / умственный процесс, который приводит к получению этой программы, например, из другого (хорошего стандартного решения):

queens(N,Qs) :-
    numlist(1,N,Ns), 
    queens(Ns,[ ],Qs).

queens(UnplacedQs,SafeQs,Qs) :-
    select(Q,UnplacedQs,UnplacedQs1),
    \+ attack(Q,SafeQs),
    queens(UnplacedQs1,[Q|SafeQs] ,Qs).
queens([ ],Qs,Qs).

attack(X,Xs) :-
    attack(X,1,Xs).

attack(X,N,[Y|_]) :-
    X is Y+N ; X is Y-N.
attack(X,N,[_|Ys]) :-
    N1 is N+1,
    attack(X,N1,Ys).

Answer 1

Пробелы могут значительно улучшить читаемость программы.Именование переменных также очень важно в этом отношении:

queens(N, QS) :-
    length(QS, N),
    place_queens(N,  QS, _, _).

place_queens(0,_,_,_).
place_queens(    I,  QS,    US, [_|DS]) :- I > 0,
    I1 is I-1,
    place_queens(I1, QS, [_|US],   DS),
    place_queen( I,  QS,    US,    DS).

place_queen(     I,  QS,    US,    DS):-       % an equivalent definition!
   nth1(K,QS,I), nth1(K,US,I), nth1(K,DS,I).   % between(1,N,K) holds

Иллюстрация от ответа Виллема , снова настроенная для пробела:

place_queens(   4,              [Q1,Q2,Q3,Q4],              UT,  [D1,D2,D3,D4|DT]) :-
    place_queens(   3,          [Q1,Q2,Q3,Q4],          [U4|UT],    [D2,D3,D4|DT]) :-
        place_queens(   2,      [Q1,Q2,Q3,Q4],       [U3,U4|UT],       [D3,D4|DT]) :-
            place_queens(   1,  [Q1,Q2,Q3,Q4],    [U2,U3,U4|UT],          [D4|DT]) :-
                place_queens(0, [Q1,Q2,Q3,Q4], [U1,U2,U3,U4|UT],              DT),
                %% ---
                place_queen(1,  [Q1,Q2,Q3,Q4],    [U2,U3,U4|UT],              DT),
            place_queen(2,      [Q1,Q2,Q3,Q4],       [U3,U4|UT],          [D4|DT]),
        place_queen(3,          [Q1,Q2,Q3,Q4],          [U4|UT],       [D3,D4|DT]),
    place_queen(4,              [Q1,Q2,Q3,Q4],              UT,     [D2,D3,D4|DT]).

Таким образом, рекурсия строит N вложенных N -длинных циклов, которыми являются действующие вызовы place_queen, работающие над теми же списками с начальными позициями, смещенными в определенной схеме.

Это также сделает так, что UT = [U5,U6,U7,U8|_] (из-за place_queen(4)) и DT = [D5,D6,D7,D8|_] (из-за place_queen(1)), поэтому четыре цикла будут эквивалентны

four_queens( [Q1,Q2,Q3,Q4] ) :-
    place_queen(1, [Q1,Q2,Q3,Q4], [U2,U3,U4,U5], [D5,D6,D7,D8]),
    place_queen(2, [Q1,Q2,Q3,Q4], [U3,U4,U5,U6], [D4,D5,D6,D7]),
    place_queen(3, [Q1,Q2,Q3,Q4], [U4,U5,U6,U7], [D3,D4,D5,D6]),
    place_queen(4, [Q1,Q2,Q3,Q4], [U5,U6,U7,U8], [D2,D3,D4,D5]).

Действительно, он дает те же результаты, что и queens(4, QS).

И мы можем видеть там диагонали .... Верно?Когда ставится первая королева, скажем, Q3, она становится 1=Q3=U4=D7,

four_queens( [Q1,Q2, 1,Q4] ) :- 
    place_queen(1, [Q1,Q2, ?,Q4], [U2,U3, ?,U5], [D5,D6, ?,D8]),  % 1st row, 3rd pos
    place_queen(2, [Q1,Q2, 1,Q4], [U3, 1,U5,U6], [D4,D5,D6, 1]),
    place_queen(3, [Q1,Q2, 1,Q4], [ 1,U5,U6,U7], [D3,D4,D5,D6]),
    place_queen(4, [Q1,Q2, 1,Q4], [U5,U6,U7,U8], [D2,D3,D4,D5]).

, и тогда невозможно, чтобы 2 королева была place_queen ed на Q2(взято 1 на US) или Q4 (взято 1 на DS).Таким образом, единственная другая возможность - это 2=Q1=U3=D4:

four_queens( [ 2,Q2, 1,Q4] ) :-
    place_queen(1, [ 2,Q2, ?,Q4], [U2, 2, 1,U5], [D5,D6, 1,D8]),
    place_queen(2, [ ?,Q2, 1,Q4], [ ?, 1,U5,U6], [ ?,D5,D6, 1]),  % 2nd row, 1st pos
    place_queen(3, [ 2,Q2, 1,Q4], [ 1,U5,U6,U7], [D3, 2,D5,D6]),
    place_queen(4, [ 2,Q2, 1,Q4], [U5,U6,U7,U8], [D2,D3, 2,D5]).

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

Далее, 3=Q2 невозможно, потому что D4=2 уже.Таким образом, мы получаем 3=Q4=U7=D6,

four_queens( [ 2,Q2, 1, 3] ) :-
    place_queen(1, [ 2,Q2, ?, 3], [U2, 2, 1,U5], [D5, 3, 1,D8]),
    place_queen(2, [ ?,Q2, 1, 3], [ 2, 1,U5,U6], [ 2,D5, 3, 1]),
    place_queen(3, [ 2,Q2, 1, ?], [ 1,U5,U6, ?], [D3, 2,D5, ?]),  % 3rd row, 4th pos
    place_queen(4, [ 2,Q2, 1, 3], [U5,U6, 3,U8], [D2,D3, 2,D5]).

, и ответ очевиден!

four_queens( [ 2, 4, 1, 3] ) :-
    place_queen(1, [ 2, 4, ?, 3], [U2, 2, 1,U5], [D5, 3, 1,D8]),
    place_queen(2, [ ?, 4, 1, 3], [ 2, 1,U5, 4], [ 2,D5, 3, 1]),
    place_queen(3, [ 2, 4, 1, ?], [ 1,U5, 4, 3], [ 4, 2,D5, 3]),
    place_queen(4, [ 2, ?, 1, 3], [U5, ?, 3,U8], [D2, ?, 2,D5]).  % 4th row, 2nd pos

---

Таким образом, мыслительный процесс автора мог быть таким.Шахматная доска представляет собой квадратную матрицу.Что если размещение королевы в какой-то конкретной ячейке автоматически осветит весь столбец, мы можем это сделать?И диагонали тоже?

Ключевым выводом было то, что это три отдельных вида одной и той же платы, и тогда, вероятно, было легко придумать эти матрицы:

           [[A, B, C, D],     [[E, F, G, H],     [[O, N, M, L],
            [A, B, C, D],      [F, G, H, I],      [P, O, N, M],
            [A, B, C, D],      [G, H, I, J],      [Q, P, O, N],
            [A, B, C, D]]      [H, I, J, K]]      [R, Q, P, O]]

итогда им просто нужен был способ настроить их на любой N автоматически.Он мог бы быть закодирован с помощью некоторой арифметики и пары вызовов length и maplist, но это было бы гораздо менее загадочно и круто, поэтому вместо этого они вставили и упростили все.

---

Еще одна интересная вещь, которую следует заметить в этом коде, это то, как он использует рекурсию для линейного перехода к базовому случаю при настройке этапа для следующих вычислений, которые будут выполняться изнутри, где на самом деле внутренний шаг рекурсии place_queen(1) фактическистановится самым внешним циклом в императивной вложенных циклах интерпретации модели недетерминированных вычислений для генерации и проверки.

Как будто создает код, который должен выполняться первым (вложенный N)циклы для данного значения N), а затем запускает его.

_{(Что-то, скажем, Common Lisp , реализация может делать со своими макросами ; но вместо этого использовать рекурсию. Или в функциональной парадигме мы можем сказать, что этоиспользует неявные продолжения (во второй строке в определении каждого предиката, которые должны быть введены после возврата первого рекурсивного), чтобы эмулировать то, что в противном случае могло бы быть достигнуто путем создания такой функции , которая будет явно выполняться следующим в стиль продолжения .)}

Answer 2

Код в первой части вопроса объясняется здесь. Код размещен здесь, чтобы читатель не ошибочно посмотрел на неправильный код.

queens(N,Qs) :-
    length(Qs,N),
    place_queens(N,Qs,_,_).

place_queens(0,_Qs,_Ups,_Downs).
place_queens(I,Qs,Ups,[_|Downs]) :-
    I > 0, I1 is I-1,
    place_queens(I1,Qs,[_|Ups] ,Downs),
    place_queen(I,Qs,Ups,Downs).

place_queen(Q,[Q|_],[Q|_],[Q|_]).
place_queen(Q,[_|Qs],[_|Ups],[_|Downs] ):-
    place_queen(Q,Qs,Ups,Downs).

Этот код, как и большинство решений Prolog для задачи N-Queens, генерируется и тестируется. Код генерирует возможное решение и проверяет его. Однако вместо того, чтобы генерировать все позиции для одного возможного ответа одновременно, позиции ферзя устанавливаются постепенно и меняются при частичном сбое до тех пор, пока не будет найдено полное решение.

В коде есть один письменный тест, который

place_queen(Q,[Q|_],[Q|_],[Q|_]).

Чтобы понять это, необходимо понять, в чем смысл аргументов, связанных с этим утверждением из здесь

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

Первый аргумент представляет ферзь, идентифицируемый положительным целым числом и связанный.

Второй аргумент представляет столбец и всегда представляет собой список размера доски, где каждое зелье в списке представляет один из столбцов доски. Код использует переменную Qs для, но для меня это имеет больше смысла как Rs, то есть строки. Так что если в позиции в списке есть какое-либо связанное значение, которое будет королевой, атакующей в этом столбце.

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

Например, на изображении ниже белая королева представляет положение проверяемой королевы, а черные королевы, идущие по диагонали вверх, представляют восходящий диагональный список, а другая королева представляет нисходящий диагональный список.

Примечание: изображения, созданные с использованием Настройка шахматной диаграммы

Диагональ спуска вверх равна длине двух, а диагональ спада - длине единицы.

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

Так что для теста

place_queen(Q,[Q|_],[Q|_],[Q|_]).

что совпадает с написанным для ясности и документации

place_queen(Q,Rs,Ups,Downs) :-
  Rs = [R_1|_],
  Ups = [U_1|_],
  Downs = [D_1|_],
  Q = R_1, Q = U_1, Q = D_1

тогда если

Q равно 1
R_1 не связан
U_1 не связан
D_1 не связан

Тестовое прошлое и 1 связаны с переменными R_1, U_1 и D_1.

и пример теста, который не прошел

Q - 3
R_1 составляет 1
U_1 не связан
D_1 не связан

Теперь для вызова, который не проходит как тест из-за отсутствия значения в списке.

Q равно 2
R_1 это []
U_1 не связан
D_1 не связан

Остальная часть кода просто генерирует кейсы для тестирования.

Второй аргумент можно увидеть генерирующим при запуске этого варианта кода.

queens(N) :-
    length(Qs,N),
    format("N: ~w, Qs: ~w~n",[N,Qs]).

?- queens(4).
N: 4, Qs: [_6476,_6482,_6488,_6494]
true.

Диагональные аргументы можно увидеть, генерируя этот вариант кода.

queens(N) :-
    length(Qs,N),
    place_queens(N,Qs,_,_).

place_queens(0,_Qs,_Ups,_Downs).
place_queens(I,Qs,Ups,[_|Downs]) :-
    I > 0,
    I1 is I-1,
    place_queens(I1,Qs,[_|Ups] ,Downs),
    format('I1: ~w, Qs: ~w, Ups: ~w, Downs: ~w~n',[I1,Qs,Ups,Downs]).

?- queens(4).
I1: 0, Qs: [_6474,_6480,_6486,_6492], Ups: [_6528,_6516,_6504|_6506], Downs: _6536
I1: 1, Qs: [_6474,_6480,_6486,_6492], Ups: [_6516,_6504|_6506], Downs: [_6534|_6536]
I1: 2, Qs: [_6474,_6480,_6486,_6492], Ups: [_6504|_6506], Downs: [_6522,_6534|_6536]
I1: 3, Qs: [_6474,_6480,_6486,_6492], Ups: _6506, Downs: [_6510,_6522,_6534|_6536]
true ;
false.

эта маленькая часть

place_queen(Q,[_|Rs],[_|Ups],[_|Downs] ):-
    place_queen(Q,Rs,Ups,Downs).

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

Чтобы было проще увидеть генерацию и тестирование в действии, измените код как таковой

queens(N,Qs) :-
    length(Qs,N),
    place_queens(N,Qs,_,_).

place_queens(0,_Qs,_Ups,_Downs).
place_queens(I,Qs,Ups,[_|Downs]) :-
    I > 0,
    I1 is I-1,
    place_queens(I1,Qs,[_|Ups] ,Downs),
    format('Generate 1 - I: ~w, Qs: ~w, Ups: ~w, Downs: ~w~n',[I,Qs,Ups,Downs]),
    place_queen(I,Qs,Ups,Downs),
    format('Result    -> I: ~w, Qs: ~w, Ups: ~w, Downs: ~w~n',[I,Qs,Ups,Downs]).

place_queen(Q,Rs,Ups,Downs) :-
    Rs = [R_1|_],
    Ups = [U_1|_],
    Downs = [D_1|_],
    format('Test        - Q : ~w, R_1: ~w, U_1: ~w, D_1: ~w~n',[Q,R_1,U_1,D_1]),
    (
        Rs = [Q|_],
        Ups = [Q|_],
        Downs = [Q|_]
    ->
        format('Test success~n')
    ;
        format('Test failure~n'),
        fail
    ).

place_queen(Q,[_|Qs],[_|Ups],[_|Downs] ):-
    format('Generate 2 - Q: ~w, Qs: ~w, Ups: ~w, Downs: ~w~n',[Q,Qs,Ups,Downs]),
    place_queen(Q,Qs,Ups,Downs).

Пример запуска до первого решения.

?- queens(4,Qs).
Generate 1 - I: 1, Qs: [_6488,_6494,_6500,_6506], Ups: [_6542,_6530,_6518|_6520], Downs: _6550
Test        - Q : 1, Q_1: _6488, U_1: _6542, D_1: _6596
Test success
Result    -> I: 1, Qs: [1,_6494,_6500,_6506], Ups: [1,_6530,_6518|_6520], Downs: [1|_6598]
Generate 1 - I: 2, Qs: [1,_6494,_6500,_6506], Ups: [_6530,_6518|_6520], Downs: [_6548,1|_6598]
Test        - Q : 2, Q_1: 1, U_1: _6530, D_1: _6548
Test failure
Generate 2 - Q: 2, Qs: [_6494,_6500,_6506], Ups: [_6518|_6520], Downs: [1|_6598]
Test        - Q : 2, Q_1: _6494, U_1: _6518, D_1: 1
Test failure
Generate 2 - Q: 2, Qs: [_6500,_6506], Ups: _6520, Downs: _6598
Test        - Q : 2, Q_1: _6500, U_1: _6746, D_1: _6752
Test success
Result    -> I: 2, Qs: [1,_6494,2,_6506], Ups: [_6530,_6518,2|_6748], Downs: [_6548,1,2|_6754]
Generate 1 - I: 3, Qs: [1,_6494,2,_6506], Ups: [_6518,2|_6748], Downs: [_6536,_6548,1,2|_6754]
Test        - Q : 3, Q_1: 1, U_1: _6518, D_1: _6536
Test failure
Generate 2 - Q: 3, Qs: [_6494,2,_6506], Ups: [2|_6748], Downs: [_6548,1,2|_6754]
Test        - Q : 3, Q_1: _6494, U_1: 2, D_1: _6548
Test failure
Generate 2 - Q: 3, Qs: [2,_6506], Ups: _6748, Downs: [1,2|_6754]
Test        - Q : 3, Q_1: 2, U_1: _6902, D_1: 1
Test failure
Generate 2 - Q: 3, Qs: [_6506], Ups: _6898, Downs: [2|_6754]
Test        - Q : 3, Q_1: _6506, U_1: _6932, D_1: 2
Test failure
Generate 2 - Q: 3, Qs: [], Ups: _6928, Downs: _6754
Generate 2 - Q: 2, Qs: [_6506], Ups: _6742, Downs: _6748
Test        - Q : 2, Q_1: _6506, U_1: _6782, D_1: _6788
Test success
Result    -> I: 2, Qs: [1,_6494,_6500,2], Ups: [_6530,_6518,_6740,2|_6784], Downs: [_6548,1,_6746,2|_6790]
Generate 1 - I: 3, Qs: [1,_6494,_6500,2], Ups: [_6518,_6740,2|_6784], Downs: [_6536,_6548,1,_6746,2|_6790]
Test        - Q : 3, Q_1: 1, U_1: _6518, D_1: _6536
Test failure
Generate 2 - Q: 3, Qs: [_6494,_6500,2], Ups: [_6740,2|_6784], Downs: [_6548,1,_6746,2|_6790]
Test        - Q : 3, Q_1: _6494, U_1: _6740, D_1: _6548
Test success
Result    -> I: 3, Qs: [1,3,_6500,2], Ups: [_6518,3,2|_6784], Downs: [_6536,3,1,_6746,2|_6790]
Generate 1 - I: 4, Qs: [1,3,_6500,2], Ups: [3,2|_6784], Downs: [_6524,_6536,3,1,_6746,2|_6790]
Test        - Q : 4, Q_1: 1, U_1: 3, D_1: _6524
Test failure
Generate 2 - Q: 4, Qs: [3,_6500,2], Ups: [2|_6784], Downs: [_6536,3,1,_6746,2|_6790]
Test        - Q : 4, Q_1: 3, U_1: 2, D_1: _6536
Test failure
Generate 2 - Q: 4, Qs: [_6500,2], Ups: _6784, Downs: [3,1,_6746,2|_6790]
Test        - Q : 4, Q_1: _6500, U_1: _7070, D_1: 3
Test failure
Generate 2 - Q: 4, Qs: [2], Ups: _7066, Downs: [1,_6746,2|_6790]
Test        - Q : 4, Q_1: 2, U_1: _7100, D_1: 1
Test failure
Generate 2 - Q: 4, Qs: [], Ups: _7096, Downs: [_6746,2|_6790]
Generate 2 - Q: 3, Qs: [_6500,2], Ups: [2|_6784], Downs: [1,_6746,2|_6790]
Test        - Q : 3, Q_1: _6500, U_1: 2, D_1: 1
Test failure
Generate 2 - Q: 3, Qs: [2], Ups: _6784, Downs: [_6746,2|_6790]
Test        - Q : 3, Q_1: 2, U_1: _6962, D_1: _6746
Test failure
Generate 2 - Q: 3, Qs: [], Ups: _6958, Downs: [2|_6790]
Generate 2 - Q: 2, Qs: [], Ups: _6778, Downs: _6784
Generate 2 - Q: 1, Qs: [_6494,_6500,_6506], Ups: [_6530,_6518|_6520], Downs: _6586
Test        - Q : 1, Q_1: _6494, U_1: _6530, D_1: _6626
Test success
Result    -> I: 1, Qs: [_6488,1,_6500,_6506], Ups: [_6542,1,_6518|_6520], Downs: [_6584,1|_6628]
Generate 1 - I: 2, Qs: [_6488,1,_6500,_6506], Ups: [1,_6518|_6520], Downs: [_6548,_6584,1|_6628]
Test        - Q : 2, Q_1: _6488, U_1: 1, D_1: _6548
Test failure
Generate 2 - Q: 2, Qs: [1,_6500,_6506], Ups: [_6518|_6520], Downs: [_6584,1|_6628]
Test        - Q : 2, Q_1: 1, U_1: _6518, D_1: _6584
Test failure
Generate 2 - Q: 2, Qs: [_6500,_6506], Ups: _6520, Downs: [1|_6628]
Test        - Q : 2, Q_1: _6500, U_1: _6776, D_1: 1
Test failure
Generate 2 - Q: 2, Qs: [_6506], Ups: _6772, Downs: _6628
Test        - Q : 2, Q_1: _6506, U_1: _6806, D_1: _6812
Test success
Result    -> I: 2, Qs: [_6488,1,_6500,2], Ups: [1,_6518,_6770,2|_6808], Downs: [_6548,_6584,1,2|_6814]
Generate 1 - I: 3, Qs: [_6488,1,_6500,2], Ups: [_6518,_6770,2|_6808], Downs: [_6536,_6548,_6584,1,2|_6814]
Test        - Q : 3, Q_1: _6488, U_1: _6518, D_1: _6536
Test success
Result    -> I: 3, Qs: [3,1,_6500,2], Ups: [3,_6770,2|_6808], Downs: [3,_6548,_6584,1,2|_6814]
Generate 1 - I: 4, Qs: [3,1,_6500,2], Ups: [_6770,2|_6808], Downs: [_6524,3,_6548,_6584,1,2|_6814]
Test        - Q : 4, Q_1: 3, U_1: _6770, D_1: _6524
Test failure
Generate 2 - Q: 4, Qs: [1,_6500,2], Ups: [2|_6808], Downs: [3,_6548,_6584,1,2|_6814]
Test        - Q : 4, Q_1: 1, U_1: 2, D_1: 3
Test failure
Generate 2 - Q: 4, Qs: [_6500,2], Ups: _6808, Downs: [_6548,_6584,1,2|_6814]
Test        - Q : 4, Q_1: _6500, U_1: _7070, D_1: _6548
Test success
Result    -> I: 4, Qs: [3,1,4,2], Ups: [_6770,2,4|_7072], Downs: [_6524,3,4,_6584,1,2|_6814]
Qs = [3, 1, 4, 2] .

Если вам трудно прочитать этот вывод здесь, потому что он широкий, а также трудно просмотреть в качестве вывода на верхний уровень (swipl.exe), тогда посмотрите, как использовать protocol / 1 для записать вывод в файл для просмотра и анализа.

Answer 3

Давайте сначала посмотрим на верхний предикат.Здесь мы решаем проблему N × N ферзей, вызывая queens(N,Qs).Первый вызов в теле length(Qs, N) создает список переменных длиной N.Затем он вызывает place_queens/4 с place_queens(N, Qs, _, _).Таким образом, он передает две свободные переменные в place_queens/4.Позже мы, по незнанию, создадим список.

Сначала place_queens/4 вызывается рекурсивно, пока мы не достигнем нуля для I, если мы, например, "развернем" программу для N = 4, мы получим:

place_queens(4, [Q1,Q2,Q3,Q4], UT, [D1,D2,D3,D4|DT]) :-
    place_queens(3, [Q1,Q2,Q3,Q4], [U4|UT], [D2,D3,D4|DT]) :-
        place_queens(2, [Q1,Q2,Q3,Q4], [U3,U4|UT], [D3,D4|DT]) :-
            place_queens(1, [Q1,Q2,Q3,Q4], [U2,U3,U4|UT], [D4|DT]) :-
                place_queens(0, [Q1,Q2,Q3,Q4], [U1,U2,U3,U4|UT], DT),
                %% ---
                place_queen(1, [Q1,Q2,Q3,Q4], [U2,U3,U4|UT], DT),
            place_queen(2, [Q1,Q2,Q3,Q4], [U3,U4|UT], [D4|DT]),
        place_queen(3, [Q1,Q2,Q3,Q4], [U4|UT], [D3,D4|DT]),
    place_queen(4, [Q1,Q2,Q3,Q4], UT, [D2,D3,D4|DT]).

(выше не код Пролога, это иллюстрация, показывающая структуру вызова.)

Таким образом, place_queens делает две вещи:

1. «разворачивает» список подъемов [U1, U2, U3, U4|_] и падений [D1, D2, D3, D4|_];и
2. он вызывает place_queen с определенным значением и определенными частями списка взлетов и падений.

Задача place_queen - заполнить столбец I где-то в списке.Он всегда получает полный список позиций ферзя [Q1, Q2, Q3, Q4] и части списка взлетов и падений.Эти взлеты и падения представляют диагонали, движущиеся в направлении вверх и вниз.

В случае, если мы заполняем значение для данной позиции ферзя, мы также отмечаем это значение для данного списка взлетов и падений и, таким образом, "утверждаем"«эти диагонали для этой королевы.Если мы ведем бухгалтерский учет должным образом, этого достаточно, поскольку, если другая королева хочет занять место, которое находится на диагонали, которая уже заявлена, она стремится привязать это значение к соответствующей диагонали, но это не удастся, поскольку ее значение отличается отуже присвоенное значение.

Покажем это на примере.Когда мы вызываем первый place_queen(1, [Q1, Q2, Q3, Q4], [U2, U3, U4|_], _), мы можем назначить эту первую позицию, это базовый регистр, поэтому это приводит к тому, что:

place_queen(1,[Q1,Q2,Q3,Q4],[U2,U3,U4|_], _D) :-
    Q1 = 1,
    U2 = 1,
    _D = [1|_].

, что означает, что теперь наш [Q1, Q2, Q3, Q4] выглядиткак [1, Q2, Q3, Q4], для диагоналей вверх это выглядит как [U1, U2, U3, U4|_] = [U1, 1, U3, U4|_], а для [D1, D2, D3, D4|_] = [D1, D2, D3, D4, 1|_].

Теперь мы стремимся назначить следующие place_queen(2, [1,Q2,Q3,Q4],[U3,U4|_], [D4, 1|_]).Мы знаем, что не можем присвоить это значение первому элементу списка Q, так как это значение занято 1, и, следовательно, это будет означать, что две королевы имеют одинаковый столбец и атакуют друг друга, так что это не будетработа.

Таким образом, мы выполняем рекурсию, и таким образом мы выталкиваем списки вверх и вниз , поэтому:

place_queen(2, [1,Q2,Q3,Q4], [U3,U4|UT], [D4, 1|DT]) :-
    place_queen(2, [Q2,Q3,Q4], [U4|UT], [1|DT]).

Итак, теперь мыстремитесь поставить ферзь для второй строки во втором столбце доски, но опять возникает проблема: диагональ этого квадрата уже заявлена, опять же королевой 1, мы можем получить тот факт, что вниз имеет [1|_].Итак, снова мы должны выполнить рекурсию, например:

place_queen(2, [1,Q2,Q3,Q4], [U4|UT], [1|DT]) :-
    place_queen(2, [Q3,Q4], UT, DT).

Здесь мы можем безопасно разместить королеву, здесь ни один из списков не блокирует.Поэтому, когда мы делаем это, списки теперь выглядят как [Q1, Q2, Q3, Q4] = [1, Q2, 2, Q4], [U1, U2, U3, U4|_] = [U1, 1, U3, U4, 2|_] и [D1, D2, D3, D4|_] = [D1, D2, D3, D4, 1, 2|_].Если мы посмотрим на доску, которую мы назначили, диагонали действительно имеют смысл:

 \D5 \D6 \D7 \ D8\
  +---+---+---+---+
 /| Q |   |   |   |
U2+---+---+---+---+
 /|   |   | Q |   |
U3+---+---+---+---+
 /|   |   |   |   |
U4+---+---+---+---+
 /|   |   |   |   |
  +---+---+---+---+
  U5 /U6 /U7 / U8/

Итак, как мы видим, первая королева заявляет D5 и U2, а вторая королева заявляет D6и U5.

Теперь мы можем разместить третью ферзя на доске, или, по крайней мере, мы можем попытаться это сделать, поэтому мы делаем вызов с place_queen(3,[1,Q2,2,Q4],[U4,2|_],[D3,D4,1,2|_]).

Здесь мыне сможет разместить его в первом столбце (так как он занят ферзем 1), не сможет поместить его во второй столбец (диагональ вверх утверждается королевой 2), третий столбец (столбец заняткоролева 2 и диагональ вниз утверждается королева 1), и последний столбец (диагональ вниз утверждается королева 2).В конце концов мы исчерпали список Q, поэтому нам придется вернуться назад к назначению предыдущей королевы.

Так что теперь мы продолжаем размещать вторую королеву, единственный оставшийся вариант, это поместить ее впоследний столбец:

 \D5 \D6 \D7 \ D8\
  +---+---+---+---+
 /| Q |   |   |   |
U2+---+---+---+---+
 /|   |   |   | Q |
U3+---+---+---+---+
 /|   |   |   |   |
U4+---+---+---+---+
 /|   |   |   |   |
  +---+---+---+---+
  U5 /U6 /U7 / U8/

В этом случае [Q1, Q2, Q3, Q4] = [1, Q2, Q3, 2], [U1, U2, U3, U4|_] = [U1, 1, U3, U4, U5, 2|_] и [D1, D2, D3, D4|_] = [D1, D2, D3, D4, 1, D6, 2|_].Итак, теперь вопрос в том, куда поставить следующую королеву (queen 3):

мы снова можем назначить третью ферзь и, таким образом, теперь вызываем предикат с place_queen(3,[1,Q2,Q3,2],[U4,U5,2|_],[D3,D4,1,D6,2|_]).Мы не можем назначить эту ферзь первому местоположению, поскольку ферзь 1 занимает этот столбец, поэтому мы рекурсивно вызываем его с помощью place_queen(3,[Q2,Q3,2],[U5,2|_],[D4,1,D6,2|_]).Здесь нет проблем, чтобы поставить ферзь, так как глава всех трех списков является свободной переменной.Таким образом, мы устанавливаем Q2 = U5 = D4 = 3 и получаем следующую доску:

 \D5 \D6 \D7 \ D8\
  +---+---+---+---+
 /| Q |   |   |   |
U2+---+---+---+---+
 /|   |   |   | Q |
U3+---+---+---+---+
 /|   | Q |   |   |
U4+---+---+---+---+
 /|   |   |   |   |
  +---+---+---+---+
  U5 /U6 /U7 / U8/

Так что теперь наши списки выглядят как [Q1, Q2, Q3, Q4] = [1, 3, Q3, 2], [U1, U2, U3, U4|_] = [U1, 1, U3, U4, 3, 2|_] и [D1, D2, D3, D4|_] = [D1, D2, D3, 3, 1, D6, 2|_].Теперь мы можем в конечном итоге назначить последнюю ферзь на доску, поэтому мы называем place_queen/4 с place_queen(4,[1,3,Q3,2],[3,2|_],[D2,D3,3,1,D6,2|DT])..Первые два места отклонены (заняты как по столбцу, так и по диагонали вверх), поэтому после двух рекурсивных вызовов мы получим place_queen(4,[Q3,2],_,[3,1,D6,2|DT]), но это занято queen 3 (вниз по диагонали), действительно, ситуациявыглядит следующим образом:

 \D5 \D6 \D7 \ D8\
  +---+---+---+---+
 /| Q |   |   |   |
U2+---+---+---+---+
 /|   |   |   | Q |
U3+---+---+---+---+
 /|   | Q |   |   |
U4+---+---+---+---+
 /|   |   | Q |   |
  +---+---+---+---+
  U5 /U6 /U7 / U8/

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

 \D5 \D6 \D7 \ D8\
  +---+---+---+---+
 /|   | Q |   |   |
U2+---+---+---+---+
 /|   |   |   | Q |
U3+---+---+---+---+
 /| Q |   |   |   |
U4+---+---+---+---+
 /|   |   | Q |   |
  +---+---+---+---+
  U5 /U6 /U7 / U8/

Тогда списки будут выглядеть как Qs = [3, 1, 4, 2], U = [1, 3, _, 2, 4|_] и D = [_, _, 3, 4_, 1, 2|_].

Итак, мы можем заключитьчто значения в верхнем и нижнем списках не имеют отношения к себе, это используется для предотвращения присвоения другого номера (королевы) на этих диагоналях.

Answer 4

В качестве промежуточного шага к пониманию исходной программы вы можете рассмотреть следующее, основанное на той же основной идее. Существует переменная для

• каждый из N рядов
• каждая из 2 * N-1 верхних диагоналей
• каждая из 2 * N-1 нисходящих диагоналей

Эти переменные создаются с номером столбца ферзя, который занимает соответствующее место на доске (потому что каждая ферма охватывает столбец, строку, диагональ вверх и диагональ вниз).

Вместо умного манипулирования списком в оригинальной программе, этот использует "массивы" для строк и диагоналей, и, вероятно, легче понять:

queens(N, Rows) :-
    NDiag is 2*N-1,
    functor(Rows,  array, N),           % create the "arrays"
    functor(Ups,   array, NDiag),
    functor(Downs, array, NDiag),
    place_queen(1, N, Rows, Ups, Downs).

place_queen(C, N, Rows, Ups, Downs) :-
    ( C>N ->
        true
    ;
        between(1, N, R),
        arg(R, Rows, C),                % place column C queen in row R
        U is C-R+N, arg(U, Ups, C),     % ... and up-diagonal C-R+N
        D is C+R-1, arg(D, Downs, C),   % ... and down-diagonal C+R-1
        C1 is C+1,
        place_queen(C1, N, Rows, Ups, Downs)
    ).

Answer 5

Поняв программу благодаря предыдущим хорошим ответам, я стараюсь дать более декларативное объяснение.Автором программы является Том Фрювирт (спасибо Jschimpf за информацию).
Я цитирую выдержку из его сообщения , опубликованного на comp.lang.prolog:

Исходя из того, что никакие две королевы не могут быть расположены в одном ряду, столбце или диагонали, мы помещаем только одну ферзь в каждую строку.Следовательно, мы можем идентифицировать королеву по номеру строки.Теперь представьте, что шахматная доска разделена на три слоя, один из которых предназначен для атак на колонны, а два - для диагоналей, идущих вверх и вниз соответственно.Мы указываем, что поле атаковано королевой, указав там номер ферзя.Теперь мы решаем проблему, рассматривая по одной строке за раз, помещая одну ферзь в столбец и два диагональных слоя.Для следующей строки / ферзя мы используем тот же слой столбцов, чтобы получить новые диагонали вверх, нам нужно переместить слой на одно поле вверх, для диагоналей вниз мы переместим поле на один слой вниз.

Его программа:

% -------- Meaning of Variables ------
% N, M  ... Size of the board
% I, J  ... Number of the row current queen is on
% Qs, L ... List of length N used to represent the solution
% Cs ... Column as a list of fields of length N
% Us ... Up-Diagonal as an open list of fields
% Ds ... Down-Diagonal as an open list of fields


queens(N,Qs):- gen_list(N,Qs), place_queens(N,Qs,_,_).

gen_list(0,[]).
gen_list(N,[_|L]):-
        N>0, M is N-1,
        gen_list(M,L).

place_queens(0,_,_,_).
place_queens(I,Cs,Us,[_|Ds]):-
        I>0, J is I-1,
        place_queens(J,Cs,[_|Us],Ds),
        place_queen(I,Cs,Us,Ds).

% place_queen(Queen,Column,Updiagonal,Downdiagonal) places a single queen
place_queen(I,[I|_],[I|_],[I|_]).
place_queen(I,[_|Cs],[_|Us],[_|Ds]):-
                place_queen(I,Cs,Us,Ds).

Давайте вернемся к вопросу.Давайте сделаем проблему проще.Давайте просто рассмотрим строки, столбцы и верхние диагонали.

queens(N,Qs) :-
    length(Qs,N),
    place_queens(N,Qs,_).

place_queens(0,_,_).    
place_queens(I,Qs,Ups) :-
    I > 0,
    I1 is I-1,
    place_queens(I1,Qs,[_|Ups]),
    place_queen(I,Qs,Ups).

place_queen(Q,[Q|_],[Q|_]).
place_queen(Q,[_|Qs],[_|Ups]):-
    place_queen(Q,Qs,Ups).

?- queens(3,L).
L = [1, 2, 3];        
L = [3, 1, 2];       % row 3/col 1 -- row 1/col 2 -- row 2/col 3
L = [2, 3, 1];
false

Шахматная доска стороны 3 с верхними диагоналями:

    C1  C2  C3
    |   |   |     Row
  +---+---+---+
U1| / | / | / |-- 1
  +---+---+---+
U2| / | / | / |-- 2
  +---+---+---+
U3| / | / | / |-- 3
  +---+---+---+
   U3  U4  U5

и предикатом, который связывает строки / королевы,списки столбцов / королев и списки восходящих диагоналей / королев:

row_col_ups(1, [ 1,C2,C3], [ 1,U2,U3,U4,U5]). % row 1
row_col_ups(1, [C1, 1,C3], [U1, 1,U3,U4,U5]).
row_col_ups(1, [C1,C2, 1], [U1,U2, 1,U4,U5]).

row_col_ups(2, [ 2,C2,C3], [U1, 2,U3,U4,U5]). % row 2
row_col_ups(2, [C1, 2,C3], [U1,U2, 2,U4,U5]).
row_col_ups(2, [C1,C2, 2], [U1,U2,U3, 2,U5]).

row_col_ups(3, [ 3,C2,C3], [U1,U2, 3,U4,U5]). % row 3
row_col_ups(3, [C1, 3,C3], [U1,U2,U3, 3,U5]).
row_col_ups(3, [C1,C2, 3], [U1,U2,U3,U4, 3]).

Рассмотрим предикат place_queen / 3 :

% place_queen(Q,Cols,Ups)
% Q    -> queen/row
% Cols -> list of colunms/queens
% Ups  -> open list of up-diagonals/queens

place_queen(Q,[Q|_],[Q|_]).
place_queen(Q,[_|Qs],[_|Ups]):-
    place_queen(Q,Qs,Ups).

Он имеет ту же структурукак member / 2 :

member(X,[X|_]).
member(X,[_|L]):-
    member(X,L).

?- member(3,[1,2,3]).
true.
?- member(X,[1,2]).
X = 1;
X = 2.

Но он используется необычным образом:

?- L=[1,2,X,4], member(3,L).
L = [1, 2, 3, 4],
X = 3

?- member(3,L).
L = [3|_1388];
L = [_1178, 3|_1186];
L = [_1178, _1184, 3|_1192];

Итак, place_queen ищетпустой квадрат, если он существует, где поставить Королеву.

?- Col=[C1,C2,C3], place_queen(3,Col,UPS).
Col = [3, C2, C3],
UPS = [3|_]

?- Col=[C1,C2,C3], place_queen(1,Col,UPS), UPS2=[U2|UPS], place_queen(2,Col,UPS2).
Col = [3, C2, 2],
UPS = [3, 2|_],
UPS2 = [U2, 3, 2|_]

?- Col=[C1,C2,C3], place_queen(3,Col,UPS), UPS2=[U2|UPS], place_queen(2,Col,UPS2), UPS3=[U1|UPS2], place_queen(1,Col,UPS3).
Col = [3, 1, 2],
UPS = [3, 2|_],
UPS2 = [1, 3, 2|_],
UPS3 = [U1, 1, 3, 2|_]

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

place_queens(0,_Qs,_Ups,_Downs). % usually pred(0,[],[],[]) for closed list
                                 % but with open-lists we have the variables.

place_queens(I,Qs,Ups,[_|Downs]) :-
    I > 0, I1 is I-1,
    place_queens(I1,Qs,[_|Ups] ,Downs), %  in next row/queen 
    place_queen(I,Qs,Ups,Downs).        %  for the up-diagonals we move the layer
                                        %  one field up.
                                        %  for the down-diagonals we move the layer
                                        %  one field down.

---

PS Предикат, который связывает строки / королевы, списки столбцов / королев и списки нисходящих диагоналей / королевна шахматной доске стороны 3:

row_col_downs(1, [ 1,C2,C3], [D1,D2, 1,D4,D5]).
row_col_downs(1, [C1, 1,C3], [D1,D2,D3, 1,D5]).
row_col_downs(1, [C1,C2, 1], [D1,D2,D3,D4, 1]).

row_col_downs(2, [ 2,C2,C3], [D1, 2,D3,D4,D5]).
row_col_downs(2, [C1, 2,C3], [D1,D2, 2,D4,D5]).
row_col_downs(2, [C1,C2, 3], [D1,D2,D3, 2,D5]).

row_col_downs(3, [ 3,C2,C3], [ 3,D2,D3,D4,D5]).
row_col_downs(3, [C1, 3,C3], [D1, 3,D3,D4,D5]).
row_col_downs(3, [C1,C2, 3], [D1,D2, 3,D4,D5]).

PPS. Том Фрювирт приводит две другие версии программы, одна из которых на чистом прологе:

% Pure version with successor function

queensp(N,Qs):- gen_listp(N,Qs), place_queensp(N,Qs,_,_).

gen_listp(0,[]).
gen_listp(s(N),[_|L]):-
        gen_listp(N,L).

place_queensp(0,_,_,_).
place_queensp(s(I),Cs,Us,[_|Ds]):-
        place_queensp(I,Cs,[_|Us],Ds),
        place_queen(s(I),Cs,Us,Ds).

place_queen(I,[I|_],[I|_],[I|_]).
place_queen(I,[_|Cs],[_|Us],[_|Ds]):-
        place_queen(I,Cs,Us,Ds).

?- queensp(Q,L).
L = [],
Q = 0 ;
L = [s(0)],
Q = s(0) ;
L = [s(s(s(0))), s(0), s(s(s(s(0)))), s(s(0))],
Q = s(s(s(s(0))))