Судоку

Так выглядит судоку

Судоку (яп. ж•з‹ су:доку, произношение  в «одинокая цифра») в популярная головоломка с цифрами. В переводе с японского «су» в «цифра», «доку» в «стоящая отдельно». Иногда судоку называют «магическим квадратом», что в общем-то не верно, так как судоку является латинским квадратом 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». Также публикует судоку российская газета «Труд».

Математическая основа

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

Долгое время оставался открытым вопрос о минимальном количестве подсказок, необходимых для однозначного решения судоку. В частности, не было известно, существует ли однозначно решаемая судоку с 16 подсказками. Проект распределённых вычислений Sudoku@vtaiwan на платформе BOINC занимался поиском такой судоку. В январе 2012 года появилось доказательство того, что однозначно решаемых судоку с 16 подсказками не существует.

Методы поиска решения

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

Лучший метод решения в записывать цифры-кандидаты в вершине левого угла ячейки, а затем вычёркивать невозможные по правилам игры цифры из данной ячейки. После этого можно увидеть именно те цифры, которые могут занимать данную ячейку. Играть в судоку рекомендуется медленно, так как это расслабляющая игра. Некоторые головоломки можно решить за несколько минут, но на другие можно потратить часы или, в отдельных случаях, даже дни. Правильно составленная головоломка имеет единственное решение. (Однако существуют случаи, когда возможны циклические перестановки среди некоторых цифр, при которых решение переходит в другое решение, отличное от первого. Это связано с тем, что в исходной головоломке может быть задано недостаточное количество цифр.)

Сначала смотрят на ряды, столбцы и блоки 3×3 с наиболее заполненными квадратами: легче решить там, где вариантов меньше. При заполнении ячейки нужно проверить столбец, ряд и блок 3×3. Нужно проверить, что все другие 8 цифр не дублируются. Легче избежать ошибок в начале игры, чем когда в решённой загадке обнаружится противоречие. Если колонка и ряд имеют одну незаполненную ячейку, то заполняйте её. При заполнении рядов и столбцов исключать цифры, которые уже вписаны.

Когда в судоку осталось несколько открытых ячеек в блоке 3×3 и только одна ячейка подходит для данной цифры, то именно эту цифру нужно записать в данную ячейку. Перед заполнением следует удостовериться, что вписываемая в ячейку цифра не будет встречаться в другой ячейке в том же столбце, строке или в блоке 3×3.

Когда в одном столбце, строке, или блоке 3×3 три любых ячейки имеют цифры-кандидаты {1,2; 1,2; 1,3}, то цифра для третьей ячейки должна быть 3. Потому что, если бы это была цифра 1, то в одной из первых двух ячеек была бы цифра 2, а в другой не было бы ничего, но такого быть не может, поскольку все клетки должны быть заполнены.

Имеются две стратегии, используемые для увеличения скорости решения головоломки.

Выбрать цифру, которая была найдена для большинства строк, столбцов или блоков 3×3 в судоку. Для каждого блока 3×3, который не содержит эту цифру, ищутся другие блоки 3×3 в том же самом ряду и столбце блоков 3×3, которые содержат эту «наиболее решённую цифру» и в решаемом блоке, исключаются места, где эта цифра, не может быть вписано в ячейку. Таким образом найдётся единственная ячейка для этой цифры.

Пример:

Цифра 9 встречается 6 раз в шести блоках 3×3. Таким образом, цифру 9 можно смело ставить в центральном нижнем блоке 3×3 в верхнем левом углу, а также во втором сверху правом блоке 3×3 в первой ячейке первого ряда. В центральном блоке 3×3 цифра 9 может стоять только в третьей ячейке второго ряда.

Пример:

Середина верхнего ряда блоков 3×3 и середина нижнего ряда блоков 3×3 почти полностью заполнены. В середине верхнего блока три нерешённых цифры в 1, 4, и 9. Анализируя такую ситуацию, можно вписать цифру 4 в центр блока, цифру 1 в правый верхний угол, а цифру 9 в в левый верхний угол. Аналогично можно поступить с нижним центральным блоком 3×3: в нём отсутствуют цифры 6, 8 и 9. Ячейки заполняются последовательно: цифру 6 ставим в центр, цифру 9 в нижний правый угол, а цифру 8 в нижний левый угол.

Наиболее сложные судоку можно решать методом исключения («нить Ариадны»), для этого на отдельном листе в клеточку записывается текущее положение дел, выбирается поле, в котором могут стоять только две цифры, при подстановке которых определяется как можно большее число пар в других клетках. Выбирается одна из цифр пары и подставляется в черновик. С вероятностью 50 % решение заведёт в тупик в что означает, что выбранная цифра была неправильной. В таком случае нужно «смотать нить» в вернуться к «развилке» и выбрать и подставить другую цифру. Если не было допущено ошибок в решении, подставленная цифра будет единственно верной.

Интересный подход к решению судоку использовал Cleve Moler, создатель пакета для научных расчётов MATLAB.

Разновидности

