Раскрывая секреты судоку

В судоку находят применение два известных математических подхода: теория графов и компьютерная алгебра. В статье Chalkdust подробно разбираются оба направления с пошаговыми примерами.

Судоку как раскраска вершин

Каждая из 81 клетки представляет собой вершину, обозначенную упорядоченной парой $(x, y)$. Две разные вершины соединяются ребром, если они находятся в одной строке, в одном столбце или в одном блоке 3×3. Корректное решение судоку в таком случае - это правильная 9-раскраска графа: каждой вершине присваивается один из девяти цветов так, чтобы у любого ребра концы были разного цвета. Исходное судоку имеет решение тогда и только тогда, когда граф допускает 9-раскраску.

В статье объединяются жадный алгоритм и backtracking:

1. Выбрать первую незакрашенную клетку.
2. Присвоить ей наименьшее допустимое число.
3. Перейти к следующей незакрашенной клетке и повторить.
4. При возникновении конфликта (допустимых чисел не осталось) вернуться к предыдущей клетке, выбрать следующее подходящее число и продолжить жадный выбор оттуда.

В разобранном примере жадный алгоритм ставит 8 в клетку (1, 7) (поскольку числа 4 - 6 конфликтуют с соседними клетками), затем заходит в тупик на (1, 8), возвращается к (1, 7), пробует 9 и продолжает работу. Упомянутые смежные работы: Joshua Cooper и Anna Kirkpatrick о минимальных наборах и минимальных корректных головоломках; Michael Haythorpe, связывающий гамильтоновы циклы с судоку разных размеров.

Судоку через базисы Грёбнера

Судоку можно представить и как задачу удовлетворения ограничений над целыми числами 1 - 9 - именно с такими задачами работает компьютерная алгебра. В статье вводится необходимый аппарат:

• Кольцо многочленов $\mathbb{Q}[x_0, \dots, x_{80}]$ - по одной переменной на каждую клетку.
• Идеал - аддитивное подмножество, замкнутое относительно умножения на элементы кольца; порождается набором многочленов.
• Порядок мономов (term ordering) - фиксированный порядок на мономах. Лексикографический для пояснения и degrevlex (degree-reverse-lex) для реального вычисления базиса Грёбнера.
• Старший член (leading term) - наибольший член в выбранном порядке. Базис Грёбнера $G$ для идеала $I$ - это такой базис, для которого $\operatorname{lt}(G) = \operatorname{lt}(I)$.

Полезное свойство состоит в том, что базис Грёбнера приводит систему к треугольному виду: $g_1$ зависит только от $x_1$, $g_2$ зависит от $x_1$ и $x_2$ со старшим членом по $x_2$ и так далее. Подстановка становится чисто механической.

Представление судоку в виде многочленов:

• Каждая клетка принимает значения 1 - 9: $(x_i - 1)(x_i - 2)\cdots(x_i - 9) = 0$ для каждой клетки.
• Сумма чисел в каждой строке, каждом столбце и блоке равна 45, а их произведение - $9! = 362{,}880$. Это исключает дубликаты.
• Для каждой предварительно заполненной клетки со значением $a_j$: $x_j - a_j = 0$.

Получается 135 многочленов плюс по одному на каждую известную клетку. Запуск алгоритма Бухбергера вычисляет базис Грёбнера для этого идеала. Если у головоломки единственное решение, базис состоит из 81 линейного многочлена, и решение считывается напрямую.

Бруно Бухбергер ввёл базисы Грёбнера в своей докторской диссертации 1965 года, назвав их в честь своего научного руководителя Вольфганга Грёбнера.

Пример с сидоку

Сидоку (shidoku) - это версия 4×4 с четырьмя блоками 2×2. Здесь 16 переменных, многочлены допустимых значений $(x_i-1)(x_i-2)(x_i-3)(x_i-4)$, суммы по строкам, столбцам и блокам равны 10, а произведения - 24, плюс уравнения для известных клеток. Всего 40 многочленов, дополненных пятью заранее заполненными клетками. При передаче их в функцию gbasis в Matlab полученный базис представляет собой линейную систему из 16 уравнений, откуда однозначно считывается решение.

Для чего это полезно

Оба подхода допускают обобщение. Решатели на основе раскраски графов с backtracking тривиально расширяются на более сложные задачи с ограничениями; подход на базисах Грёбнера применим к любой задаче с ограничениями, выразимой в виде системы полиномиальных уравнений над полем, что охватывает большинство комбинаторных головоломок. Компромисс здесь стандартный: backtracking быстр на практике, но в худшем случае экспоненциален; вычисление базиса Грёбнера имеет плохую сложность в худшем случае (дважды экспоненциальную по числу переменных), но после нахождения базиса превращает поиск в чистую алгебраическую подстановку.

Статья перекликается с нейросимволическими темами в вики - см. neurosymbolic-ai о более общем паттерне объединения поиска с символьными решателями ограничений.