Недавно The New York Times запустила новую ежедневную головоломку под названием Pips. Суть в том, что нужно разложить набор костяшек домино на сетке так, чтобы выполнялись различные условия. Например, в головоломке ниже сумма очков (точек на костях домино) в фиолетовых клетках должна быть равна 8, в красной клетке должно быть меньше 5 очков, а в трёх зелёных клетках значения должны быть одинаковыми. (Чтобы решить эту «лёгкую» головоломку, много думать не нужно, а вот варианты «medium» и «hard» уже заметно сложнее.)

Я задумался, как решать такие головоломки на компьютере. Недавно я увидел статью «Многие сложные задачи на LeetCode — это простые задачи на ограничения», в которой рассказывалось о преимуществах и гибкости системы класса «решателей ограничений». Решатель ограничений принимает на вход набор ограничений и находит решения, которые этим ограничениям удовлетворяют, — ровно то, что нужно для Pips.

Я решил, что решение Pips с помощью решателя ограничений — хороший способ разобраться с такими системами, но у меня было несколько вопросов. Требуют ли решатели ограничений какой-то запредельной математики? Насколько сложно формулировать задачу? Сможет ли решатель быстро найти решение или завязнет в экспоненциальном переборе?

В итоге выяснилось, что пользоваться решателем ограничений довольно просто: у меня ушло меньше двух часов от состояния «ничего не знаю про решатели ограничений (constraint solving)» до рабочего решения задачи. Решатель находил решения за миллисекунды (в большинстве случаев). Однако по дороге встретилось несколько подводных камней. В этой статье я расскажу о своём опыте работы с системой моделирования ограничений MiniZinc ^(прим.1) и покажу, как с её помощью можно решать Pips.

Подход к проблеме

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

Чтобы решить задачу, я создал массив pips, в котором хранится количество очков домино в каждой позиции сетки. Тогда три ограничения для задачи выше можно записать так. Видно, что ограничения напрямую выражают условия головоломки.

constraint pips[1,1] + pips[2,1] == 8;
constraint pips[2,3] < 5;
constraint all_equal([pips[3,1], pips[3,2], pips[3,3]]);

Далее мне нужно было задать, в каких местах на поле можно размещать домино. Для этого я определил массив grid, который обозначает допустимые позиции: 1 означает допустимую клетку, 0 — недопустимую. (Если сравнить с головоломкой в начале статьи, можно увидеть, что сетка ниже совпадает с её формой.)

grid = [|
1,1,0|
1,1,1|
1,1,1|];

Я также определил набор домино для этой задачи, указав количество очков на каждой половине:

spots = [|5,1| 1,4| 4,2| 1,3|];

Пока что ограничения напрямую повторяют условия задачи. Однако далее мне пришлось написать ещё немного кода, чтобы задать правила взаимодействия всех этих элементов. Но прежде чем описывать этот код, я покажу решение. Я не знал, чего ожидать: выдаст ли решатель ограничений решение или зависнет навечно? Оказалось, что он нашёл единственное решение за 109 миллисекунд и вывел массивы результата. Массив pips показывает количество очков в каждой клетке, а dominogrid — какая костяшка домино (с номером от 1 до 4) расположена в каждой позиции.

pips = 
[| 4, 2, 0
 | 4, 5, 3
 | 1, 1, 1
 |];
dominogrid = 
[| 3, 3, 0
 | 2, 1, 4
 | 2, 1, 4
 |];

Текстовое представление решения выглядит, конечно, грубовато. Но создать графический вывод довольно просто. MiniZinc предоставляет JavaScript API, поэтому можно легко отображать решения на веб-странице. Я написал несколько строк на JavaScript, которые рисуют решение, как показано ниже. (Я вывел только числа, потому что мне было лень рисовать точки.) Решение этой головоломки не слишком впечатляет — всё-таки она уровня «easy», — но ниже я покажу, что решатель справляется и с гораздо более сложными пазлами.

Подробности кода

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

Главное архитектурное решение заключалось в том, как задавать расположение домино. Я рассматривал вариант, при котором каждому домино назначается позиция на сетке и ориентация, но работать с разными ориентациями показалось неудобным. Вместо этого я решил задавать координаты для каждой половинки домино отдельно — с координатами x и y на сетке.^{(прим. 2)} Я добавил ограничение, что две половины каждого домино должны находиться в соседних клетках, то есть их координаты по X или по Y должны отличаться на 1.

constraint forall(i in DOMINO) (abs(x[i, 1] - x[i, 2]) + abs(y[i, 1] - y[i, 2]) == 1);

