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

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

Чтобы не было нападений по горизонтали, никакие два ферзя не должны занимать одну и ту же горизонталь. Это требование накладывает ограничение на Y-координаты: ферзи должны занимать все горизонтали с 1-й по 8-ю. Остается только выбрать порядок следования этих восьми номеров. Каждое решение представляет собой поэтому одну из перестановок списка:

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

Рис. 4.8. (а) Расстояние по X между

и равно 1. (b) Расстояние по X между и равно 3

Отношение

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

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

(2) S — непустой список вида

. Он безопасный, если список  — безопасный и не бьет ни одного ферзя из списка .

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

В этой программе отношение

более хитрое.

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

Трудность состоит в том, что расположение ферзей определяется только их Y-координатами, а X-координаты в представлении позиции не присутствуют в явном виде. Этой трудности можно избежать путем небольшого обобщения отношения

, как это показано на рис. 4.8. Предполагается, что цель

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

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

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

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

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

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