Я думаю, что как «низко висящий фрукт», мы можем обеспечить, чтобы никакие две королевы не были в одном столбце (учитывая, что в каждом поколении мы определяем положение следующего ряда), динамически уменьшая «домен».Это означает, что мы (а) никогда не приведем ситуацию, когда две королевы находятся в одном столбце;и (b) мы также можем повысить производительность, поскольку нам больше не нужно это проверять.
Таким образом, мы, например, можем начать со списка возможных столбцов, таких как [1, 2, 3, 4].Если мы выберем 2 для первой королевы, мы передадим список [1, 3, 4] рекурсивному вызову, и независимо от того, что выберет рекурсивный вызов, мы знаем, что это не может быть тот же столбец.Для этого нам нужен предикат, который выбирает элемент и в то же время выдает список, в котором мы удалили этот элемент, например:
pick_rem([H|T], H, T).
pick_rem([H|T], P, [H|R]) :-
pick_rem(T, P, R).
. Затем будет сгенерировано:
?- pick_rem([1,2,3], P, R).
P = 1,
R = [2, 3] ;
P = 2,
R = [1, 3] ;
P = 3,
R = [1, 2] ;
false.
Дополнительным бонусом является то, что если список пуст, мы уже знаем, что достигли конца доски, и, таким образом, мы нашли правильное решение.Таким образом, завершение можно проверить с помощью простого сопоставления с образцом вместо числового сравнения индекса.
Нам также нужен предикат, который генерирует диапазон, например:
range(X, Y, []) :-
X > Y.
range(X, Y, [X|T]) :-
X =< Y,
X1 is X + 1,
range(X1, Y, T).
Что касается проверки того, что ферзяне атакуйте по диагонали, мы можем построить предикат, который принимает два числа и каждый раз обновляет два, например:
not_attack([], _, _).
not_attack([H|T], C, D) :-
\+ H is C + D,
\+ H is C - D,
D1 is D+1,
not_attack(T, C, D1).
Таким образом, мы должны отслеживать позиции королев, и это в «обратном направлении»."order (поэтому ближайшая строка является заголовком этого списка).
Так что теперь мы можем объединить это вместе в предикат генерирования:
gen([], _, []).
gen(Dom, Old, [C|Res]) :-
pick_rem(Dom, C, Dom1),
not_attack(Old, C, 1),
gen(Dom1, [C|Old], Res).
Здесь первый параметр - это домен, который«сжимает» каждый рекурсивный вызов одним элементом, второй элемент представляет собой список, который строится из столбцов ферзей, которые мы помещаем на доску.Наконец, последний параметр будет «конструировать» позиции доски.
Так что теперь нам нужно только обернуть этот предикат некоторой логикой в более удобную:
to_pos(R, C, pos(R, C)).
n_queens(N, Sol) :-
range(1, N, Dom),
gen(Dom, [], Res),
maplist(to_pos, Dom, Res, Sol).
Затем генерируется N -критические решения для N = 4 и N = 5 довольно эффективно:
?- n_queens(4, S).
S = [pos(1, 2), pos(2, 4), pos(3, 1), pos(4, 3)] ;
S = [pos(1, 3), pos(2, 1), pos(3, 4), pos(4, 2)] ;
false.
?- n_queens(5, S).
S = [pos(1, 1), pos(2, 3), pos(3, 5), pos(4, 2), pos(5, 4)] ;
S = [pos(1, 1), pos(2, 4), pos(3, 2), pos(4, 5), pos(5, 3)] ;
S = [pos(1, 2), pos(2, 4), pos(3, 1), pos(4, 3), pos(5, 5)] ;
S = [pos(1, 2), pos(2, 5), pos(3, 3), pos(4, 1), pos(5, 4)] ;
S = [pos(1, 3), pos(2, 1), pos(3, 4), pos(4, 2), pos(5, 5)] ;
S = [pos(1, 3), pos(2, 5), pos(3, 2), pos(4, 4), pos(5, 1)] ;
S = [pos(1, 4), pos(2, 1), pos(3, 3), pos(4, 5), pos(5, 2)] ;
S = [pos(1, 4), pos(2, 2), pos(3, 5), pos(4, 3), pos(5, 1)] ;
S = [pos(1, 5), pos(2, 2), pos(3, 4), pos(4, 1), pos(5, 3)] ;
S = [pos(1, 5), pos(2, 3), pos(3, 1), pos(4, 4), pos(5, 2)] ;
false.
На моей машине это работает довольнодействует до N = 19 .Выше, конечно, не идеально .Можно подумать о некоторой эвристике и т. Д., Чтобы выбрать лучшие позиции, или заранее увидеть, что определенные паттерны потерпят неудачу.Прямо сейчас мы прекращаем поиск ветви только в том случае, если нет возможности разместить ферзя на доске.Но иногда комбинация некоторых ферзей никогда не может привести к хорошим результатам позже, и такие шаблоны могут быть добавлены, чтобы избежать исчерпывающего поиска в ветви.