Пришлось немного подумать, как заполнить массив pips количествами очков на домино. В обычном языке программирования мы бы просто прошлись циклом по домино и записали значения в pips. Здесь же это делается через ограничение, и уже решатель следит за тем, чтобы значения были присвоены. Конкретно: для каждой половины домино элемент массива pips по координатам x/y этой половины должен быть равен соответствующему значению из spots:

constraint forall(i in DOMINO, j in HALF) (pips[y[i,j], x[i, j]] == spots[i, j]);

Я решил добавить ещё один массив, чтобы отслеживать, какое домино стоит в какой позиции. Этот массив полезен для наглядного вывода расположения домино, но он также не даёт домино накладываться друг на друга. Я использовал ограничение, которое записывает номер домино (1, 2, 3 и т. д.) в соответствующую занятую клетку массива dominogrid:

constraint forall(i in DOMINO, j in HALF) (dominogrid[y[i,j], x[i, j]] == i);

Дальше — как убедиться, что домино попадают только в позиции, разрешённые сеткой grid? Для этого я использовал ограничение: клетка в dominogrid должна быть пустой, либо соответствующая клетка в grid должна допускать домино.^{(прим. 3)} Здесь используется операция «или», которая записывается как \/ — довольно необычный синтаксический выбор. (Аналогично, «и» записывается как /\. Эти обозначения соответствуют логическим символам ∨ и ∧).

constraint forall(i in 1..H, j in 1..W) (dominogrid[i, j] == 0 \/ grid[i, j] != 0);

Честно говоря, я переживал, что у меня слишком много массивов, и решатель увязнет, пытаясь поддерживать их согласованность. Но я решил попробовать такой лобовой подход и посмотреть, что получится. В итоге он в целом сработал, так что ничего более хитрого мне придумывать не пришлось.

Наконец, программе нужно несколько строк, чтобы определить константы и переменные. Следующие константы задают количество домино и размеры сетки для конкретной задачи:

int: NDOMINO = 4; % Number of dominoes in the puzzle
int: W = 3; % Width of the grid in this puzzle
int: H = 3; % Height of the grid in this puzzle

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

set of int: DOMINO = 1..NDOMINO; % Dominoes are numbered 1 to NDOMINO
set of int: HALF = 1..2; % The domino half is 1 or 2
set of int: xcoord = 1..W; % Coordinate into the grid
set of int: ycoord = 1..H;

И наконец, я задаю размеры и типы всех используемых массивов. Очень важный элемент синтаксиса — ключевое слово var, которое помечает переменные, значения которых должен подобрать решатель. Обратите внимание, что у первых двух массивов, grid и spots, var нет: это константы, которые и задают саму задачу.

array[1..H,1..W] of 0..1: grid; % The grid defining where dominoes can go
array[DOMINO, HALF] of int: spots; % The number of spots on each half of each domino
array[DOMINO, HALF] of var xcoord: x; % X coordinate of each domino half
array[DOMINO, HALF] of var ycoord: y; % Y coordinate of each domino half
array[1..H,1..W] of var 0..6: pips; % The number of pips (0 to 6) at each location.
array[1..H,1..W] of var 0..NDOMINO: dominogrid; % The domino sequence number at each location

Весь код можно найти на GitHub. Забавный момент в том, что, поскольку код непроцедурный, строки можно располагать почти в любом порядке. Можно использовать массивы или константы до того, как они объявлены. Можно даже перенести include-операторы в конец файла, если захочется!

Осложнения

В целом, пользоваться решателем оказалось гораздо проще, чем я ожидал. Однако без сложностей всё же не обошлось.

Если изменить настройку, решатель может искать не одно решение, а множество. Но когда я попробовал это сделать, он сгенерировал тысячи бессмысленных решений. При ближайшем рассмотрении выяснилось, что проблема в том, что решатель подставлял произвольные числа в «пустые» клетки, получая формально корректные, но по сути бессмысленные варианты. Оказалось, я просто явно не запретил такое поведение, и хитрый решатель ограничений радостно наделал кучу решений, которые мне были не нужны. Добавление ещё одного ограничения решило проблему. Мораль: даже если вам кажется, что вы чётко описали все условия, решатели ограничений очень хорошо умеют находить нежелательные решения, которые формально этим условиям соответствуют. ^{(прим. 4)}

Вторая проблема в том, что если вы где-то ошиблись, решатель просто говорит, что задача неразрешима. Возможно, есть какой-то изящный способ отладки, но я в итоге просто по очереди убирал ограничения, пока задача снова не начинала иметь решения, а потом уже смотрел, что не так с последним добавленным ограничением. (Например, в какой-то момент я перепутал индексы массива, и задача стала принципиально неразрешимой.)

