удалить( U, Du, Du1), % Ее удаление
V is X+Y % Соответствующая диагональ вниз
удалить( V, Dv, Dv1), % Ее удаление
реш( СписY, Dх1, Dy1, Du1, Dv1).
% Выбор из оставшихся значений
удалить( А, [А | Список], Список).
удалить(A, [В | Список ], [В | Список1 ] ) :-
удалить( А, Список, Список1).
Рис. 4. 11. Программа 3 для задачи о восьми ферзях.
задачи о восьми ферзях.
Процедура реш универсальна в том смысле, что ее можно использовать для решения задачи об N ферзях (на доске размером N х N). Нужно только правильно задеть области Dx, Dy и т.д.
Удобно автоматизировать получение этих областей. Для этого нам потребуется процедура
генератор( Nl, N2, Список)
которая для двух заданных целых чисел Nl и N2 порождает список
Список = [Nl, Nl + 1, Nl + 2, ..., N2 - 1, N2]
Вот она:
генератор( N, N, [N]).
генератор( Nl, N2, [Nl | Список]) :-
Nl < N2,
М is Nl + 1,
генератор( М, N2, Список).
Главную процедуру решение нужно соответствующим образом обобщить:
решение( N, S)
где N - это размер доски, а S - решение, представляемое в виде списка Y-координат N ферзей. Вот обобщенное отношение решение:
решение( N, S) :-
генератор( 1, N, Dxy),
Nu1 is 1 - N, Nu2 is N - 1,
генератор( Nu1, Nu2, Du),
Nv2 is N + N,
генератор( 2, Nv2, Dv),
реш( S, Dxy, Dxy, Du, Dv).
Например, решение задачи о 12 ферзях будет получено с помощью:
?- решение( 12, S).
S = [1, 3, 5, 8, 10, 12, 6, 11, 2, 7, 9, 4]
4. 5. 4. Заключительные замечания
Три решения задачи о восьми ферзях показывают, как к одной и той же задаче можно применять различные подходы. Мы варьировали также и представление данных. В одних случаях это представление было более экономным, в других - более наглядным и, до некоторой степени, избыточным. К недостаткам более экономного представления можно отнести то, что какая-то информация всякий раз, когда она требовалась, должна была перевычисляться.
В некоторых случаях основным шагом к решению было обобщение задачи. Как ни парадоксально, но
