Судоку: правила, история и виды головоломки¶

Судоку — это логическая головоломка-пазл с числами, как правило, представленная в виде квадратной сетки 9×9, разделённой на девять меньших квадратов (блоков) со стороной 3×3. Цель игры заключается в заполнении пустых клеток сетки цифрами от 1 до 9 таким образом, чтобы в каждой строке, каждом столбце и в каждом малом блоке 3×3 каждая цифра встречалась ровно один раз. Судоку относится к классу комбинаторных задач с ограничениями и не требует математических вычислений, поскольку основано исключительно на дедуктивном мышлении и логике.

¶История происхождения

Предшественником современного судоку считается головоломка «Магический квадрат», известная в Китае ещё в древности. Однако непосредственным прототипом судоку является «Number Place» (с англ. — «Место числа»), созданная американским архитектором Ховардом Гарнсом в 1979 году. Впервые эта головоломка была опубликована в журнале Dell Pencil Puzzles and Word Games под названием «Number Place». Сетка Гарнса уже тогда имела современный вид 9×9 с частично заполненными клетками.

В Японии головоломка появилась в 1984 году, когда её опубликовала компания Nikoli в своём журнале. Японское название «数独» (су:доку) является сокращением фразы «су:дзи ва докусин ни кагиру» (яп. 数字は独身に限る), что переводится как «цифры должны быть одиночными». Именно в Японии головоломка приобрела массовую популярность и стандартизированные правила, включая требование симметричности расположения исходных цифр.

Международное признание пришло к судоку в середине 2000-х годов благодаря усилиям новозеландца Уэйна Гулда, который разработал компьютерную программу для генерации головоломок. В 2004 году он начал распространять судоку в британских газетах, что вызвало настоящий бум в Европе и Северной Америке. С 2005 года судоку регулярно публикуется в большинстве крупных мировых изданий.

¶Правила и терминология

Стандартное судоку состоит из 81 клетки. Часть клеток изначально заполнена числами — эти значения называются «данными» или «подсказками». Количество подсказок в корректной головоломке обычно варьируется от 17 до 36. Минимальное возможное число подсказок для однозначного решения классического судоку — 17; этот факт был доказан в 2012 году группой исследователей с использованием компьютерного перебора.

Основные правила:

• В каждой горизонтальной строке цифры от 1 до 9 не должны повторяться.
• В каждом вертикальном столбце цифры также не должны повторяться.
• В каждом блоке 3×3, ограниченном жирными линиями, все цифры должны быть уникальны.

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

¶Методы решения

Решение судоку предполагает последовательное применение логических приёмов. Базовым методом является вычёркивание: для каждой пустой клетки определяются все цифры, которые уже присутствуют в её строке, столбце и блоке; оставшиеся числа становятся кандидатами. Если кандидат остаётся один, клетка заполняется.

К более сложным техникам относятся:

• Открытые и скрытые пары, тройки: когда в нескольких клетках строки, столбца или блока присутствует одинаковый набор из двух (или трёх) кандидатов, эти значения можно исключить из остальных клеток данной группы.
• Метод «крыло X» (X-Wing): применяется, когда определённая цифра может находиться только в двух строках и двух столбцах, образующих прямоугольник.
• Меч-рыба (Swordfish): обобщение метода X-Wing на три строки и три столбца.
• Цепочки (XY-Chain): логические построения, связывающие клетки с двумя кандидатами для исключения значений.

Для головоломок высокой сложности иногда применяется метод «предположения и проверки» (backtracking), который формально не является чисто логическим, так как требует перебора вариантов.

¶Сложность и классификация

Сложность судоку определяется не количеством подсказок, а необходимостью применения тех или иных логических методов. Выделяют несколько уровней сложности: лёгкий, средний, сложный и экспертный. На лёгком уровне достаточно использования простых синглов; для экспертных требуются сложные техники, такие как X-Wing или цепочки.

Существуют также модификации и варианты судоку:

• Судоку 6×6 — упрощённый вариант для детей, использующий блоки 2×3.
• Судоку 16×16 — расширенная версия с цифрами и буквами от A до G.
• Самurai Sudoku — пять перекрывающихся сеток 9×9, образующих крестообразную структуру.
• Killer Sudoku (судоку-убийца) — вариант, в котором дополнительно задаются суммы чисел в пунктирных областях.
• Diagonal Sudoku — головоломка, в которой цифры не должны повторяться также на обеих главных диагоналях.

¶Математические свойства

С математической точки зрения судоку представляет собой задачу раскраски графа с латинским квадратом в основе. Количество возможных корректно заполненных сеток 9×9 было вычислено в 2005 году Бертрамом Фельгенхауэром и Фрейзером Джарвисом; оно составляет 6 670 903 752 021 072 936 960 (примерно 6,67 × 10²¹) вариантов. При учёте симметрий (поворотов, отражений, перестановок цифр) число существенно различных решений сокращается до 5 472 730 538.

Задача определения, имеет ли данная частично заполненная сетка решение, является NP-полной, что доказал Такаюки Ёнэмото в 2003 году. Это означает, что для произвольного судоку не существует известного эффективного алгоритма, который решал бы её за полиномиальное время, однако для стандартных головоломок с 17 и более подсказками решение находится достаточно быстро.

¶Применение и культурное влияние

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

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