Prolog

Позицию на доске будем представлять как список Y-координат поставленных ферзей. Получаем программу:

        после( Ферзи, [Ферзь | Ферзи] ) :-

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

                                % Поместить ферзя на любую вертикальную линию

                небьет( Ферзь, Ферзи).

        цель( [ _, _, _, _, _, _, _, _ ] )

                                % Позиция с восемью ферзями

Отношение небьет означает, что Ферзь не может поразить ни одного ферзя из списка Ферзи. Эту процедуру можно легко запрограммировать так же, как это сделано в гл. 4. Ответ на вопрос

        ?-  решить( [ ], Решение)

будет выглядеть как список позиций с постепенно увеличивающимся количеством поставленных ферзей. Список завершается 'безопасной' конфигурацией из восьми ферзей. Механизм возвратов позволит получить и другие решения задачи.

Поиск в глубину часто работает хорошо, как в рассмотренном примере, однако наша простая процедура решить может попасть в затруднительное положение, причем многими способами. Случится ли это или нет - зависит от структуры пространства состояний. Для того, чтобы затруднить работу процедуры решить в примере рис. 11.4, достаточно внести в задачу совсем небольшое изменение: добавить дугу, ведущую из h  в  d,  чтобы получился цикл (рис. 11.5). В этом случае поиск будет выглядеть так: начиная с вершины  а,   спускаемся вплоть до  h,   придерживаясь самой левой ветви графа. На этот раз, в отличие от рис. 11.4, у вершины  h   будет преемник  d.  Поэтому произойдет не возврат из  h,  а переход к  d.  Затем мы найдем преемника вершины   d,  т.е. вершину  h,  и т.д., в результате программа зациклится между  h   и  d.

Рис. 11. 5.  Начинаясь в а, поиск вглубину заканчивается

бесконечным циклом между  d  и  h:   a, b, d, h, d, h, d ... .

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

        вглубину( Путь, Верш, Решение)

Как видно из рис. 11.6, Верш - это состояние, из которого необходимо найти путь до цели; Путь - путь (список вершин) между стартовой вершиной и Верш; Решение - Путь, продолженный до целевой вершины.

Рис. 11. 6.  Отношение вглубину( Путь, В, Решение).

Для облегчения программирования вершины в списках, представляющих пути, будут расставляться в обратном порядке. Аргумент Путь нужен для того,

(1)        чтобы не рассматривать тех преемников вершины Верш, которые уже встречались раньше (обнаружение циклов);

(2)        чтобы облегчить построение решающего пути Решение. Соответствующая программа поиска в глубину