Упражнение. 4.6, При поиске решения программа, приведенная в листинге 4,2, проверяет аль­тернативные значения для координат Y ферзей

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

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

При использовании представления позиции на доске при разработке программы 1 каждое решение имело следующую форму:

[ l/Yi, 2/Y2, 3/Y3,..., 8/YS]

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

[ XI, Y2, Y3, ..., YB]

Для предотвращения нападений по горизонтали ни одна пара ферзей не должна находиться на одном и том же горизонтальном ряду клеток доски. Такое условие на­лагает ограничение на выбор координат Y. Ферзи должны занимать все горизонталь-

Часть I, Язык Prolog

ные ряды 1, 2, ..., 8. Остается только сделать выбор правильного порядка этих вось­ми чисел. Поэтому каждое решение представляет собой одну из перестановок списка: [1,2,3,4,5, 6,7,В]

Такая перестановка, S, представляет собой решение, если все ферзи находятся в безопасности. Поэтому можно записать следующее правило: solution ( S) : -

permutation ( [1,2,3,4,5,6,7,8], S),

safe [ S) .

Программа для отношения permutation была разработана в главе 3, поэтому ос­тается только определить отношение safe. Его определение можно разделить на два описанных ниже случая.

1, S пустой список. Такой вариант, безусловно, является безопасным, по­
скольку отсутствует угроза нападения со стороны какого-либо из ферзей.

2. S •- непустой список в форме [Queen | Others]. Эта ситуация является
безопасной, если безопасным является список Others и ферзь Queen не напа­
дает на каких-либо ферзей в списке Others.

В языке Prolog¹ это определение может быть выражено следующим образом: safe ([ ]) .

safe. [Queen I Others] ] : -safe: Others), noattack< Queen, others).

Приведенное здесь отношение noattack определить немного сложнее. Сложность состоит в том, что позиции ферзей определены только координатами Y, а координаты X явно не представлены. Эту проблему можно решить благодаря небольшому обобще­нию отношения noattack, как показано на рис. 4.6, Следующая цель: noattack< Queen, Others)

предназначена для обеспечения того, чтобы ферзь Queen не нападал на ферзей Others, если расстояние X между Queenи Others равно 1. В данном случае необхо­димо обобщить понятие расстояния X между Queen и Others. Поэтому введем это рас­стояние в качестве третьего параметра в отношение noattack следующим образом: oeattacfel Queen, Others, Xdist)

Соответствующим образом цель noattack в отношении safe необходимо модифи­цировать следующим образом: noattack( Queen, others, 1)

а)

Queen -

	/ *\
л	J
/	• у -
---/
i	r
\t	/

ГЧ

Расстояние X равно 1

• Others

6)
	/•
	/ '
	/• 1
•	f /
: з	/
. _^	л'
i—	н

Расстояние X равно 3

Рис. 4.6. Способ обобщения отношения noattack: а) расстояние X между Queen и Otherравно 1; б) расстояние X между Queen и Others равно 3

Глава 4. Использование структур: примеры программ

Теперь отношение noattack можно сформулировать в соответствии с двумя рас­сматриваемыми случаями, в зависимости от списка Others: если список Others пуст, то отсутствует противник, на которого можно было бы напасть, и поэтому, без­условно, отсутствует нападение; если список Others не пуст, то ферзь Queen не дол­жен нападать на первого ферзя в списке Others (который находится на расстоянии в Xdist столбцов от Queen), а также на ферзя, находящегося в хвосте списка Others, который расположен на расстоянии Xdist + 1. Эти рассуждения приводят к созда­нию программы, показанной в листинге 4.3.

Листинг 4.3.Программа 2 для решения задачи с восемью ферзями

* solution) Queens), если

% Queens - список координат Y восьми ненападающих ферзей

solution С Queens) :-

permutation( [1,2,3,4,5,6,7,8!, Queens) , safe( Queens).

permutation( (], [] ).

permutation[ [Head I Tail], PermList) :-

permutation; Tail, PermTail),

dell Head, PermList, PermTail). ft Вставить голову Head в список Tail,

% подвергшийся перестановке

% del( Item, List, NewList) - список NewList получек пугеы удаления элемента
% Item из списка List

del t Item, [Item I List], List).

dell Item, [First I List], [First I Listl] ) :-del( Item, List, Listl) .

* safe i Queens) , если

Queens - список координат Y восьми ненападающих ферзей

safe( [] ).

safe( [Queen I Others] } :-safe( Others) , noattack( Queen, Others, 1) .

noattackl _, [] , _) .

noattack! Y, [Yl I Ylist], Xdist) :-Yl-Y -\- Xdist, y-yi -\- xdist,

Distl is Xdist + 1, noattack ( Y, Ylist, Distl).