Судоку

Материал из Википедии — свободной энциклопедии

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

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

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

Содержание

1 Правило игры
2 Разновидности
3 Происхождение
4 Математическая основа
5 Методы поиска решения
6 Настольная игра Судоку
7 Источники
- 7.1 Программное обеспечение
8 Литература

[править] Правило игры

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

[править] Разновидности

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

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

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

Для детей делают судоку меньших размеров с полем 4х4 и блоками 2х2.

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

Пример:

3						6
				8		4

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

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

[править] Происхождение

Настоящую популярность завоевала судоку (Sūdoku) только в наше время, когда японский журнал Nikoli начал регулярно публиковать на своих страницах эту головоломку (с 1986 года). Тогда же она и получила своё сегодняшнее обозначение. С 2005 года британская газета «Таймс» ([1]) стала печатать судоку и прославила её по всей Европе. Сегодня судоку — это обязательный компонент многих газет. Среди них много изданий с многомиллионными тиражами, например, немецкая газета «Цайт» (Die Zeit), австрийский «Стандарт» (Standard). Также публикуют судоку российская газета «Труд» и журнал «Всё ясно».

[править] Математическая основа

Количество возможных комбинаций в судоку 9x9 составляет по расчётам Бертхама Фельгенхауэра 6 670 903 752 021 072 936 960.

Если обобщить судоку на случай доски N²xN², задача обобщённого судоку является NP-полной (к судоку сводится задача о заполнении латинского квадрата, см. доказательство).

[править] Методы поиска решения

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

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

Будьте последовательны. Проверяйте ваши действия время от времени. Ошибка в начале может привести к неверному решению всей игры. Если Вы не находите правильного решения, попробуйте решить судоку позже. Иногда решение появляется внезапно, словно озарение.

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

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

Когда три ячейки имеют числа-кандидаты {12, 12, 13}, то число для третьей ячейки должно быть 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% решение заведёт в тупик — что означает, что выбранное число было неправильным. В таком случае нужно «смотать нить» — вернуться к «развилке» и выбрать и подставить другое число. Если не было допущено ошибок в решении, подставленное число будет единственным верным.

[править] Настольная игра Судоку

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