Судоку

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

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

Содержание

Правило игры

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

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

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

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

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

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

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


Пример: 3.....6.* .*..8.4*. ..*...*.. .2.*4*... ..6.*...7 .379.*26. ..2..7*.4 .*.....15

  • .86..3.*


Теоретически могут существовать судоку и с малыми квадратами и с диагоналями, а так же с условием на все диагонали, а не только на две максимальных, но я таких не встречал.

Происхождение

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

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

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

Если обобщить судоку на случай доски N²×N², задача обобщённого судоку является 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 — портал о судоку на нескольких языках (русский в том числе), где можно после бесплатной регистрации получить доступ к практически неограниченному количеству судоку трёх степеней сложности, в которые можно играть в онлайновом режиме. Зарегистрированные игроки получают возможность участвовать в глобальном конкурсе и состязаться между собой. Существуют версии для печати.

Источники

(кроме упомянутых выше)

Программное обеспечение

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home