Поскольку вы не предоставили ни одного примера запросов, начните с нескольких примеров запросов, чтобы определить параметры и формат вывода.Обычно для определения параметров и формата вывода для неизвестного кода требуется просмотреть код структуры аргументов, а затем попробовать примеры запросов.Кроме того, обратите внимание, что в этом коде используется программирование логики ограничений библиотека clpfd ;когда я читаю это, я буквально перестаю думать синтаксическое объединение и начинаю думать ограничения .Я думаю, что это отдельная система, встроенная в Пролог, а не дополнительные предикаты.Вы заметите, что в этом ответе constraint используется очень часто, а predicate или rule совершенно отсутствует, хотя это пролог.
Поскольку проблема N-Куинса так хорошо известна какЛогическая проблема: быстрый поиск в Google ( clpfd n queens ) обнаруживает SWI-Prolog Пример: головоломка «Восемь королев» .Обратите внимание на добавление ключевого слова clpfd, которое крайне важно для понимания этого варианта кода;в других языках программирования много решений.
Это пример запроса n_queens(8, Qs), label(Qs), для которого label / 1 возвращает значения для сгенерированных системой переменных.Это также говорит нам, что первый аргумент является положительным целым числом, а второй аргумент является списком длины первого аргумента.Также, работая с этой проблемой ранее, первым аргументом является размерный размер доски, поэтому 1 - это доска 1x1, 8 - доска 8x8 и т. Д., А также число ферзей, которые будутбыть на доске.
Следующее, что помогает, - это знать, какие есть действительные решения или хотя бы их количество для набора параметров.
Статья из Википедии для Пазл «Восемь королев» предусматривает, что в разделе подсчет решений .Это показывает, что для платы 1x1 есть одно решение, для платы 2x2 или 3x3 нет решений, два решения для 4x4 и т. Д.
Для платы 1x1 есть одно решение.
?- n_queens(1,Qs),label(Qs).
Qs = [1].
Для платы 2x2 решения не существует.
?- n_queens(2,Qs),label(Qs).
false.
Для платы 4x4 есть два решения.
?- n_queens(4,Qs),label(Qs).
Qs = [2, 4, 1, 3] ;
Qs = [3, 1, 4, 2] ;
false.
Qs = [2, 4, 1, 3]
Для интерпретации результатов позиции в списке соответствуют столбцам на доске и значениям со строкой на доске, поэтому для первого значенияв списке (2) читается a queen in row 2, column 1, для второго значения в списке (4) читается a queen in row 4, column 2
Qs = [3, 1, 4, 2]
Примечание. Изображения, сгенерированные с использованием Настройка шахматной диаграммы
Если мы запустим запрос со значениями в качестве переменных, результатом будет бесконечный парад действительных ответов.
?- n_queens(N,Qs),label(Qs).
N = 0,
Qs = [] ;
N = 1,
Qs = [1] ;
N = 4,
Qs = [2, 4, 1, 3] ;
N = 4,
Qs = [3, 1, 4, 2] ;
N = 5,
Qs = [1, 3, 5, 2, 4] ;
N = 5,
Qs = [1, 4, 2, 5, 3] ;
N = 5,
Qs = [2, 4, 1, 3, 5] ;
N = 5,
Qs = [2, 5, 3, 1, 4] ;
N = 5,
Qs = [3, 1, 4, 2, 5] ;
N = 5,
Qs = [3, 5, 2, 4, 1] ;
N = 5,
Qs = [4, 1, 3, 5, 2]
...
Теперь, когда мы знаем, что код работает и дает правильные решения, мы можем начать его анализировать.
Обычно SWI-Prolog trace / 0 или SWI-PRolog GUI-tracer , начатый с gtrace/0, будет предпочтительным инструментом, но, если я знаю, что использовал его на clpfd, я не знаю, что это лучший инструмент с Constraint Logic Programming.Попробуйте, и вы поймете, почему.
Вкл. С рассечением.
?- n_queens(1,Qs).
Qs = [1].
?- n_queens(2,Qs).
Qs = [_1942, _1948],
_1942 in 1..2,
abs(_1942-_1948)#\=1,
_1942#\=_1948,
_1948 in 1..2.
Это что-то интересное.
Чтобы упростить понимание, поменяйте местами сгенерированную системупеременные с дружественными к пользователю переменными и дают человеческое прочтение смысла оператора.
?- n_queens(2,Qs).
Qs = [A, B],
A in 1..2,
abs(A-B)#\=1,
A#\=B,
B in 1..2.
Обратите внимание, что с операторами CLP (FD) с # обычно являются ограничениями, например # \= и # = читаются как обычные операторы, за исключением #
`A in 1..2` reads the value for `A` must be in the range `1..2`
`abs(A-B)#\=1` reads the difference of the values between `A` and `B` must not equal 1
`A#\=B` reads the value of `A` must not equal the value of `B`
`B in 1..2` reads the value of `B` must be in `1..2`
Так что это всего лишь набор ограничений.Если вы попытаетесь решить ограничения вручную, вы обнаружите, что решения не существует, например,
0,_ invalid by `A in 1..2`
_,0 invalid by `B in 1..2`
3,_ invalid by `A in 1..2`
_,3 invalid by `B in 1..2`
1,1 invalid by `A#\=B`
1,2 invalid by `abs(A-B)#\=1`
2,1 invalid by `abs(A-B)#\=1`
2,2 invalid by `A#\=B`
То же самое для доски 4х4
?- n_queens(4,Qs).
Qs = [_5398, _5404, _5410, _5416],
_5398 in 1..4,
abs(_5398-_5416)#\=3,
_5398#\=_5416,
abs(_5398-_5410)#\=2,
_5398#\=_5410,
abs(_5398-_5404)#\=1,
_5398#\=_5404,
_5416 in 1..4,
abs(_5410-_5416)#\=1,
_5410#\=_5416,
abs(_5404-_5416)#\=2,
_5404#\=_5416,
_5410 in 1..4,
abs(_5404-_5410)#\=1,
_5404#\=_5410,
_5404 in 1..4.
?- n_queens(4,Qs).
Qs = [A, B, C, D],
A in 1..4, reads the value for `A` must be in the range `1..4`
abs(A-D)#\=3, reads the difference of the values between `A` and `D` must not equal 3
A#\=D, reads the value of `A` must not equal the value of `D`
abs(A-C)#\=2, reads the difference of the values between `A` and `C` must not equal 2
A#\=C, reads the value of `A` must not equal the value of `C`
abs(A-B)#\=1, reads the difference of the values between `A` and `B` must not equal 1
A#\=B, reads the value of `A` must not equal the value of `B`
D in 1..4, reads the value for `D` must be in the range `1..4`
abs(C-D)#\=1, reads the difference of the values between `C` and `D` must not equal 1
C#\=D, reads the value of `C` must not equal the value of `D`
abs(B-D)#\=2, reads the difference of the values between `B` and `D` must not equal 2
B#\=D, reads the value of `B` must not equal the value of `D`
C in 1..4, reads the value for `C` must be in the range `1..4`
abs(B-C)#\=1, reads the difference of the values between `B` and `C` must not equal 1
B#\=C, reads the value of `B` must not equal the value of `C`
B in 1..4. reads the value for `B` must be in the range `1..4`
Это немного, но с учетом логики мы можем переставить утверждения, и значение будет одинаковым.
Таким образом, группировка похожих операторов, сортировка по переменным, затем упорядочение групп по простоте дает
`A in 1..4` reads the value for `A` must be in the range `1..4`
`B in 1..4` reads the value for `B` must be in the range `1..4`
`D in 1..4` reads the value for `D` must be in the range `1..4`
`C in 1..4` reads the value for `C` must be in the range `1..4`
`A#\=B` reads the value of `A` must not equal the value of `B`
`A#\=C` reads the value of `A` must not equal the value of `C`
`A#\=D` reads the value of `A` must not equal the value of `D`
`B#\=C` reads the value of `B` must not equal the value of `C`
`B#\=D` reads the value of `B` must not equal the value of `D`
`C#\=D` reads the value of `C` must not equal the value of `D`
`abs(A-B)#\=1` reads the difference of the values between `A` and `B` must not equal 1
`abs(A-C)#\=2` reads the difference of the values between `A` and `C` must not equal 2
`abs(A-D)#\=3` reads the difference of the values between `A` and `D` must not equal 3
`abs(B-C)#\=1` reads the difference of the values between `B` and `C` must not equal 1
`abs(B-D)#\=2` reads the difference of the values between `B` and `D` must not equal 2
`abs(C-D)#\=1` reads the difference of the values between `C` and `D` must not equal 1
Теперь объясним ограничения и покажем, как они относятся к королевам на квадратной доске;Заметьте, я говорю квадратная доска, а не шахматная доска, потому что шахматная доска имеет размер 8x8, и этот код работает с квадратными досками разных размеров.
A in 1..4
Означает, что королева Aдолжен быть размещен в позиции на доске 4х4.Работая с проблемами с ограничениями, вы часто обнаруживаете, что то, что мы, люди, считаем само собой разумеющимся или думаем о здравом смысле, нужно воспринимать как конкретные ограничения, это именно тот случай.Также понимание того, что добавление правил для здравого смысла, иногда является одной из самых сложных задач при создании ИИ-решений.Хотя я не могу найти ссылку, когда создатели Cyc добавляли правила, концепция времени отнимала много времени, чтобы понять правильно (не каламбур).Остальные ограничения, такие как A in 1..4, просто гарантируют, что никакая ферзь не будет помещена в позицию вне доски.
A#\=B
Чтобы лучше понять это ограничение, давайте сделаем картинус доской 4x4 и белыми ферзями в качестве допустимой позиции и черной королевой в качестве недопустимой позиции, определенной ограничением.
То есть Aбелая королева в строке 1, а B черная королева в строке 1. Поскольку A не может быть равным B, это говорит о том, что если queen A находится в строке 1, то ферзь B не может быть в строке 1. Asправило используется с переменными, это означает, что для любой строки ферзь A находится в королеве B и не может быть в этой строке.Остальные ограничения, такие как A#\=B, просто гарантируют, что никакие две королевы не могут быть в одной строке.
Думайте об этом ограничении как о горизонтальной атаке для королевы.
abs(A-B)#\=1
Чтобы лучше понять это ограничение, давайте создадим изображение с доской 4x4 и белыми ферзями в качестве допустимой позиции и черной королевы в качестве недопустимой позиции, как определено ограничением.
Естьчетыре позиции для A 1,2,3,4, но поскольку правило симметрично по горизонтали (1 - это то же самое, что 4, а 2 - это то же самое, что и 3), я сделаю только два из них.
Когда A равно 1.
Поскольку A равно 1, B не может быть 2.
1-2 = -1
ABS(-1) = 1
1 can not equal 1.
Когда A равно 2.
Поскольку A равно 2, B не может быть 1.
2 - 1 = 1
ABS(1) = 1
1 can not equal 1.
Поскольку A равно 2, B не может быть 3.
2 - 3 = -1
ABS(-1) = 1
1 can not equal 1.
Если проверяется ограничение, использующее Queen A и Queen D
abs(A-D)#\=3
Когда A равно 1.
Поскольку A равно 1, D не может быть 4.
1-4 = -3
ABS(-3) = 3
3 can not equal 1.
Когда A равно 2.
Поскольку A равно 2, D может быть 1.
2-1 = 1
ABS(1) = 1
1 can not equal 3.
Поскольку A равно 2, D может быть 2.
2-2 = 0
ABS(0) = 0
0 can not equal 3.
Поскольку A равно 2, D может быть 3.
2-3 = -1
ABS(-1) = 1
1 can not equal 3.
Поскольку A равно 2, D может быть 4.
2-4 = -2
ABS(-2) = 2
2 can not equal 3.
Думайте об этом ограничении как о диагональной атаке на королеву.
Но подождите минуту, королева может двигаться горизонтально, вертикально и по диагонали, где находится ограничение дляперемещение по вертикали?
Хотя это не отображается как ограничение в выходных данных из примера запроса, есть ограничение.До сих пор у нас есть ограничения, которые ограничивают положение ферзей до нахождения на доске, горизонтальную атаку и диагональную атаку как отдельные ограничения, однако структура данных, список длины N также является ограничением, ([A,B,C,D]) и ограничивает королеву A первым столбцом, королеву B вторым столбцом и т. д.Опять же, это одна из точек обучения программированию в искусственном интеллекте: то, как мы думаем, как люди, не всегда напрямую приводит к решению проблемы с компьютером.Поэтому, хотя этот код использует ограничения для решения проблемы, он также использует структуру данных.
Думайте о списке как о нападении на столбца для королевы.
В одном столбце не может быть двух королев, и это ограничено тем фактом, что в скалярной переменной не может быть двух значений.
На этом этапе многие из вас распознают оставшуюся часть кода как вспомогательный и рекурсивный предикат safe_queens/1 и как рекурсивный предикат safe_queens/3.
safe_queens([], _, _).
safe_queens([Q|Qs], Q0, D0) :-
Q0 #\= Q,
abs(Q0 - Q) #\= D0,
D1 #= D0 + 1,
safe_queens(Qs, Q0, D1).
Это стандартный рекурсивный вызов для обработки списка, например
safe_queens([], _, _).
safe_queens([H|T], _, _) :-
% Process head of list (H)
safe_queens(T, _, _). % Process tail of list (T)
Эти два оператора
Q0 #\= Q
abs(Q0 - Q) #\= D0
объясненывыше
и
D1 #= D0 + 1
устанавливает D1 на D0 + 1
Если мы изменим предикат как таковой
permutations([], _, _).
permutations([Q|Qs], Q0, D0) :-
write(Q0),write('#\\='),writeln(Q),
write('abs('),write(Q0),write('-'),write(Q),write(')#\\='),writeln(D0),
D1 is D0 + 1,
permutations(Qs, Q0, D1).
и запустим этиВ запросах мы видим, что он генерирует некоторые из ограничений
?- permutations(['B','C','D'],'A',1).
A#\=B
abs(A-B)#\=1
A#\=C
abs(A-C)#\=2
A#\=D
abs(A-D)#\=3
true.
?- permutations(['C','D'],'B',1).
B#\=C
abs(B-C)#\=1
B#\=D
abs(B-D)#\=2
true.
?- permutations(['D'],'C',1).
C#\=D
abs(C-D)#\=1
true.
safe_queens([]).
safe_queens([Q|Qs]) :-
safe_queens(Qs, Q, 1),
safe_queens(Qs).
Это стандартный рекурсивный вызов для обработки списка, например
safe_queens([]).
safe_queens([H|T]) :-
% Process head of list (H)
safe_queens(T). % Process tail of list (T)
, а также помощникдля safe_queens/3 потому что это утверждение
safe_queens(Qs, Q, 1)
инициализирует третий аргумент для safe_queens/3 до 1
Если мы изменимy предикат как таковой
generate_args([]).
generate_args([Q|Qs]) :-
write('Qs: '),write(Qs),write(', Q: '),write(Q),writeln(', 1'),
generate_args(Qs).
и запустив этот запрос, мы увидим, что он генерирует аргументы, необходимые для safe_queens/3
?- generate_args(['A','B','C','D']).
Qs: [B,C,D], Q: A, 1
Qs: [C,D], Q: B, 1
Qs: [D], Q: C, 1
Qs: [], Q: D, 1
true.
Однако в своем вопросе вы не задавалио первом предикате
n_queens(N, Qs) :-
length(Qs, N),
Qs ins 1..N,
safe_queens(Qs).
, который имеет
length(Qs,N)
, который генерирует список длины N с несвязанными переменными
[A,B,C,D]
и имеет критический оператор ограничения
Qs ins 1..N
, который генерирует ограничения типа
A in 1..4
Теперь решающее отличие, добавленное к запросу
labels(Qs)
Если вы используете графический интерфейс пользователя SWI-Prolog и запустите код до конца n_queens/2, вы увидите в отладчикесписок ограничений, но не решение
, потому что эти предикаты генерируют ограничения, которые поддерживаются внутренне, только когда вызывается labels/1что ограничения решаются для получения результата.