Судоку

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

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

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

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

Содержание

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

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

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

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

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

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

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

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

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

Пример:

3						6
				8		4

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

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

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

Прообраз судоку впервые встречается под именем «Carré latin» («латинский квадрат») и был изобретен швейцарским математиком Леонардом Эйлером в 18 веке. Этот квадрат не был разделен на 9 меньших квадратов. Настоящую популярность завоевала судоку (Sūdoku) только в наше время, когда японский журнал Nikoli начал регулярно публиковать на своих страницах эту головоломку. Тогда же она и получила своё сегодняшнее обозначение. С 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 в нижний левый угол.

[править] Русскоязычные ссылки в интернете

Русскоязычных ресурсов, посвященных судоку, в интернете пока немного. Например, сайт Play-Sudoku — портал о судоку на нескольких языках (русский в том числе), где можно после бесплатной регистрации получить доступ к практически неограниченному количеству судоку трёх степеней сложности, в которые можно играть в онлайновом режиме. Зарегистрированные игроки получают возможность участвовать в глобальном конкурсе и состязаться между собой. Существуют версии для печати.