Самая неприятная особенность — непредсказуемость времени работы: решатель может отработать за миллисекунды, а может — за часы. Например, сложная головоломка Pips от 5 октября (см. ниже) заставила решатель работать несколько минут без видимых причин. Однако в MiniZinc IDE можно переключаться между разными backend-решателями. Я сменил стандартный Gecode на Chuffed, и тот тут же нашёл множество решений — если точнее, 384. (Иногда у головоломок Pips действительно бывает несколько решений, что вызывает споры среди игроков.) Я подозреваю, что наличие множества решений как-то сбило Gecode, возможно, он не смог сузить поиск до «хорошей» ветки дерева перебора. Бенчмарк разных решателей приведён в сноске.^{(прим. 5)}

Как работает решатель ограничений?

Если бы вы писали программу для решения Pips «с нуля», у вас, скорее всего, был бы цикл, перебирающий варианты размещения домино на поле. Проблема в том, что количество вариантов растёт экспоненциально. Если у вас есть 16 домино, то для первой костяшки — 16 вариантов, для второй — 15, и так далее: всего примерно 16! комбинаций, и это ещё без учёта ориентаций. Это удобно представлять как дерево поиска: на первом шаге — 16 ветвей. На следующем каждая из них разветвляется на 15 подветвей, затем на 14, и так далее.

Простая оптимизация заключается в проверке ограничений после добавления каждой костяшки. Например, как только нарушается ограничение «значение меньше 5», можно сделать бэктрекинг и пропустить целую ветку дерева. Так можно обойти только часть возможных вариантов — веток всё равно много, но, возможно, это будет приемлемо.

Решатель ограничений работает похожим образом, но более абстрактно. Он присваивает значения переменным, откатываясь назад при обнаружении конфликта. Поскольку исходная задача обычно NP-полная, решатель использует эвристики, чтобы ускорить работу. Например, переменные можно назначать в разном порядке. Решатель старается как можно раньше создавать конфликты, чтобы большие части дерева поиска можно было отбросить. (В случае домино это похоже на попытку сперва размещать костяшки в самых «жёстких» местах головоломки, а не в удобных свободных клетках.)

Ещё один приём — распространение ограничений (constraint propagation). Идея в том, что можно выводить новые ограничения и раньше находить конфликты. Например, представим, что у нас есть задача с ограничениями «a равно c» и «b равно c». Если присвоить значения «a = 1» и «b = 2», конфликт проявится только позже, когда мы попробуем подобрать значение для «c». Но при распространении ограничений мы можем вывести новое ограничение «a равно b», и проблема обнаружится сразу. (Решатели умеют работать и с более сложным распространением ограничений, например с неравенствами.) Обратная сторона в том, что генерация новых ограничений занимает время и раздувает задачу, так что распространение ограничений может замедлить решатель. Поэтому применимость этого приёма тоже выбирается эвристически.

Исследователи активно разрабатывают новые алгоритмы, эвристики и оптимизации,^{(прим. 6)} такие как более агрессивный откат по дереву поиска (backjumping), ведение списка неудачных присваиваний переменных (так называемые «nogoods») и использование булевых SAT-решателей (решателей задач выполнимости). Решатели соревнуются на ежегодных конкурсах, где эти техники сравнивают в боевых условиях. Приятная особенность решателей ограничений в том, что вам не нужно во всём этом разбираться: все эти приёмы применяются автоматически.

Заключение

Надеюсь, мне удалось показать, что решатели ограничений — это интересный инструмент, который не так уж страшен и способен решать реальные задачи без больших усилий. Даже будучи новичком, я довольно быстро начал работать с MiniZinc (я прочитал половину туториала, а потом сразу перешёл к написанию кода).

Одна из причин обратить внимание на решатели ограничений — в том, что это принципиально иной парадигмальный подход к программированию. Использование решателя похоже на программирование на более высоком уровне абстракции: вы не думаете о том, как именно решается задача и какой алгоритм используется. Кроме того, анализ задачи в терминах ограничений — это другой способ мыслить об алгоритмах. Порой бывает неприятно, что нельзя воспользоваться привычными конструкциями вроде циклов и присваиваний, но это расширяет кругозор.

И, наконец, писать код, который решает головоломку, на мой взгляд, куда веселее, чем решать их вручную, так что попробуйте сами!

Примечания и ссылки

1. Я начал с того, что скачал MiniZinc IDE и прочитал руководство по MiniZinc. Интерфейс MiniZinc IDE довольно простой: окно редактора в верхней части и окно вывода в нижней. Нажатие кнопки «Run» приводит к тому, что IDE генерирует решение.

