Описание тега sudoku

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

Эта головоломка была популяризирована в 1986 году японской компанией Nikoli под названием Sudoku, что означает одно число. Он стал международным хитом в 2005 году.

О решении головоломок судоку написано много литературы, и они представляют собой очень интересный и распространенный предмет для математиков и программистов. Решение сложных головоломок судоку может включать в себя комбинаторику, теорию групп, вычислительную сложность, угадывание и отслеживание с возвратом. Общее количество различных сеток было рассчитано примерно как 6,671 × 10²¹, поэтому перебор сложных головоломок не всегда может быть успешным в желаемый период времени.

Следующие ресурсы более подробно исследуют логику и математику головоломок судоку:

• Математика судоку I Бертрама Фельгенгауэра и Фрейзера Джарвиса, 2006 г.
• Математика судоку от Клуба исследователей математики

История:

Числовые головоломки появились в газетах в конце 19 века, когда французские разработчики головоломок начали экспериментировать с удалением чисел из магических квадратов. Le Siècle, парижская ежедневная газета, 19 ноября 1892 года опубликовала частично заполненный магический квадрат 9×9 с субквадратами 3×3. Это не была судоку, потому что она содержала двузначные числа и требовала арифметики, а не логики. решить, но у него общие ключевые характеристики: каждая строка, столбец и подквадрат в сумме дают одно и то же число.

6 июля 1895 года соперник Ле Сикля, Ла Франс, усовершенствовал головоломку, превратив ее в почти современную судоку. Это упростило головоломку с магическим квадратом 9×9, так что каждая строка, столбец и ломаные диагонали содержали только числа 1–9, но не отмечали подквадраты. Хотя они не отмечены, каждый подквадрат 3×3 действительно содержит числа 1–9, и дополнительное ограничение на ломаные диагонали приводит только к одному решению.

Эти еженедельные головоломки появлялись во французских газетах, таких как L'Echo de Paris, около десяти лет, но исчезли примерно во время Первой мировой войны.

По словам Уилла Шортца, современная судоку, скорее всего, была разработана анонимно Говардом Гарнсом, 74-летним архитектором на пенсии и внештатным конструктором головоломок из Индианы, и впервые опубликована в 1979 году журналами Dell Magazines как Number Place (самые ранние известные примеры современных Судоку). Имя Гарнса всегда присутствовало в списке авторов выпусков Dell Pencil Puzzles и Word Games, которые включали Number Place, и всегда отсутствовало в выпусках, которых не было. Он умер в 1989 году, прежде чем получил шанс увидеть свое творение как всемирное явление. Неясно, был ли Гарнс знаком с какой-либо из французских газет, перечисленных выше.

Загадка была представлена ​​в Японии Николи в газете "Ежемесячный Николист" в апреле 1984 года как "Судзи ва докушин ни кагиру"(数字は独身に限る?), Что можно перевести как "цифры должны быть одиночными" или "цифры ограничены до один случай ". (По-японски "докушин" означает "неженатый человек".) Позднее Маки Кадзи (鍜治 真 Кадзи Маки?) Сократил это имя до Судоку (數 獨), взяв только первые кандзи из составных слов. чтобы сформировать более короткую версию. В 1986 году Николи представил два нововведения: количество заданных значений было ограничено до 32, а головоломки стали "симметричными"(то есть данные были распределены по вращательно-симметричным ячейкам). Сейчас он публикуется в основных японских периодических изданиях, таких как Asahi Shimbun.

Статья Википедии: http://en.wikipedia.org/wiki/Sudoku