Самой простой модификацией судоку является судоку «чёт-нечёт». В них некоторые клетки изначально выделены цветом, в этих клетках находятся или только чётные, или только нечётные цифры.

В последнее время появились модификации большего размера, чем 9 на 9 клеток. Например, существуют судоку с размерами 12×12 или даже 16×16, предназначенные для опытных игроков.

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

Ещё один вариант судоку в с блоками не квадратной, а произвольной формы с тем же числом клеток. Для стандартного судоку 9×9 это блоки по 9 клеток.

Для детей делают судоку меньших размеров с полем 4×4 и блоками 2×2. Такие уменьшенные головоломки называют «шидоку» (Shidoku) от японского shi в четыре.

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

Пример:

3						6
				8		4
	2			4
		6						7
	3	7	9			2	6
		2			7			4
							1	5
		8	6			3

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

• Головоломки с другим размером игрового поля (от 4×4 до 25×25 клеток).
• Геометрические судоку с иным принципом разбиения на блоки, отличные от квадратов 3×3.
• «Судоку-Самурай» («Судоку-Комбо», «Судоку-Конструкции» и др.), в которых одна головоломка содержит сразу несколько отдельных судоку, связанных друг с другом общими клетками.
• «Судоку-Точки», где между соседними клетками выводится точка чёрного или белого цвета, когда соседние цифры отличаются на 1 или в два раза.
• «Судоку-Перегородки» («Судоку-Соседи»), где цифры в соседних клетках отличаются на 1.
• Судоку и множество её вариаций («Судоку-Произведения», «Судоку-Арифметика», «Квадросудоку», «Суммы-сбоку», «Суммы по диагонали» и т. п.), где всё поле делится на блоки, для которых сообщается сумма (произведение, разность и т. п.) всех входящих в него цифр
• Тудоку (Twodoku) представляет собой комбинацию из двух судоку, имеющих один общий блок. При этом каждая из этих двух головоломок не может быть решена по отдельности, существует только общее решение. Подсказки в общем блоке отсутствуют.

Настольная игра судоку

Существуют также настольные варианты игры. Подобные игры были изданы по всему миру различными издателями и разработчиками (к примеру, известный разработчик настольных игр Reiner Knizia издал свой вариант этой логической игры). В России можно встретить настольные судоку от фирмы Астрель и польской компании Trefi.

Компьютерные игры

• Sudoku в из набора игр GNOME Games.
• KSudoku в из набора игр KDE Games.

Версии для мобильных телефонов

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

Соревнования по решению судоку

Во многих странах проводятся различные турниры и соревнования по решению судоку. Чемпионаты мира по решению судоку проводит Международная федерация пазлспорта, с 2007 года в них определяется и команда-победительница.

Год	Место проведения	Чемпион	2-й призёр	3-й призёр	Команда-победительница
2006	Лукка	Jana Tylova (Чехия)	Thomas Snyder (США)	Wei-Hwa Huang (США)
2007	Прага	Thomas Snyder (США)	Yuhei Kusui (Япония)	Peter Hudak (Словакия)	Япония
2008	Гоа	Thomas Snyder (США)	Yuhei Kusui (Япония)	Jakub Ondrousek (Чехия)	Чехия
2009	Жилина	Jan Mrozowski (Польша)	Branko Ceranic (Сербия)	Robert Babilon (Чехия)	Словакия
2010	Филадельфия	Jan Mrozowski (Польша)	Jakub Ondrousek (Чехия)	Hideaki Jo (Япония)	Германия
2011	Эгер	Thomas Snyder (США)	Kota Morinishi (Япония)	Tiit Vunk (Эстония)	Германия

С 2006 года проводятся и чемпионаты России по решению судоку, организацией которых занимается клуб любителей головоломок «Диоген».

Год	Чемпион	2-й призёр	3-й призёр
2006	Ханмагомедов Риад	Богданов Андрей	Лемеш Андрей
2007	Ханмагомедов Риад	Богданов Андрей	Ершов Александр
2008	Богданов Андрей	Ханмагомедов Риад	Ершов Александр
2009	Кравченко Алексей (Беларусь)	Ершов Александр	Португалов Владимир (Беларусь)
2010	Ханмагомедов Риад	Кравченко Алексей	Португалов Владимир
2011	Ершов Александр	Ханмагомедов Риад	Португалов Владимир
2012	Ханмагомедов Риад	Ершов Александр	Португалов Владимир

См. также

• Какуро
• Кроссворд
• Японский кроссворд
• Латинский квадрат
• Четыре четверки

Ссылки

• Правила игры судоку.
• Как решать судоку.
• Более полное объяснение решения судоку (включая сложные методы).

Литература

• Эндрю Херон, Эдмунд Джеймс. Судоку для «чайников» = Su Doku for Dummies (Sudoku). в М.: «Диалектика», 2007. в С. 336. в ISBN 978-0-470-01892-7
• К. Кноп. Магический квадрат или Числа на плацу // Компьютерра. в В. 09.09.2000.