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

        рейс( Город3, лондон, пт, Np4, Отпр4, Приб4).

        Город1 = милан

        Город2 = цюрих

        Город3 = любляна

        Npl = ba510

        Отпр1 = 8:30

        Приб1 = 11:20

        Np2 =sr621

        Отпр2 = 9:25

        Приб2 = 10:15

        Np3 = yu323

        Отпр3 = 13:30

        Приб3 = 14:40

        Np4 = yu200

        Отпр4 = 11:10

        Приб4 = 12:20

Назад | Содержание | Вперёд

Назад | Содержание | Вперёд

4. 5.    Задача о восьми ферзях

Эта задача состоит в отыскании такой расстановки восьми ферзей на пустой шахматной доске, в которой ни один из ферзей не находится под боем другого. Решение мы запрограммируем в виде унарного отношения:

        решение( Поз)

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

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

Вначале нужно выбрать способ представления позиции на доске. Один из наиболее естественных способов - представить позицию в виде списка из восьми элементов, каждый из которых соответствует одному из ферзей. Каждый такой элемент будет описывать то поле доски, на которой стоит соответствующий ферзь. Далее, каждое поле доски можно описать с помощью пары координат ( Х и Y), где каждая координата - целое число от 1 до 8. В программе мы будем записывать такую пару в виде

        Х / Y

где оператор "/" обозначает, конечно, не деление, а служит лишь для объединения координат поля в один элемент списка. На рис. 4.6 показано одно из решений задачи о восьми ферзях и его запись в виде списка.

После того. как мы выбрали такое представление, задача свелась к нахождению списка вида:

        [Xl/Yl, X2/Y2, X3/Y3, X4/Y4, X5/Y5, X6/Y6, X7/Y7, X8/Y8]

удовлетворяющего требованию отсутствия нападений. Наша процедура решение должна будет найти подходящую конкретизацию переменных X1, Y1, Х2, Y2, ..., Х8, Y8. Поскольку мы знаем, что все ферзи должны находиться на разных вертикалях во избежание нападений по вертикальным линиям, мы можем сразу же ограничить перебор, чтобы облегчать поиск решения. Можно поэтому сразу зафиксировать Х-координаты так, чтобы список, изображающий решение, удовлетворял следующему, более конкретному шаблону:

        [1/Y1, 2/Y2, 3/Y3, 4/Y4, 5/Y5, 6/Y6, 7/Y7, 8/Y8]

Рис. 4. 6.  Решение задачи о восьми ферзях. Эта позиция может быть

представлена в виде списка [1/4,  2/2,  3/7,   4/3,  5/6,  6/8,  7/5,  8/1].

Нас интересует решение для доске размером 8х8. Однако, как это часто бывает в программировании, ключ к решению легче найти, рассмотрев более общую постановку задачи. Как это ни парадоксально, но часто оказывается, что решение более общей задачи легче сформулировать, чем решение более частной, исходной задачи; после этого исходная задача решается просто как частный случай общей задачи.

Основная часть работы при таком подходе ложится на нахождение правильного обобщения исходной задачи. В нашем случае хорошей является идея обобщать задачу в отношении количества ферзей (количества вертикалей в списке), разрешив количеству ферзей принимать любое значение, включая нуль. Тогда отношение решение можно сформулировать, рассмотрев два случая:

Случай 1.    Список ферзей пуст. Пустой список без сомнения является решением, поскольку нападений в этом случае нет.

Случай 2.    Список ферзей не пуст. Тогда он выглядит так:

        [ X/Y | Остальные ]

В случае 2 первый ферзь находится на поле Х / Y, а остальные - на полях, указанных в списке Остальные. Если мы хотим, чтобы это было решением, то должны выполняться следующие условия:

(1)        Ферзи, перечисленные в списке Остальные, не должны бить друг друга; т. е. список Остальные сам должен быть решением.

(2)        Х и Y должны быть целыми числами от 1 до 8.

(3)        Ферзь, стоящий на поле X / Y, не должен бить ни одного ферзя из списка Остальные.

Чтобы запрограммировать первое условие, можно воспользоваться самим отношением решение. Второе условие можно сформулировать так: Y должен принадлежать списку целых чисел от 1 до 8. т. е. [1, 2, 3, 4, 5, 6, 7, 8]. С другой стороны, о координате Х можно не беспокоиться, поскольку список-решение должен соответствовать шаблону, у которого Х-координаты уже определены. Поэтому Х гарантированно получит правильное значение от 1 до 8. Третье условие можно обеспечить с помощью нового отношения небьет. Все это можно записать на Прологе так:

        решение( [X/Y | Остальные] ) :-

               решение( Остальные),