Генерация и проверка (generate-and-test) и головоломки

Самая знаменитая стратегия Prolog: пусть машина переберёт все варианты, а ограничения отсеют неподходящие.

Generate-and-test — приём, при котором одна часть программы порождает кандидата-решение (генератор), а другая проверяет, удовлетворяет ли он условиям задачи (тест); бэктрекинг автоматически перебирает кандидатов, пока тест не пройдёт.

В императивных языках головоломку решают, явно описывая алгоритм перебора: вложенные циклы, флаги, ручной откат. В Prolog всё иначе — откат встроен в сам движок. Достаточно описать, как выглядит правильное решение, а поиск Prolog возьмёт на себя. Парадигма «генерируй и проверяй» доводит эту идею до предела: вы пишете предикат, который недетерминированно порождает любого кандидата, и набор условий, которые он обязан соблюсти. Если кандидат не проходит проверку, бэктрекинг молча возвращается и пробует следующего. Получается код, который читается почти как условие задачи.

Скелет подхода

Любое решение в этом стиле имеет одинаковую форму: сначала генератор, потом серия тестов.

solution(X) :-
    generate(X),   % недетерминированно даёт кандидата за кандидатом
    test(X).       % проваливается, если кандидат плох -> бэктрекинг

Классический генератор перестановок — permutation/2 из стандартной библиотеки. Допустим, нужно расставить числа 1, 2, 3 так, чтобы первое было меньше последнего:

?- permutation([1,2,3], [A,B,C]), A < C.
A = 1, B = 2, C = 3 ;
A = 1, B = 3, C = 2 ;
A = 2, B = 1, C = 3 ;
... (только перестановки, где A < C)

Обратите внимание на A < C — это и есть «тест». Любая перестановка, нарушающая условие, отбрасывается откатом.

Зебра-загадка Эйнштейна

Знаменитая головоломка: пять домов в ряд, каждый своего цвета, в каждом живёт человек своей национальности, с любимым напитком, сигаретами и питомцем. Дано полтора десятка подсказок вроде «зелёный дом сразу справа от белого», «норвежец живёт в первом доме», «тот, кто держит лошадь, живёт рядом с любителем определённого табака». Вопрос: кто пьёт воду и у кого живёт зебра?

В Prolog ряд домов моделируют списком из пяти структур, где неизвестные признаки — несвязанные переменные. Подсказки превращаются в предикаты над этим списком.

% Дом: h(Цвет, Нация, Напиток, Сигареты, Питомец)
% «X сразу справа от Y» — соседние элементы списка:
right_of(X, Y, [Y, X | _]).
right_of(X, Y, [_ | Rest]) :- right_of(X, Y, Rest).

% «X живёт рядом с Y» — в любом порядке:
next_to(X, Y, L) :- right_of(X, Y, L).
next_to(X, Y, L) :- right_of(Y, X, L).

zebra(WaterDrinker, ZebraOwner) :-
    Houses = [h(_,_,_,_,_), h(_,_,_,_,_), h(_,_,_,_,_),
              h(_,_,_,_,_), h(_,_,_,_,_)],
    member(h(red, english, _, _, _), Houses),         % англичанин в красном
    member(h(_, spanish, _, _, dog), Houses),         % у испанца собака
    right_of(h(green,_,_,_,_), h(white,_,_,_,_), Houses), % зелёный справа от белого
    member(h(green, _, coffee, _, _), Houses),        % в зелёном пьют кофе
    Houses = [h(_, norwegian, _, _, _) | _],          % норвежец в первом доме
    % ... остальные подсказки ...
    member(h(_, _, water, _, _), Houses),             % кто-то пьёт воду
    member(h(_, _, _, _, zebra), Houses),             % у кого-то зебра
    member(h(_, WaterDrinker, water, _, _), Houses),
    member(h(_, ZebraOwner, _, _, zebra), Houses).

Здесь member/2 — генератор: он недетерминированно сопоставляет шаблон с каждым домом, перебирая варианты. Совокупность подсказок — тест. Prolog сам ищет такую расстановку переменных, при которой выполнены все условия одновременно. Запрос даёт единственное решение:

Вывод:

?- zebra(W, Z).
W = norwegian,
Z = japanese.

То есть воду пьёт норвежец, а зебра живёт у японца. Мы не написали ни одного цикла — только описали условие.

Раскраска карты

Вторая хрестоматийная задача: раскрасить карту так, чтобы никакие две соседние страны не были одного цвета. Генератором служит member/2 по списку доступных цветов, тестом — неравенство \= для каждой пары соседей.

color(C) :- member(C, [red, green, blue]).

% Соседи: A-B, A-C, B-C, B-D, C-D
color_map(A, B, C, D) :-
    color(A), color(B), color(C), color(D),
    A \= B, A \= C,
    B \= C, B \= D,
    C \= D.

?- color_map(A, B, C, D).
A = red, B = green, C = blue, D = red ;
...

Каждый вызов color/4 генерирует один из трёх цветов, а проверки \= отбрасывают расстановки, где соседи совпали. Заметьте, как генератор и тест чередуются: Prolog не строит сначала все 81 комбинацию, а отсекает плохие ветки по ходу — но об этом подробнее ниже.

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

Эффективность generate-and-test целиком зависит от того, когда срабатывает тест. Если сначала сгенерировать полного кандидата и лишь потом проверять, движок переберёт всё пространство — для перестановок это факториал, для пяти домов с пятью признаками — астрономические числа. Спасает приём «вплетённый тест» (interleaving): проверки ставят как можно ближе к генерации соответствующей переменной, чтобы откат случался рано.

           generate A           generate A
              |                    |
           generate B          test A (рано!)
              |          vs        |
           test A,B            generate B
   (поздно — много веток)   test A,B (отсекли заранее)

В зебра-загадке роль раннего отсечения играет унификация: как только member связывает национальность с цветом, несовместимые дома мгновенно отпадают по сопоставлению, а не доживают до финальной проверки. Тем не менее это всё ещё перебор — просто с умной расстановкой условий. Именно ограниченность «чистого» generate-and-test мотивирует следующий шаг — программирование в ограничениях, где отсечение веток встроено в сам механизм.

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

• Все тесты в конце. Сначала generate(всё), потом test(всё) — корректно, но катастрофически медленно. Вплетайте проверки между генераторами.
• Путать \= и \==. \= означает «не унифицируемы» (то, что нужно для раскраски связанных переменных), а \== — «не идентичны как термы прямо сейчас». Для свободных переменных они ведут себя по-разному.
• Генератор, не покрывающий все варианты. Если generate упускает часть кандидатов, решение может не найтись вовсе — проверяйте полноту генератора.
• Бесконечная генерация. Рекурсивный генератор без ограничения длины (например, перебор списков любой длины) уведёт поиск в бесконечность ещё до первого теста.

Итоги

• Generate-and-test: один предикат порождает кандидата, другой проверяет; бэктрекинг перебирает варианты автоматически.
• permutation/2 и member/2 — типичные генераторы; <, \= и подобные — типичные тесты.
• Зебра-загадка решается описанием подсказок как предикатов над списком домов — без единого цикла.
• Раскраска карты: member по цветам как генератор, \= для соседей как тест.
• Производительность определяется ранним вплетением тестов; «чистый» перебор в конце — медленный, и это мотивирует переход к CLP(FD).