Судоку


Судо́ку (яп. 数独 су:доку, произношениео файле) — головоломка с числами. Судоку является латинским квадратом 9-го порядка. Иногда судоку называют магическим квадратом, что является неверным. Судоку активно публикуют газеты и журналы многих стран мира, сборники судоку издаются большими тиражами. Решение судоку является популярным видом досуга.

Игровое поле представляет собой квадрат размером 9×9, разделённый на меньшие квадраты со стороной в 3 клетки. Таким образом, всё игровое поле состоит из 81 клетки. В них уже в начале игры стоят некоторые числа (от 1 до 9), называемые подсказками. От игрока требуется заполнить свободные клетки цифрами от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3×3 каждая цифра встречалась только один раз.

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

Правильно составленная головоломка имеет только одно решение. Тем не менее на некоторых сайтах в интернете под видом усложнённых головоломок пользователю предлагаются варианты судоку с несколькими вариантами решения, а также с ветвлениями самого хода решения.

В XVIII веке Леонард Эйлер изобрёл игру «Carré latin» («Латинский квадрат»). На основе этой игры в 1970-х годах в Северной Америке были придуманы специальные числовые головоломки. Так в США судоку появилась впервые в 1979 году в журнале «Dell Puzzle Magazine». Тогда она называлась «Number Place». Настоящую популярность судоку завоевала в 1980—1990-х годах, когда японский журнал «Nikoli» начал регулярно публиковать на своих страницах эту головоломку (с 1986 года). Сегодня судоку — обязательный компонент многих газет. Среди них много изданий с многомиллионными тиражами: например, немецкая газета «Die Zeit»[1], австрийский «Der Standard»[2]. В России судоку также публикуются во многих газетах, журналах и специализированных сборниках.

Задача обобщённого судоку на поле является NP-полной, так как к ней сводится задача о заполнении латинского квадрата[3].