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

              безопасный( Остальные),

              небьет(Ферзь | Остальные).

В этой программе отношение небьет более хитрое.

решение( Ферзи) :-

        перестановка( [1, 2, 3, 4, 5, 6, 7, 8], Ферзи),

        безопасный( Ферзи).

перестановка( [ ], [ ]).

перестановка( [Голова | Хвост], СписПер) :-

        перестановка( Хвост, ХвостПер),

        удалить( Голова, СписПер, ХвостПер).

                            % Вставка головы в переставленный хвост

удалить( А, [А | Список).

удалять( А, [В | Список], [В, Список1] ) :-

        удалить( А, Список, Список1).

безопасный( [ ]).

безопасный( [Ферзь | Остальные]) :-

        безопасный( Остальные),

        небьет( Ферзь, Остальные, 1).

небьет( _, [ ], _ ).

небьет( Y, [Y1 | СписY], РасстХ) :-

    Y1-Y =\= РасстХ,

    Y-Y1 =\= РасстХ,

    Расст1 is РасстХ + 1,

    небьет( Y, СписY, Расст1).

Рис. 4. 9.  Программа 2 для задачи о восьми ферзях.

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

        небьет( Ферзь, Остальные)

обеспечивает отсутствие нападении ферзя Ферзь на поля списка Остальные в случае, когда расстояние по Х между Ферзь и Остальные равно 1. Остается рассмотреть более общий случай произвольного расстояния. Для этого мы добавим его в отношение небьет в качестве третьего аргумента:

        небьет( Ферзь, Остальные, РасстХ)

Соответственно и цель небьет в отношении безопасный должна быть изменена на

        небьет( Ферзь, Остальные, 1)

Теперь отношение небьет может быть сформулировано в соответствии с двумя случаями, в зависимости от списка Остальные: если он пуст, то бить некого и, естественно, нет нападений; если же он не пуст, то Ферзь не должен бить первого ферзя из списка Остальные (который находится от ферзя Ферзь на расстоянии РасстХ вертикалей), а также ферзей из хвоста списка Остальные, находящихся от него на расстоянии РасстХ + 1. Эти соображения приводят к программе, изображенной на рис. 4.9.

4. 5. 3.    Программа 3

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

    x         вертикали

    у         горизонтали

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

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

Эти координаты не являются независимыми: при заданных  х  и  у,  u  и   v  определяются однозначно (пример на рис.4.10). Например,

    u = х - у

    v = х + у

Рис. 4. 10.  Связь между вертикалями, горизонталями и диагоналями. Помеченное

поле имеет следующие координаты: x = 2,  у = 4,  u = 2 - 4 = -2,  v = 2 + 4 = 6.

Области изменения всех четырех координат таковы:

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

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

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

        Dv = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

Задачу о восьми ферзях теперь можно сформулировать следующим образом: выбрать восемь четверок (X, Y, U, V), входящих в области изменения (X в Dx, Y в Dy и т.д.), так, чтобы ни один их элемент не выбирался дважды из одной области. Разумеется, выбор Х и Y определяет выбор U и V. Решение при такой постановке задачи может быть вкратце таким: при заданных 4-х областях изменения выбрать позицию для первого ферзя, вычеркнуть соответствующие элементы из 4-х областей изменения, а затем использовать оставшиеся элементы этих областей для размещения остальных ферзей. Программа, основанная на таком подходе, показана на рис. 4.11. Позиция на доске снова представляется списком Y-координат. Ключевым отношением в этой программе является отношение

        peш( СписY, Dx, Dy, Du, Dv)