2018-03-01 16:35:31
История Судоку
История самой популярной японской игры
Показать все →
Судо́ку (яп. 数独 су:доку, произношение (инф.) ) — головоломка с числами. Иногда судоку называют магическим квадратом, что в общем-то неверно, так как судоку является латинским квадратом 9-го порядка. Судоку активно публикуют газеты и журналы разных стран мира, сборники судоку издаются большими тиражами. Решение судоку — популярный вид досуга.
Правила
Игровое поле представляет собой квадрат размером 9×9, разделённый на меньшие квадраты со стороной в 3 клетки. Таким образом, всё игровое поле состоит из 81 клетки. В них уже в начале игры стоят некоторые числа (от 1 до 9), называемые подсказками. От игрока требуется заполнить свободные клетки цифрами от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3×3 каждая цифра встречалась бы только один раз.
Сложность судоку зависит от количества изначально заполненных клеток и от методов, которые нужно применять для её решения. Самые простые решаются дедуктивно: всегда есть хотя бы одна клетка, куда подходит только одно число. Некоторые головоломки можно решить за несколько минут, на другие можно потратить часы.
Правильно составленная головоломка имеет только одно решение. Тем не менее, на некоторых сайтах в интернете под видом усложнённых головоломок пользователю предлагаются варианты судоку с несколькими вариантами решения, а также с ветвлениями самого хода решения.
Происхождение
В XVIII веке Леонард Эйлер изобрёл игру «Carré latin» («Латинский квадрат»). На основе этой игры в 70-х годах прошлого века в Северной Америке были придуманы специальные числовые головоломки. Так, в США судоку появилась впервые в 1979 году в журнале «Dell Puzzle Magazine». Тогда она называлась «Number Place». Настоящую популярность судоку завоевала в 1980—1990-х годах, когда японский журнал «Nikoli» начал регулярно публиковать на своих страницах эту головоломку (с 1986 года). Сегодня судоку — обязательный компонент многих газет. Среди них много изданий с многомиллионными тиражами, например, немецкая газета «Die Zeit»[, австрийский «Der Standard». Также публикует судоку российская газета «Труд».
Математическая основа
Задача обобщённого судоку на поле {\displaystyle N^{2}\times N^{2}} [{\displaystyle N^{2}\times N^{2}}] является NP-полной, так как к ней сводится задача о заполнении латинского квадрата.
Долгое время оставался открытым вопрос о минимальном количестве подсказок, необходимых для однозначного решения судоку. В частности, не было известно, существует ли однозначно решаемая судоку с 16 подсказками. Проект распределённых вычислений Sudoku@vtaiwan на платформе BOINC занимался поиском такой судоку. В январе 2012 года появилось доказательство того, что однозначно решаемых судоку с 16 подсказками не существует.
Разновидности
Существует множество вариаций судоку:
- Нерегулярное судоку (их ещё называют Судоку-пазл, Судоку-фигуры, Области). В этой головоломке вместо стандартных областей 3x3 используются области произвольной формы. Цифры не должны повторяться в каждой такой области.
- Судоку разных размеров. Встречаются судоку размером от 4x4 (такие уменьшенные головоломки называют «шидоку» (Shidoku) от японского shi — четыре) до 25x25. Наиболее распространены судоку небольших размеров для детей.
- Судоку с дополнительными областями. В этих задачах помимо стандартных областей (вертикалей, горизонталей и блоков) задаются дополнительные области, в которых цифры не могут повторяться. Наиболее распространены диагональные судоку.
- Судоку с дополнительными условиями. В таких задачах помимо стандартного условия неповторяемости цифр задаются ещё дополнительные условия на значения. Например:
- Судоку «Суммы» и множество её вариаций («Судоку-Произведения», «Судоку-Арифметика», «Квадросудоку», «Суммы-сбоку», «Суммы по диагонали» и т. п.), где всё поле делится на блоки, для которых сообщается сумма (произведение, разность и т. п.) всех входящих в него цифр.
- Судоку «Чёт-нечёт». В них некоторые клетки изначально выделены цветом, в этих клетках находятся или только чётные, или только нечётные цифры.
- Судоку «Больше-меньше». Для некоторых соседних клеток указан знак, показывающий в какой из клеток цифра больше.
- Судоку «Точки», где между соседними клетками выводится точка белого или чёрного цвета, когда соседние цифры отличаются на 1 или в два раза.
- Судоку «Перегородки» («Судоку-Соседи»), где отмечены все места с цифрами в соседних клетках отличающихся на 1.
- Судоку другой формы. В головоломке используется не квадратная сетка, а треугольная, шестиугольная или более хитроумной формы.
- Сцепленные судоку. «Судоку-Самурай» («Судоку-Комбо», «Судоку-Конструкции», «Тудоку» и др.), в которых несколько отдельных судоку имеют общие блоки и решаются взаимозависимо.
Настольная игра судоку
Существуют также настольные варианты игры. Подобные игры были изданы по всему миру различными издателями и разработчиками (к примеру, известный разработчик настольных игр Reiner Knizia издал свой вариант этой логической игры). В России можно встретить настольные судоку от фирмы Астрель и польской компании Trefi.
Компьютерные игры
Для персональных компьютеров существует достаточно много вариантов данной игры, выпускаемых различными компаниями-разработчиками для разных платформ, например,
Sudoku (из набора игр GNOME Games) или KSudoku (из набора игр KDE Games) — для Linux-платформ,
Microsoft Sudoku (доступная для ОС Windows 8.1 или Windows 10 в Windows Store) — для Windows-платформ.
Версии для мобильных телефонов
Существуют несколько версий игры для мобильных телефонов, а также для смартфонов. Эти версии удобны тем, что могут сами создавать условие головоломки. Также они указывают на ошибки (противоречащие цифры подсвечиваются) или могут дать подсказку в решении. 9 цифр в стандартных судоку, назначенные на 9 цифровых кнопок на мобильном телефоне, делают процесс игры очень удобным.
С появлением смартфонов игра заняла достойное место среди самых популярных. С выходом на рынок устройств на базе Android и iOS, количество поклонников игры резко возросло.
По материалам https://ru.wikipedia.org/