Читаем Prolog полностью

которое конкретизирует Y-координаты (в СписY) ферзей, считая, что они размещены в последовательных вертикалях, взятых из Dx. Все Y-координаты и соответствующие координаты U и V берутся из списков Dy, Du и Dv. Главную процедуру решение можно запустить вопросом

        ?-  решение( S)

Это вызовет запуск реш с полными областями изменения координат, что соответствует пространству

решение( СписY) :-

        реш( СписY,                 % Y-координаты ферзей

                    [1, 2, 3, 4, 5, 6, 7, 8],

                                             % Область изменения Y-координат

                    [1, 2, 3, 4, 5, 6, 7, 8],

                                              % Область изменения Х-координат

                    [-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7],

                                              % Диагонали, идущие снизу вверх

                    [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 15, 14, 15, 16] ).

                                              % Диагонали, идущие сверху вниз

реш([ ], [ ], Dy, Du, Dv).

реш( [Y | СписY], [X | Dx1], Dy, Du, Dv) :-

        удалить( Y, Dy, Dy1),             % Выбор Y-координаты

        U is X-Y                             % Соответствующая диагональ вверх

        удалить( 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.    Заключительные замечания

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

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

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

Возникает естественный вопрос: " Какая из трех программ наиболее эффективна?" В этом отношение программа 2 значительно хуже двух других, а эти последние - одинаковы. Причина в том, что основанная на перестановках программа 2 строит все перестановки, тогда как две другие программы способны отбросить плохую перестановку не дожидаясь, пока она будет полностью построена. Программа 3 наиболее эффективна. Она избегает некоторых арифметических вычислений, результаты которых уже сразу заложены в избыточное представление доски, используемое этой программой.

Упражнение

4. 7.    Пусть поля доски представлены парами своих координат в виде X/Y, где как X, так и Y принимают значения от 1 до 8.