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

Братко Иван

Отношение

перестановка

мы уже определила в гл. 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. Предполагается, что цель

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

обеспечивает отсутствие нападении ферзя

Ферзь

на поля списка

Остальные

в случае, когда расстояние по X между

Ферзь

и

Остальные

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

небьет

в качестве третьего аргумента:

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

Соответственно и цель

небьет

в отношении

безопасный

должна быть изменена на

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

Теперь отношение

небьет

может быть сформулировано в соответствии с двумя случаями, в зависимости от списка

Остальные

: если он пуст, то бить некого и, естественно, нет нападений; если же он не пуст, то

Ферзь

не должен бить первого ферзя из списка

Остальные

(который находится от ферзя

Ферзь

на расстоянии

РасстХ

вертикалей), а также ферзей из хвоста списка

Остальные

, находящихся от него на расстоянии

РасстХ + 1

. Эти соображения приводят к программе, изображенной на рис. 4.9.

4.5.3. Программа 3

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

 x вертикали

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

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

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

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

u = x - у

v = x + у

Рис. 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 и т.д.), так, чтобы ни один их элемент не выбирался дважды из одной области. Разумеется, выбор X и Y определяет выбор U и V. Решение при такой постановке задачи может быть вкратце таким: при заданных 4-x областях изменения выбрать позицию для первого ферзя, вычеркнуть соответствующие элементы из 4-x областей изменения, а затем использовать оставшиеся элементы этих областей для размещения остальных ферзей. Программа, основанная на таком подходе, показана на рис. 4.11. Позиция на доске снова представляется списком Y-координат. Ключевым отношением в этой программе является отношение

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

которое конкретизирует Y-координаты (в

СписY

) ферзей, считая, что они размещены в последовательных вертикалях, взятых из Dx. Все Y-координаты и соответствующие координаты U и V берутся из списков Dy, Du и Dv. Главную процедуру

решение

можно запустить вопросом

?- решение( S)

Это вызовет запуск

реш

с полными областями изменения координат, что соответствует пространству задачи о восьми ферзях.