Вторая формулировка.

Переменные: +

Домены:

Ограничения:

,

.

Ниже, в разделе 10.2.5, приведена программа решения этой задачи на языке Prolog.

Пример 10.7. Задача о ферзях

Задача о ферзях состоит в размещении ферзей на шахматной доске так, чтобы они не угрожали друг другу (см. рис. 10.1).

Модель удовлетворения ограничений:

ферзи в вертикальных столбцах: .

отсутствие конфликтов:

Рис. 10.1. Одно из решений задачи о 8 ферзях.

Одним из примеров использования УО является решение кроссвордов.

Пример 10.8. Пример составления кроссворда.

Рассмотрим пример составления кроссворда из [33]. Задача со­стоит в вертикальной или горизонтальной записи слов из заданного множе­ства слов (словаря) в таблицу с учетом некоторых ограничений. Если разре­шено вставлять каждое слово на пустое место соответствующей длины, воз­можная формулировка задачи о кроссворде в виде задачи УО выглядит сле­дующим образом. Для каждого квадрата кроссворда вводится переменная, принимающая буквенные значения из алфавита, причем могут быть заданы возможные значения для групп смежных переменных.

Рис. 10.2. Задача о кроссворде.

Приведем формальную формулировку задачи о кроссворде в терминах ограничений. Каждому квадрату кроссворда, который должен быть запол­нен (см. рис. 10.2) поставим в соответствие переменную . Пере­менные в качестве доменов имеют буквы алфавита, в качестве ограни­чений служат допустимые слова. Например, ограничения могут быть заданы следующим образом [33]:

,

,

,

,

.