Программирование на языке Пролог для искусственного интеллекта
6ec30db9

представлением доски каждое решение



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

В соответствии с принятым в программе 1 представлением доски каждое решение имело вид
        [1/Y1, 2/Y2, 3/Y3, ..., 8/Y8]
так как ферзи расставлялись попросту в последовательных вертикалях. Никакая информация не была бы потеряна, если бы Х-координаты были пропущены. Поэтому можно применить более экономное представление позиции на доске, оставив в нем только Y-координаты ферзей:
        [Y1, Y2, Y3, ..., Y8]
Чтобы не было нападений по горизонтали, никакие два ферзя не должны занимать одну и ту же горизонталь. Это требование накладывает ограничение на Y-координаты: ферзи должны занимать все горизонтали с 1-й по 8-ю. Остается только выбрать порядок следования этих восьми номеров. Каждое решение представляет собой поэтому одну из перестановок списка:
        [1, 2, 3, 4, 5, 6, 7, 8]
Такая перестановка S является решением, если каждый ферзь в ней не находится под боем (список S - "безопасный"). Поэтому мы можем написать:
        решение( S) :-
              перестановка( [1, 2, 3, 4, 5, 6, 7, 8], S),
              безопасный( S).


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

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




Содержание раздела