2. Возможно, было бы аккуратнее объединить координаты X и Y в единый тип Point, используя тип записи (record) в MiniZinc.

3. Позже я решил, что логичнее требовать, чтобы dominogrid была пустой тогда и только тогда, когда соответствующая ячейка grid равна 0, хотя на само решение это не влияет. Это ограничение использует оператор «если и только если» <->.

constraint forall(i in 1..H, j in 1..W) (dominogrid[i, j] == 0 <-> grid[i, j] == 0);

4. Чтобы помешать решателю подставлять произвольные числа в неиспользуемые позиции массива pips, я добавил ограничение, которое заставляет эти значения быть равными нулю:

constraint forall(i in 1..H, j in 1..W) (grid[i, j] == 0 -> pips[i, j] == 0);

При генерации нескольких решений возникла вторая проблема, которую я и ожидал: симметричное домино можно разместить двумя избыточными способами. Например, домино «дубль шесть» можно перевернуть, и получится решение, которое технически отличается, но выглядит так же. Я исправил это, добавив для каждого симметричного домино ограничения, которые допускают только одну из двух избыточных позиций. Ограничение ниже навязывает предпочтительную ориентацию для симметричных домино.

constraint forall(i in DOMINO) (spots[i,1] != spots[i,2] \/ x[i,1] > x[i,2] \/ (x[i,1] == x[i,2] /\ y[i,1] > y[i,2]));

Чтобы включить режим поиска нескольких решений в MiniZinc, нужная настройка находится в Show Configuration Editor > User Defined Behavior > Satisfaction Problems, либо можно использовать флаг командной строки --all. 

5. В MiniZinc есть пять решателей, которые могут справляться с такими целочисленными задачами: Chuffed, OR-Tools CP-SAT, Gecode, HiGHS и Coin-OR BC. Я измерил производительность этих пяти решателей на 20 разных головоломках Pips. В большинстве случаев решатели находили решения менее чем за секунду, но разброс по времени был заметным.

В целом, Chuffed показал наилучшие результаты на тех задачах, которые я тестировал, укладываясь значительно менее чем в секунду. Google OR-Tools выиграл все категории в соревновании MiniZinc Challenge 2025 года, но для моих задач с Pips он был существенно медленнее Chuffed. Стандартный решатель Gecode в большинстве случаев работал очень хорошо, но на нескольких задачах показал себя крайне плохо, тратя более 15 минут. HiGHS в среднем был медленнее, занимая несколько минут на самых сложных задачах, но не проваливался так сильно, как Gecode. (Любопытно, что Gecode и HiGHS иногда считали сложными разные задачи.) Наконец, Coin-OR BC стабильно показывал себя плохо: в лучшем случае это были несколько секунд, но одна из головоломок решалась почти два часа, а другие так и не были решены до того, как я сдался спустя два часа. (Я не стал включать Coin-OR BC на график, потому что он портил масштаб.)

Не относитесь к этим результатам слишком серьёзно, поскольку разные решатели оптимизируются под разные цели. (В частности, Coin-OR BC рассчитан на линейные задачи.) Но эти результаты хорошо демонстрируют непредсказуемость решателей: иногда вы получаете решение за секунду, а иногда — через несколько часов. 

6. Если вы хотите детальнее узнать про решатели, хороший обзор даёт презентация «Задачи удовлетворения ограничений». Алгоритмы Gecode описаны в хорошем техническом отчёте «Алгоритмы программирования с ограничениями, используемые в Gecode». С Chuffed всё ещё сложнее: «Chuffed — это современный решатель с ленивой генерацией клауз, изначально спроектированный именно под этот подход. Lazy clause generation — гибридный метод решения задач с ограничениями, который сочетает в себе приёмы конечнодоменной пропагации и булевой выполнимости». Статья о Chuffed «Переосмысление ленивой генерации клауз» и сопутствующая презентация уже посерьёзнее для восприятия. 

Когда поигрался с MiniZinc и Pips, приходит мысль: «круто, но не хватает системного понимания алгоритмов поиска и современных подходов к AI, чтобы применять это не только к головоломкам». Если хочется прокачать именно фундамент — от точного покрытия до обучения с подкреплением — можно продолжить маршрут на демо-уроках OTUS от преподавателей курсов:

• 22 декабря, 20:00 — Dancing Links: задача о полном покрытии. Записаться

• 23 декабря, 20:00 — Классические алгоритмы RL: SARSA и Q-learning. Записаться