Программирование на языке ПРОЛОГ для искуственного интеллекта




Задача о восьми ферзях - часть 2


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

fig4_6.gif (1501 bytes)

Рис. 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.


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