Судоку: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
[отпатрулированная версия][непроверенная версия]
Содержимое удалено Содержимое добавлено
отклонены последние 2 изменения от 88.249.192.88
Метка: ручная отмена
орфография
 
(не показаны 33 промежуточные версии 22 участников)
Строка 1: Строка 1:
[[Файл:Sudoku-by-L2G-20050714.svg|мини|216x216пкс|Судоку]]
{{нет ссылок|дата=9 августа 2017}}
'''Судо́ку'''<ref>{{Cite web|url=https://gramota.ru/meta/sudoku|title=Грамота.ру — Судоку|access-date=2024-09-13|archive-date=2024-09-13|archive-url=https://web.archive.org/web/20240913230258/https://gramota.ru/meta/sudoku|url-status=live}}</ref> (от {{lang-ja|数独}} ''су:доку'') — [[головоломка]] с числами. Судоку является [[Латинский квадрат|латинским квадратом]] 9-го порядка. Иногда судоку называют [[Магический квадрат|магическим квадратом]], это обозначение неверно. Судоку активно публикуют газеты и журналы многих стран мира, сборники судоку издаются большими тиражами. Решение головоломки — популярный вид досуга.
[[Файл:Sudoku-by-L2G-20050714.svg|thumb|300px|Судоку]]
{{нихонго|'''Судо́ку'''|数独|су:доку|{{Audio|Ja-Sudoku.oga|произношение}}}} — [[головоломка]] с числами. Иногда судоку называют [[Магический квадрат|магическим квадратом]], что в общем-то неверно, так как судоку является [[Латинский квадрат|латинским квадратом]] 9-го порядка. Судоку активно публикуют газеты и журналы многих стран мира, сборники судоку издаются большими тиражами. Решение судоку — популярный вид досуга.


== Правила ==
== Правила ==
Игровое поле представляет собой [[квадрат]] размером 9×9, разделённый на меньшие квадраты со стороной в 3 клетки. Таким образом, всё игровое поле состоит из 81 клетки. В них уже в начале игры стоят некоторые числа (от 1 до 9), называемые ''подсказками''. От игрока требуется заполнить свободные клетки цифрами от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3×3 каждая цифра встречалась бы только один раз.
Игровое поле представляет собой квадрат размером 9×9, разделённый на меньшие квадраты со стороной в 3 клетки. Таким образом, всё игровое поле состоит из 81 клетки. В них уже в начале игры стоят некоторые числа (от 1 до 9), называемые ''подсказками''. От игрока требуется заполнить свободные клетки цифрами от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3×3 каждая цифра встречалась только один раз.


Правильно составленная головоломка имеет только одно решение. Тем не менее, на некоторых интернет-сайтах, под видом усложнённых головоломок пользователю предлагаются варианты судоку с несколькими вариантами решения, а также с ветвлениями самого хода решения.
Сложность судоку зависит от количества изначально заполненных клеток и от методов, которые нужно применять для её решения. Самые простые решаются дедуктивно: всегда есть хотя бы одна клетка, куда подходит только одно число. Некоторые головоломки можно решить за несколько минут, на другие можно потратить часы.


== Сложность ==
Правильно составленная головоломка имеет только одно решение. Тем не менее, на некоторых сайтах в интернете под видом усложнённых головоломок пользователю предлагаются варианты судоку с несколькими вариантами решения, а также с ветвлениями самого хода решения.
Сложность судоку зависит от количества изначально заполненных клеток и методов, которые нужно применять для её решения. Самые простые решаются дедуктивно: всегда есть хотя бы одна клетка, куда подходит только одно число. Некоторые головоломки можно решить за несколько минут, на другие можно потратить несколько часов.

В 2012 году финский математик Арто Инкала заявил, что разработал «самую трудную в мире судоку», которая получила название «Эверест». Если самые простые из распространённых вариантов судоку по шкале сложности обозначить, как «1», а наиболее сложные из популярных оценить на «5», то предложенный математиком вариант имеет сложность «11»<ref>{{Cite web|url=https://metro.co.uk/2012/06/28/worlds-hardest-sudoku-everest-created-by-mathematician-arto-inkala-483588/amp/|title=Mathematician Arto Inkala creates world’s hardest Sudoku, ‘Everest’|lang=en|access-date=2024-09-23}}</ref>.


== Происхождение ==
== Происхождение ==
В XVIII веке [[Эйлер, Леонард|Леонард Эйлер]] изобрёл игру «{{lang-fr2|Carré latin}}» («Латинский квадрат»). С конца XIX века многие французские газеты издавали похожую головоломку<ref>{{Cite web|url=http://cboyer.club.fr/multimagie/English/SudokuAncestors.htm|title=MULTIMAGIE.COM - Sudoku's French ancestors|website=web.archive.org|date=2007-10-10|access-date=2024-08-10|archive-date=2007-10-10|archive-url=https://web.archive.org/web/20071010081626/http://cboyer.club.fr/multimagie/English/SudokuAncestors.htm|url-status=dead}}</ref><ref>{{Статья|ссылка=http://cboyer.club.fr/multimagie/SupplAncetresSudoku.pdf|заглавие=Supplément de l’article
В [[XVIII век]]е [[Эйлер, Леонард|Леонард Эйлер]] изобрёл игру «{{lang-fr2|Carré latin}}» («''Латинский квадрат''»). На основе этой игры в [[1970-е годы|1970-х годах]] в [[Северная Америка|Северной Америке]] были придуманы специальные числовые [[головоломки]]. Так, в [[США]] судоку появилась впервые в [[1979 год]]у в журнале «''Dell Puzzle Magazine''». Тогда она называлась «''Number Place''». Настоящую популярность судоку завоевала в 1980—1990-х годах, когда японский журнал «[[Nikoli]]» начал регулярно публиковать на своих страницах эту головоломку (с [[1986 год]]а). Сегодня судоку — обязательный компонент многих газет. Среди них много изданий с многомиллионными тиражами, например, немецкая газета «[[Die Zeit]]»<ref>[http://apollo.zeit.de/sudoku/ Die Zeit] {{Wayback|url=http://apollo.zeit.de/sudoku/ |date=20050912033222 }}{{ref-de}}</ref>, австрийский «[[Der Standard]]»<ref>[http://derstandard.at/sudoku Der Standard ›Lifestyle›Spielen & Lesen›Spielen›Sudoku] {{Wayback|url=http://derstandard.at/sudoku |date=20050827224535 }}{{ref-de}}</ref>. В России судоку также публикуются в десятках{{уточнить|причина=это фигура речи? Или точно известно, что их и в самом деле «десятки», а например не сотни? Если первое, то может лучше «во многих»?}}{{нет АИ|22|01|2022}} газет, журналов и в специализированных сборниках.
« Les ancêtres français du sudoku »|издание=|archivedate=2006-12-10|archiveurl=https://web.archive.org/web/20061210103525/http://cboyer.club.fr/multimagie/SupplAncetresSudoku.pdf}}</ref>.

Изобретателем головоломки в современном виде, вероятно, является 74-летний архитектор Говард Гарнс. Впервые она была опубликована в 1979 году под названием Number Place американской компанией Dell Magazines, которая занималась изданием журналов, книг и комиксов<ref name=":0">{{Cite web|url=https://www.mathpuzzle.com/MAA/41-Sudoku%20Variations/mathgames_09_05_05.html|title=Math Games:Sudoku Variations|website=www.mathpuzzle.com|access-date=2024-08-10|archive-date=2024-07-27|archive-url=https://web.archive.org/web/20240727154509/https://www.mathpuzzle.com/MAA/41-Sudoku%20Variations/mathgames_09_05_05.html|url-status=live}}</ref><ref name=":1">{{Cite news|title=So you thought Sudoku came from the Land of the Rising Sun ...|first=David|last=Smith|url=https://www.theguardian.com/media/2005/may/15/pressandpublishing.usnews|website=The Observer|id=0029-7712|date=2005-05-15|access-date=2024-08-10|lang=en-GB|archive-date=2013-08-29|archive-url=https://web.archive.org/web/20130829045004/http://www.theguardian.com/media/2005/may/15/pressandpublishing.usnews|url-status=live}}</ref>.

В [[Япония|Японии]] игра была впервые представлена [[Кадзи, Маки|Маки Кадзи]] в апреле 1984 года под названием «Sūji wa dokushin ni kagiru» ({{lang-ja|数字は独身に限る}}), что в данном случае переводится как «Цифры должны быть одни». Слово из [[кандзи]] ({{lang-ja|独身}}) имеет обозначение «Одинокий человек, не состоящий в отношениях». Позже название головоломки было сокращено лишь до двух кандзи ({{lang-ja|数独}}) и появилось известное на весь мир обозначение. Судоку является зарегистрированным брендом в Японии<ref>{{Cite web|url=https://www.j-platpat.inpit.go.jp/?uri=/c1801/TR/JPT_5056856/00/ja|title=j-platpat|website=www.j-platpat.inpit.go.jp|access-date=2024-08-10|archive-date=2024-08-10|archive-url=https://web.archive.org/web/20240810191248/https://www.j-platpat.inpit.go.jp/?uri=/c1801/TR/JPT_5056856/00/ja|url-status=live}}</ref>. Также игра известна под названиями ({{lang-ja|ナンバープレース, намба: пурэ:су}}) или в кратком варианте ({{lang-ja|ナンプレ, нампурэ}})<ref name=":0" />. В 1986 году [[Nikoli]] представили свою версию головоломки<ref name=":1" /><ref>{{Cite news|title=Inside Japan’s Puzzle Palace|first=Martin|last=Fackler|url=https://www.nytimes.com/2007/03/21/business/worldbusiness/21sudoku.html|website=The New York Times|id=0362-4331|date=2007-03-21|access-date=2024-08-10|lang=en-US|archive-date=2024-08-10|archive-url=https://web.archive.org/web/20240810193534/https://www.nytimes.com/2007/03/21/business/worldbusiness/21sudoku.html|url-status=live}}</ref>.

Сегодня судоку — обязательный компонент многих газет<ref>{{Cite news|title=G2, home of the discerning Sudoku addict|url=https://www.theguardian.com/theguardian/2005/may/13/features11.g2|website=The Guardian|id=0261-3077|date=2005-05-12|access-date=2024-08-10|lang=en-GB}}</ref>. Среди них много изданий с многомиллионными тиражами: например, немецкая газета ''[[Die Zeit]]''<ref>[http://apollo.zeit.de/sudoku/ Die Zeit] {{Wayback|url=http://apollo.zeit.de/sudoku/ |date=20050912033222 }}{{ref-de}}</ref>, австрийский ''[[Der Standard]]''<ref>[http://derstandard.at/sudoku Der Standard ›Lifestyle›Spielen & Lesen›Spielen›Sudoku] {{Wayback|url=http://derstandard.at/sudoku |date=20050827224535 }}{{ref-de}}</ref> и «[[Асахи Симбун]]» в Японии. На территории России судоку также публикуются во многих газетах, журналах и специализированных сборниках.


== Математическая основа ==
== Математическая основа ==
Строка 26: Строка 35:
{{стиль}}
{{стиль}}


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


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


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


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


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


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


Наиболее сложные судоку можно решать методом исключения («нить Ариадны»), для этого на отдельном листе в клеточку записывается текущее положение дел, выбирается поле, в котором могут стоять только два числа, при подстановке которых определяется как можно большее число пар в других клетках. Выбирается одно из чисел пары и подставляется в черновик. С вероятностью 50 % решение заведёт в тупик — что означает, что выбранное число было неправильным. В таком случае нужно «смотать нить» — вернуться к «развилке» и выбрать и подставить другое число. Если не было допущено ошибок в решении, подставленное число будет единственным верным. Подобный подход подробно описал Cleve Moler, создатель пакета для научных расчётов [[MATLAB]]<ref name="Moler">''Cleve Moler.'' [https://www.mathworks.com/company/newsletters/articles/solving-sudoku-with-matlab.html Solving Sudoku with MATLAB] {{Wayback|url=https://www.mathworks.com/company/newsletters/articles/solving-sudoku-with-matlab.html |date=20170814140350 }}.</ref>.
Наиболее сложные судоку можно решать методом исключения («нить Ариадны»), для этого на отдельном листе в клеточку записывается текущее положение дел, выбирается поле, в котором могут стоять только два числа, при подстановке которых определяется как можно большее число пар в других клетках. Выбирается одно из чисел пары и подставляется в черновик. С вероятностью 50% решение заведёт в тупик — это означает, что выбранное число было неправильным. В таком случае нужно «смотать нить» — вернуться к «развилке», выбрать и подставить другое число. Если не было допущено ошибок в решении, подставленное число будет единственным верным. Подобный подход подробно описал [[Моулер, Клив|Моулер Клив]], создатель пакета для научных расчётов [[MATLAB]]<ref name="Moler">''Cleve Moler.'' [https://www.mathworks.com/company/newsletters/articles/solving-sudoku-with-matlab.html Solving Sudoku with MATLAB] {{Wayback|url=https://www.mathworks.com/company/newsletters/articles/solving-sudoku-with-matlab.html |date=20170814140350 }}.</ref>.


== Разновидности ==
== Разновидности ==
Строка 55: Строка 64:
* Судоку разных размеров. Встречаются судоку размером от 4×4 (такие уменьшенные головоломки называют «шидоку» (Shidoku) от японского shi — четыре<ref name="Moler"/>) до 25×25. Наиболее распространены судоку небольших размеров для детей.
* Судоку разных размеров. Встречаются судоку размером от 4×4 (такие уменьшенные головоломки называют «шидоку» (Shidoku) от японского shi — четыре<ref name="Moler"/>) до 25×25. Наиболее распространены судоку небольших размеров для детей.
* Судоку с дополнительными областями. В этих задачах помимо стандартных областей (вертикалей, горизонталей и блоков) задаются дополнительные области, в которых цифры не могут повторяться. Наиболее распространены диагональные судоку.
* Судоку с дополнительными областями. В этих задачах помимо стандартных областей (вертикалей, горизонталей и блоков) задаются дополнительные области, в которых цифры не могут повторяться. Наиболее распространены диагональные судоку.
* Судоку с дополнительными условиями. В таких задачах помимо стандартного условия неповторяемости цифр задаются ещё дополнительные условия на значения. Например:
* Судоку с дополнительными условиями. В таких задачах, помимо стандартного условия неповторяемости цифр, задаются дополнительные условия на значения. Например:
** Судоку «Суммы» и множество её вариаций («Судоку-Произведения», «Судоку-Арифметика», «Квадросудоку», «Суммы-сбоку», «Суммы по диагонали» и т. п.), где всё поле делится на блоки, для которых сообщается сумма (произведение, разность и т. п.) всех входящих в него цифр.
** Судоку «Суммы» и множество её вариаций («Судоку-Произведения», «Судоку-Арифметика», «Квадросудоку», «Суммы-сбоку», «Суммы по диагонали» и т.п.), где всё поле делится на блоки, для которых сообщается сумма (произведение, разность и т.д.) всех входящих в него цифр.
** Судоку «Чёт-нечёт». В них некоторые клетки изначально выделены цветом, в этих клетках находятся или только чётные, или только нечётные цифры.
** Судоку «Чёт-нечёт». В них некоторые клетки изначально выделены цветом. В этих клетках находятся или только чётные или только нечётные цифры.
** Судоку «Больше-меньше». Для некоторых соседних клеток указан знак, показывающий в какой из клеток цифра больше.
** Судоку «Больше-меньше». Для некоторых соседних клеток указан знак, показывающий в какой из клеток цифра больше.
** Судоку «Точки», где между соседними клетками выводится точка белого или чёрного цвета, когда соседние цифры отличаются на 1 или в два раза.
** Судоку «Точки», где между соседними клетками выводится точка белого или чёрного цвета, когда соседние цифры отличаются на 1 или в два раза.
** Судоку «Перегородки» («Судоку-Соседи»), где отмечены все места с цифрами в соседних клетках отличающихся на 1.
** Судоку «Перегородки» («Судоку-Соседи»), где отмечены все места с цифрами в соседних клетках, отличающихся на 1.
** «Шахматные» судоку, где две или более клеток, которые связаны между собой ходом определённой шахматной фигуры (чаще всего коня), не могут содержать одинаковые цифры. Данное ограничение может налагаться на все возможные цифры или на некоторые из них.
** «Шахматные» судоку, где две или более клеток, которые связаны между собой ходом определённой шахматной фигуры (чаще всего коня), не могут содержать одинаковые цифры. Данное ограничение может налагаться на все возможные цифры или на некоторые из них.
* Судоку другой формы. В головоломке используется не квадратная сетка, а треугольная, шестиугольная или более хитроумной формы.
* Судоку другой формы. В головоломке используется не квадратная сетка, а треугольная, шестиугольная или более хитроумной формы.
Строка 69: Строка 78:


=== Компьютерные игры ===
=== Компьютерные игры ===
Для [[Персональный компьютер|персональных компьютеров]] существует достаточно много вариантов данной игры, например,
Для [[Персональный компьютер|персональных компьютеров]] существует достаточно много вариантов данной игры, например:
* [[GNOME Games#Sudoku|Sudoku]] (из набора игр [[GNOME Games]]) или KSudoku (из набора игр [[KDE Games]]) — для [[Linux]]-платформ,
* ''[[GNOME Games#Sudoku|Sudoku]]'' (из набора игр [[GNOME Games]]) или ''KSudoku'' (из набора игр [[KDE Games]]) — для [[Linux]]-платформ;
* Microsoft Sudoku (доступная для [[Операционная система|ОС]] [[Windows 8.1]] или [[Windows 10]] в [[Windows Store]]) — для [[Windows]]-платформ.
* ''Microsoft Sudoku'' (доступная для [[Операционная система|ОС]] [[Windows 8.1]] или [[Windows 10]] в [[Windows Store]]) — для [[Windows]]-платформ.


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


С появлением [[смартфон]]ов игра заняла достойное место среди самых популярных. С выходом на рынок устройств на базе [[Android]] и [[iOS]], количество поклонников игры резко возросло.
С появлением [[смартфон]]ов игра заняла достойное место среди самых популярных. С выходом на рынок устройств на базе [[Android]] и [[iOS]] количество поклонников игры резко возросло.


== См. также ==
== См. также ==
Строка 92: Строка 101:
* [https://sudokuhit.com/ru/kak-igrat/x-wing/ Техника X-крыла Судоку].
* [https://sudokuhit.com/ru/kak-igrat/x-wing/ Техника X-крыла Судоку].
* [https://dailysudokupuzzles.com/ru/kto-izobrel-sudoku-nashe-rassledovanie/ Кто придумал Судоку]
* [https://dailysudokupuzzles.com/ru/kto-izobrel-sudoku-nashe-rassledovanie/ Кто придумал Судоку]
* [https://sudoku-guru.ru/pravila_sudoku/mech-ryba/ Техника Меч-рыба]


== Литература ==
== Литература ==
Строка 106: Строка 116:
[[Категория:Японские игры]]
[[Категория:Японские игры]]
[[Категория:Изобретения Японии]]
[[Категория:Изобретения Японии]]
[[Категория:NP-полные задачи]]

Текущая версия от 20:33, 20 декабря 2024

Судоку

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

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

Правильно составленная головоломка имеет только одно решение. Тем не менее, на некоторых интернет-сайтах, под видом усложнённых головоломок пользователю предлагаются варианты судоку с несколькими вариантами решения, а также с ветвлениями самого хода решения.

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

В 2012 году финский математик Арто Инкала заявил, что разработал «самую трудную в мире судоку», которая получила название «Эверест». Если самые простые из распространённых вариантов судоку по шкале сложности обозначить, как «1», а наиболее сложные из популярных оценить на «5», то предложенный математиком вариант имеет сложность «11»[2].

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

[править | править код]

В XVIII веке Леонард Эйлер изобрёл игру «Carré latin» («Латинский квадрат»). С конца XIX века многие французские газеты издавали похожую головоломку[3][4].

Изобретателем головоломки в современном виде, вероятно, является 74-летний архитектор Говард Гарнс. Впервые она была опубликована в 1979 году под названием Number Place американской компанией Dell Magazines, которая занималась изданием журналов, книг и комиксов[5][6].

В Японии игра была впервые представлена Маки Кадзи в апреле 1984 года под названием «Sūji wa dokushin ni kagiru» (яп. 数字は独身に限る), что в данном случае переводится как «Цифры должны быть одни». Слово из кандзи (яп. 独身) имеет обозначение «Одинокий человек, не состоящий в отношениях». Позже название головоломки было сокращено лишь до двух кандзи (яп. 数独) и появилось известное на весь мир обозначение. Судоку является зарегистрированным брендом в Японии[7]. Также игра известна под названиями (яп. ナンバープレース, намба: пурэ:су) или в кратком варианте (яп. ナンプレ, нампурэ)[5]. В 1986 году Nikoli представили свою версию головоломки[6][8].

Сегодня судоку — обязательный компонент многих газет[9]. Среди них много изданий с многомиллионными тиражами: например, немецкая газета Die Zeit[10], австрийский Der Standard[11] и «Асахи Симбун» в Японии. На территории России судоку также публикуются во многих газетах, журналах и специализированных сборниках.

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

[править | править код]

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

Количество различных судоку классического размера 9×9 с однозначным решением равно

6 670 903 752 021 073 000 000 (последовательность A107739 в OEIS),

или примерно . Если, однако, считать одинаковыми те судоку, которые получаются друг из друга с помощью поворотов, отражений и перенумерации, то это количество уменьшается до 5 472 730 538 (последовательность A109741 в OEIS[13].

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

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

[править | править код]

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

Сначала смотрят на ряды, столбцы и блоки 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% решение заведёт в тупик — это означает, что выбранное число было неправильным. В таком случае нужно «смотать нить» — вернуться к «развилке», выбрать и подставить другое число. Если не было допущено ошибок в решении, подставленное число будет единственным верным. Подобный подход подробно описал Моулер Клив, создатель пакета для научных расчётов MATLAB[16].

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

[править | править код]

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

  • Нерегулярное судоку (их ещё называют Судоку-пазл, Судоку-фигуры, Области). В этой головоломке вместо стандартных областей 3×3 используются области произвольной формы. Цифры не должны повторяться в каждой такой области.
  • Судоку разных размеров. Встречаются судоку размером от 4×4 (такие уменьшенные головоломки называют «шидоку» (Shidoku) от японского shi — четыре[16]) до 25×25. Наиболее распространены судоку небольших размеров для детей.
  • Судоку с дополнительными областями. В этих задачах помимо стандартных областей (вертикалей, горизонталей и блоков) задаются дополнительные области, в которых цифры не могут повторяться. Наиболее распространены диагональные судоку.
  • Судоку с дополнительными условиями. В таких задачах, помимо стандартного условия неповторяемости цифр, задаются дополнительные условия на значения. Например:
    • Судоку «Суммы» и множество её вариаций («Судоку-Произведения», «Судоку-Арифметика», «Квадросудоку», «Суммы-сбоку», «Суммы по диагонали» и т.п.), где всё поле делится на блоки, для которых сообщается сумма (произведение, разность и т.д.) всех входящих в него цифр.
    • Судоку «Чёт-нечёт». В них некоторые клетки изначально выделены цветом. В этих клетках находятся или только чётные или только нечётные цифры.
    • Судоку «Больше-меньше». Для некоторых соседних клеток указан знак, показывающий в какой из клеток цифра больше.
    • Судоку «Точки», где между соседними клетками выводится точка белого или чёрного цвета, когда соседние цифры отличаются на 1 или в два раза.
    • Судоку «Перегородки» («Судоку-Соседи»), где отмечены все места с цифрами в соседних клетках, отличающихся на 1.
    • «Шахматные» судоку, где две или более клеток, которые связаны между собой ходом определённой шахматной фигуры (чаще всего коня), не могут содержать одинаковые цифры. Данное ограничение может налагаться на все возможные цифры или на некоторые из них.
  • Судоку другой формы. В головоломке используется не квадратная сетка, а треугольная, шестиугольная или более хитроумной формы.
  • Сцепленные судоку. «Судоку-Самурай» («Судоку-Комбо», «Судоку-Конструкции», «Тудоку» и др.), в которых несколько отдельных судоку имеют общие блоки и решаются взаимозависимо.

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

[править | править код]

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

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

[править | править код]

Для персональных компьютеров существует достаточно много вариантов данной игры, например:

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

[править | править код]

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

С появлением смартфонов игра заняла достойное место среди самых популярных. С выходом на рынок устройств на базе Android и iOS количество поклонников игры резко возросло.

Примечания

[править | править код]
  1. Грамота.ру — Судоку. Дата обращения: 13 сентября 2024. Архивировано 13 сентября 2024 года.
  2. Mathematician Arto Inkala creates world’s hardest Sudoku, ‘Everest’ (англ.). Дата обращения: 23 сентября 2024.
  3. MULTIMAGIE.COM - Sudoku's French ancestors. web.archive.org (10 октября 2007). Дата обращения: 10 августа 2024. Архивировано из оригинала 10 октября 2007 года.
  4. [http://cboyer.club.fr/multimagie/SupplAncetresSudoku.pdf Supplément de l’article « Les ancêtres français du sudoku »]. Архивировано 10 декабря 2006 года.
  5. 1 2 Math Games:Sudoku Variations. www.mathpuzzle.com. Дата обращения: 10 августа 2024. Архивировано 27 июля 2024 года.
  6. 1 2 Smith, David (2005-05-15). "So you thought Sudoku came from the Land of the Rising Sun ..." The Observer (англ.). 0029-7712. Архивировано 29 августа 2013. Дата обращения: 10 августа 2024.
  7. j-platpat. www.j-platpat.inpit.go.jp. Дата обращения: 10 августа 2024. Архивировано 10 августа 2024 года.
  8. Fackler, Martin (2007-03-21). "Inside Japan's Puzzle Palace". The New York Times (англ.). 0362-4331. Архивировано 10 августа 2024. Дата обращения: 10 августа 2024.
  9. "G2, home of the discerning Sudoku addict". The Guardian (англ.). 2005-05-12. 0261-3077. Дата обращения: 10 августа 2024.
  10. Die Zeit Архивная копия от 12 сентября 2005 на Wayback Machine (нем.)
  11. Der Standard ›Lifestyle›Spielen & Lesen›Spielen›Sudoku Архивная копия от 27 августа 2005 на Wayback Machine (нем.)
  12. T. Yato, T. Seta. Complexity and Completeness of Finding Another Solution and Its Application to Puzzles Архивная копия от 21 июля 2011 на Wayback Machine (англ.).
  13. Jarvis, Frazer; Russell, Ed.: There are 5472730538 essentially different Sudoku grids ... and the Sudoku symmetry group. Frazer Jarvis's home page (7 сентября 2005). Дата обращения: 16 сентября 2006. Архивировано 4 октября 2006 года.
  14. Sudoku@vtaiwan — Проект распределённых вычислений по исследованию судоку Архивировано 19 августа 2013 года.
  15. Математики решили задачу о подсказках в судоку. Дата обращения: 9 января 2012. Архивировано 12 января 2012 года.
  16. 1 2 Cleve Moler. Solving Sudoku with MATLAB Архивная копия от 14 августа 2017 на Wayback Machine.
  17. Судоку — тренировка для ума Архивная копия от 14 июня 2007 на Wayback Machine  (недоступная ссылка с 13-05-2013 [4242 дня] — история).

Литература

[править | править код]