Энциклопедия судоку · Математика и вычисления

Математика судоку

Обновлено 2026-10-05

Латинский квадрат с блоками

В латинском квадрате каждый символ встречается один раз в каждой строке и каждом столбце. Заполненное судоку представляет собой латинский квадрат размера 9 с ещё одним условием: каждый из девяти блоков 3×3 также содержит каждую цифру один раз.

Источники: Wikipedia: Latin square

Сколько существует сеток

Бертрам Фельгенхауэр (Bertram Felgenhauer) и Фрейзер Джарвис (Frazer Jarvis) подсчитали заполненные сетки 9×9 в 2005 году: их 6 670 903 752 021 072 936 960, около 6,67 × 10²¹. Многие из них представляют собой одну и ту же сетку в изменённом виде. Если считать две сетки одной, когда одну можно превратить в другую перенумерацией цифр, поворотом или отражением либо перестановкой строк и столбцов способами, сохраняющими правильность сетки, останется 5 472 730 538 существенно различных сеток. Это число вычислили Эд Рассел (Ed Russell) и Фрейзер Джарвис.

Источники: Felgenhauer and Jarvis, Enumerating possible Sudoku grids (2005), OEIS A107739: number of Sudoku grids, Wikipedia: Mathematics of Sudoku

Минимум 17 подсказок

Ни одно стандартное судоку 9×9 с 16 или меньшим числом исходных цифр не имеет ровно одного решения. Гэри Макгуайр (Gary McGuire), Бастиан Тугеманн (Bastian Tugemann) и Жиль Сиварио (Gilles Civario) показали это с помощью полного компьютерного перебора и объявили результат в январе 2012 года. Семнадцать является минимумом, но не гарантией: многие сетки с 17 исходными цифрами по-прежнему имеют более одного решения.

Источники: McGuire, Tugemann and Civario, There is no 16-Clue Sudoku (arXiv 1201.0749)

Судоку как раскраска графа

Нарисуйте по одной вершине для каждой из 81 ячейки и соедините две вершины, если их ячейки находятся в одной строке, столбце или блоке. Этот граф судоку имеет 810 рёбер, а у каждой вершины ровно 20 соседей. Решить головоломку означает продолжить раскраску, заданную исходными цифрами, так, чтобы соединённые вершины никогда не имели одинаковый цвет. Требуется не менее девяти цветов, поскольку каждая строка, каждый столбец и каждый блок образуют группу из девяти вершин, каждая из которых соединена со всеми остальными. Любая заполненная сетка показывает, что девяти цветов достаточно.

Источники: Wikipedia: Sudoku graph

Сложно в общем случае, быстро для 9×9

Для сеток судоку, размер которых может расти без ограничений (n²×n² с блоками n×n), задача определения того, можно ли полностью заполнить частично заполненную сетку, является NP-полной. Этот результат Такаюки Ято (Takayuki Yato) и Такахиро Сэта (Takahiro Seta) опубликовали в 2003 году. Эффективные компьютерные программы обычно решают обычные головоломки 9×9 за доли секунды, хотя время зависит от программы, компьютера и головоломки.

Источники: Wikipedia: Mathematics of Sudoku, Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle

См. также

Источники

Все статьи →