Программирование в ограничениях CLP(FD)

Промышленный способ решать головоломки: не перебирать вслепую, а позволить ограничениям самим отсекать невозможное.

CLP(FD) (Constraint Logic Programming over Finite Domains) — расширение Prolog, в котором переменные принимают значения из конечного множества целых чисел, а ограничения вроде «равно», «не равно», «меньше» активно сужают допустимые значения ещё до перебора.

В прошлом уроке мы увидели слабость «чистого» generate-and-test: сначала порождается кандидат, потом проверяется. CLP(FD) переворачивает порядок — сначала объявляются ограничения, и движок постоянно вычисляет, какие значения переменных ещё возможны. Это называется распространением ограничений (constraint propagation): едва значение одной переменной сузилось, эффект мгновенно прокатывается по всем связанным ограничениям. Перебор (labeling) подключается лишь в самом конце и работает по уже сильно урезанному пространству. Для задач вроде судоку разница — секунды против часов.

Библиотека подключается одной строкой:

:- use_module(library(clpfd)).

Переменные, домены и оператор ins

Каждой переменной задают домен — диапазон допустимых целых. Оператор in задаёт домен одной переменной, ins — сразу списку.

?- X in 1..9.
X in 1..9.            % X может быть любым целым от 1 до 9

?- [A,B,C] ins 0..5.
A in 0..5, B in 0..5, C in 0..5.

Арифметические ограничения

Главное отличие от обычной арифметики Prolog (is/2) — ограничения двунаправленны и работают даже над несвязанными переменными. Их имена начинаются с #.

Смотрите, как ограничение сужает домен само, без перебора:

?- X in 1..9, Y in 1..9, X #> Y, Y #> 6.
X in 8..9,
Y in 7..8.

Мы не назвали ни одного конкретного числа, но движок уже вывел, что X может быть только 8 или 9, а Y — 7 или 8. Это и есть распространение ограничений в действии.

all_different и перечисление меток

Ограничение all_different/1 требует, чтобы все элементы списка были попарно различны — встречается почти в каждой головоломке. Когда ограничения объявлены, для получения конкретных чисел вызывают label/1 (или более гибкий labeling/2): он перебирает значения из суженных доменов.

puzzle([A,B,C]) :-
    [A,B,C] ins 1..3,
    all_different([A,B,C]),
    A #< B,
    label([A,B,C]).

?- puzzle(L).
L = [1, 2, 3].

Из 27 формальных комбинаций ограничения оставили ровно одну ещё до того, как label начал перебор.

SEND + MORE = MONEY

Классический ребус: каждой букве сопоставить свою цифру так, чтобы сложение в столбик было верным. CLP(FD) решает его почти дословно по условию.

:- use_module(library(clpfd)).

send_more_money([S,E,N,D,M,O,R,Y]) :-
    Vars = [S,E,N,D,M,O,R,Y],
    Vars ins 0..9,
    all_different(Vars),
            1000*S + 100*E + 10*N + D
    +       1000*M + 100*O + 10*R + E
    #= 10000*M + 1000*O + 100*N + 10*E + Y,
    S #\= 0,
    M #\= 0,
    label(Vars).

Вывод:

?- send_more_money(Solution).
Solution = [9, 5, 6, 7, 1, 0, 8, 2].
% S=9 E=5 N=6 D=7 M=1 O=0 R=8 Y=2
%   9567 + 1085 = 10652

Ни единого цикла или ручного перебора — только перевод условия в ограничения. Ограничения S #\= 0 и M #\= 0 убирают ведущие нули.

Судоку в нескольких строках

Та же идея масштабируется на судоку: домен 1..9 на каждую клетку, all_different на каждую строку, столбец и блок 3×3, затем labeling.

sudoku(Rows) :-
    append(Rows, Vs), Vs ins 1..9,
    maplist(all_distinct, Rows),        % строки
    transpose(Rows, Columns),
    maplist(all_distinct, Columns),     % столбцы
    blocks(Rows),                       % блоки 3x3 (через all_distinct)
    maplist(label, Rows).

(all_distinct/1 — более мощная версия all_different/1 с сильным распространением.) Распространение ограничений отсекает большинство ветвей мгновенно — настоящий перебор почти не нужен.

Как работает под капотом

За каждой CLP(FD)-переменной стоит её текущий домен — множество ещё возможных значений. Когда вы пишете ограничение, оно регистрируется как «наблюдатель» за своими переменными. Стоит домену любой из них сузиться (например, из-за другого ограничения или шага label), наблюдатель просыпается и пересчитывает, какие значения остальных переменных всё ещё совместимы, выкидывая невозможные. Эта волна сужений прокатывается по сети ограничений, пока всё не стабилизируется. Лишь после этого label/1 выбирает одну переменную, присваивает ей значение из домена — и снова запускает волну распространения. Контраст с generate-and-test нагляден:

generate-and-test:   придумай ВСЁ -> проверь -> почти всё отбрось
CLP(FD):             ограничь домены -> распространи -> перебирай малый остаток

Поэтому CLP(FD) не угадывает вслепую: к моменту перебора пространство уже схлопнуто ограничениями до крошечного.

Частые ошибки

• Путать #= и =/is. = — это унификация термов, is/2 требует, чтобы правая часть была уже вычислимой. Только #= создаёт настоящее двунаправленное числовое ограничение над доменами.
• Забыть label/labeling. Без него вы получите суженные домены, но не конкретные числа — решение «зависнет» в виде ограничений.
• Сырой < вместо #<. Обычные <, >, =< требуют связанных чисел и упадут на переменных-доменах; в CLP(FD) используйте версии с #.
• Перебор раньше времени. Если поставить label до того, как объявлены все ограничения, теряется весь смысл распространения — будет почти тот же слепой перебор.

Итоги

• CLP(FD) подключается через use_module(library(clpfd)) и работает с переменными над конечными целочисленными доменами.
• Домен задаётся через in/ins; арифметические ограничения — #=, #\=, #<, #>, #=<, #>= — двунаправленны.
• all_different/1 (и all_distinct/1) требует попарной различности; label/labeling присваивает конкретные значения.
• Судоку и SEND+MORE=MONEY решаются почти дословным переводом условия в ограничения.
• Преимущество над generate-and-test — распространение ограничений отсекает ветви заранее, до перебора.