Sudoku и математика: неожиданная связь

Арифметика не требуется

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

Можно заменить цифры 1–9 буквами A–I, и головоломка будет идентична по сложности. Некоторые книги с головоломками так и делают для демонстрации. Используемый математический навык — не арифметика, а логика.

Поэтому Sudoku преодолевает языковые и образовательные барьеры. Ребёнок, не умеющий умножать, может решать Sudoku для новичков. Человек, не говорящий по-английски, решает те же головоломки, что и носитель. Универсальная природа логики Sudoku — ключевая причина её мировой популярности.

Комбинаторика: подсчёт решений Sudoku

С математической точки зрения Sudoku — задача комбинаторики. Число валидных заполненных сеток Sudoku 9×9, вычисленное Фельгенхауэром и Джарвисом в 2005 году, — примерно 6,67 секстиллиона. Это астрономически большое число.

С учётом эквивалентностей (повороты, отражения, перемаркировка цифр) число по сути разных сеток падает до около 5,47 миллиарда. Это сокращение приходит из применения концепций теории групп — групп симметрии, действующих на сетку.

Минимальное число подсказок для единственного решения — 17, доказано в 2012 году командой Гэри Макгуайра. Ни одна головоломка с 16 подсказками не имеет единственного решения. Доказательство потребовало огромных вычислительных усилий — проверки миллиардов конфигураций сеток.

Теория групп и латинские квадраты

Sudoku — частный случай латинского квадрата, сетки n×n, где каждый символ появляется ровно один раз в каждой строке и столбце. Эйлер изучал латинские квадраты в XVIII веке. Ограничение блоков Sudoku добавляет структуру, делая её «gerechte design» из экспериментальной статистики.

Теория групп изучает преобразования, сохраняющие структуру. В Sudoku операции вроде обмена строк внутри полосы, обмена столбцов внутри стека, поворота сетки или перемаркировки цифр сохраняют валидность головоломки. Множество всех таких операций образует математическую группу с 3 359 232 элементами.

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

Sudoku и искусственный интеллект

В информатике Sudoku — классическая задача удовлетворения ограничений (CSP). Исследователи используют Sudoku как бенчмарк для тестирования алгоритмов, включая backtracking, распространение ограничений, arc consistency и решатели булевой выполнимости.

Питер Норвиг, директор по исследованиям Google, опубликовал влиятельное эссе о решении Sudoku с распространением ограничений и поиском. Его Python-решатель мог решить любую Sudoku за миллисекунды. Статья стала стандартным учебным ресурсом в курсах информатики.

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