Иван Братко - Программирование на языке Пролог для искусственного интеллекта Страница 25

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

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

[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 первый ферзь находится на поле X / Y, а остальные — на полях, указанных в списке Остальные. Если мы хотим, чтобы это было решением, то должны выполняться следующие условия:

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

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

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

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

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

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

 принадлежит( Y, [1, 2, 3, 4, 5, 6, 7, 8] ),

 небьет( X/Y, Остальные).

Осталось определить отношение небьет:

небьет( Ф, Фспис)

И снова его описание можно разбить на два случая:

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

(2) Если Фспис не пуст, то он имеет форму

[Ф1 | Фспис1]

и должны выполняться два условия:

 (а) ферзь на поле Ф не должен бить ферзя на поле Ф1 и

 (b) ферзь на поле Ф не должен бить ни одного ферзя из списка Фспис1.

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

• Y-координаты ферзей были различны и

• ферзи не находились на одной диагонали, т.е. расстояние между полями по направлению X не должно равняться расстоянию между ними по Y.

На рис. 4.7 приведен полный текст программы. Чтобы облегчить ее использование, необходимо добавить список-шаблон. Это можно сделать в запросе на генерацию решений. Итак:

?-  шаблон( S), решение( S).

решение( [] ).

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

  % Первый ферзь на поле X/Y,

  % остальные ферзи на полях из списка Остальные

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

 принадлежит Y, [1, 2, 3, 4, 5, 6, 7, 8] ),

 небьет( X/Y | Остальные).

  % Первый ферзь не бьет остальных

небьет( _, [ ]). % Некого бить

небьет( X/Y, [X1/Y1 | Остальные] ) :-

 Y =\= Y1,       % Разные Y-координаты

 Y1-Y =\= X1-X   % Разные диагонали

 Y1-Y =\= X-X1,

 небьет( X/Y, Остальные).

принадлежит( X, [X | L] ).

принадлежит( X, [Y | L] ) :-

 принадлежит( X, L).

% Шаблон решения

шаблон( [1/Y1, 2/Y2, 3/Y3, 4/Y4, 5/Y5, 6/Y6, 7/Y7, 8/Y8]).

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

Система будет генерировать решения в таком виде:

S = [1/4, 2/2, 3/7, 4/3, 5/6, 6/8, 7/5, 8/1];

S = [1/5, 2/2, 3/4, 4/7, 5/3, 6/8, 7/6, 8/1];

S = [1/3, 2/5, 3/2, 4/8, 5/6, 6/4, 7/7, 8/1].

...

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

4.5.2. Программа 2

В соответствии с принятым в программе 1 представлением доски каждое решение имело вид

[1/Y1, 2/Y2, 3/Y3, ..., 8/Y8]

так как ферзи расставлялись попросту в последовательных вертикалях. Никакая информация не была бы потеряна, если бы X-координаты были пропущены. Поэтому можно применить более экономное представление позиции на доске, оставив в нем только 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.8. (а) Расстояние по X между Ферзь и Остальные равно 1. (b) Расстояние по X между Ферзь и Остальные равно 3

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

(1) S — пустой список. Тогда он, конечно, безопасный, ведь нападать не на кого.

(2) S — непустой список вида [Ферзь | Остальные]. Он безопасный, если список Остальные — безопасный и Ферзь не бьет ни одного ферзя из списка Остальные.

На Прологе это выглядит так:

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

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

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

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

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

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

 перестановка( [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-координатами, а X-координаты в представлении позиции не присутствуют в явном виде. Этой трудности можно избежать путем небольшого обобщения отношения небьет, как это показано на рис. 4.8. Предполагается, что цель