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


Рисунок 4 10 Связь между вертикалями



Рисунок 4. 10.  Связь между вертикалями, горизонталями и диагоналями. Помеченное
поле имеет следующие координаты: x = 2,  у = 4,  u = 2 - 4 = -2,  v = 2 + 4 = 6.

fig4_10.gif (3362 bytes)

Области изменения всех четырех координат таковы:

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

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

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

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

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

line();

решение( СписY) :-
        реш( СписY,                 % Y-координаты ферзей
                    [1, 2, 3, 4, 5, 6, 7, 8],
                                             % Область изменения Y-координат
                    [1, 2, 3, 4, 5, 6, 7, 8],
                                              % Область изменения Х-координат
                    [-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7],
                                              % Диагонали, идущие снизу вверх
                    [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 15, 14, 15, 16] ).
                                              % Диагонали, идущие сверху вниз
реш([ ], [ ], Dy, Du, Dv).

реш( [Y | СписY], [X | Dx1], Dy, Du, Dv) :-
        удалить( Y, Dy, Dy1),             % Выбор Y-координаты
        U is X-Y                             % Соответствующая диагональ вверх
        удалить( U, Du, Du1),             % Ее удаление
        V is X+Y                            % Соответствующая диагональ вниз
        удалить( V, Dv, Dv1),             % Ее удаление
        реш( СписY, Dх1, Dy1, Du1, Dv1).
                                                  % Выбор из оставшихся значений

удалить( А, [А | Список], Список).

удалить(A, [В | Список ], [В | Список1 ] ) :-
        удалить( А, Список, Список1).

line();



Начало Назад Вперед