Объектно-ориентированное программирование в ограничениях


         

Один из вариантов решения задачи




Рис. 1.  Один из вариантов решения задачи о восьми ферзях

Положение каждой фигуры на шахматной доске характеризуется парой координат x/y, каждая из которых принимает целые значения от 1 до 8 (здесь мы отступим от традиционной буквенно-цифровой нотации ходов в шахматной партии, подобной “e2-e4”, и будем использовать оператор «/» для объединения координат в один элемент списка). Тогда шахматная позиция представляется списком вида [xl/yl, x2/y2, x3/y3, x4/y4, x5/y5, x6/y6, x7/y7, x8/y8]. В этом представлении решение на рис. 1 выглядит, как [1/4,  2/2,  3/7,   4/3,  5/6,  6/8,  7/5,  8/1].

Если принять во внимание необходимость расположения ферзей на разных вертикалях (или на разных горизонталях), то представление списка можно сразу уточнить, как [l/yl, 2/y2, 3/y3, 4/y4, 5/y5, 6/y6, 7/y7, 8/y8]. Таким образом, задача сводится к определению горизонтальных (или вертикальных) координат, исключающих расположение нескольких фигур на одних и тех же линиях шахматной доски.

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

  • Случай 1. Список пуст. Очевидно, пустой список является согласованным при отсутствии фигур и возможных атак.

  • Случай 2. Список не пуст. Тогда он представим в виде [ x/y | Остальные ], где x/y задает положение первого ферзя, а список “Остальные” — положение остальных. Определим необходимые условия, при которых непустой список является согласованным. Во-первых, список “Остальные” должен быть согласованным. Во-вторых, значения x и y должны принадлежать множеству целых чисел от 1 до 8 включительно. В-третьих, значения x и y, а также их разности ( x-y ) и суммы ( x+y ) не должны совпадать с соответствующими значениями из списка “Остальные”.


    Содержание  Назад  Вперед





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