Что такое судоку
Судоку — логическая числовая головоломка, в которой нужно заполнить поле 9×9 клеток цифрами от 1 до 9 так, чтобы в каждой строке, каждом столбце и каждом из девяти квадратов 3×3 каждая цифра встречалась ровно один раз. Название происходит от японского «数独» (сÿдоку — «одинокое число»). Несмотря на японское название, головоломку в современном виде изобрёл американский архитектор Говард Гарнс в 1979 году для журнала Dell Magazines под названием Number Place. В Японию головоломка попала в 1984 году благодаря компании Nikoli, а мировой бум начался в 2004–2005 годах после публикации в газете The Times.
Правила
Правила судоку исключительно просты. Игровое поле представляет собой таблицу 9×9, разделённую на девять квадратов 3×3 (их называют блоками или боксами). Часть клеток уже заполнена цифрами — это подсказки (в стандартных головоломках их обычно от 17 до 35). Задача — заполнить все пустые клетки цифрами от 1 до 9, соблюдая три ограничения: ни одна цифра не повторяется в строке, в столбце и в блоке 3×3. Математически доказано, что минимальное количество подсказок для единственного решения — 17 (McGuire, Tugemann, Civario, 2012).
Методы решения
Базовые методы включают сканирование (проверка строк, столбцов и блоков для исключения кандидатов) и метод «голого одиночки» (naked single — клетка, в которой возможен только один кандидат). Метод «скрытого одиночки» (hidden single) находит цифру, которая в данном блоке, строке или столбце может стоять только в одной клетке. Продвинутые техники включают «голые пары/тройки/четвёрки» (группы клеток с ограниченным набором кандидатов, позволяющие исключить эти кандидаты из других клеток), X-Wing (паттерн в двух строках и двух столбцах для исключения кандидата), Swordfish (расширение X-Wing на три линии) и цепочки (coloring, forcing chains). Для самых сложных головоломок применяются методы trial and error (угадывание с проверкой) или алгоритм Кнута «Dancing Links».
Виды судоку
Помимо классического формата 9×9, существует множество вариаций. Мини-судоку (4×4 или 6×6) подходит для детей и начинающих. Диагональное судоку добавляет ограничение: на обеих главных диагоналях цифры тоже не повторяются. Самурай-судоку объединяет пять перекрывающихся полей 9×9. Дзигоку (Jigsaw) заменяет квадратные блоки фигурами неправильной формы. Killer-судоку добавляет «клетки» с указанной суммой цифр внутри них (и запретом повторов). Гигантские форматы 16×16 и 25×25 используют дополнительные символы (буквы или двузначные числа).
Математика судоку
Общее число различных заполненных сеток 9×9 составляет 6 670 903 752 021 072 936 960 (≈ 6,67 × 10²¹), что было вычислено Бертрамом Фельгенхауэром и Фразером Джарвисом в 2005 году. С учётом симметрий (повороты, отражения, перестановки цифр) число существенно различных сеток — 5 472 730 538. Задача решения судоку относится к классу NP-полных задач для обобщённого случая n²×n², хотя конкретные головоломки 9×9 решаются за доли секунды.
Таблица видов судоку
| Вид | Размер поля | Особенность | Сложность |
|---|---|---|---|
| Классическое | 9×9 | Стандартные правила | Простая–сложная |
| Мини | 4×4 / 6×6 | Уменьшенное поле | Простая |
| Диагональное | 9×9 | + ограничение диагоналей | Средняя |
| Самурай | 5 × (9×9) | Пять перекрывающихся полей | Сложная |
| Killer | 9×9 | Клетки с указанной суммой | Сложная |
| Jigsaw | 9×9 | Блоки неправильной формы | Средняя–сложная |
Интересный факт
Чемпионат мира по судоку проводится ежегодно Всемирной федерацией головоломок (WPF) с 2006 года. Рекорд решения классической сложной головоломки 9×9 — менее 2 минут. Ежедневно во всём мире головоломки судоку решают десятки миллионов людей, а приложение Sudoku.com было загружено более 100 миллионов раз.
