Судоку

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

Правила

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

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

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

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

В XVIII веке Леонард Эйлер изобрёл игру «Carré latin» (Латинский квадрат»). На основе этой игры в 70-х годах прошлого века в Северной Америке были придуманы специальные числовые кроссворды. Так, в США судоку появилась впервые в 1979 году в журнале «Dell Puzzle Magazine». Тогда она называлась «Number Place». Настоящую популярность судоку завоевала в 1980—1990-х годах, когда японский журнал «Nikoli» начал регулярно публиковать на своих страницах эту головоломку (с 1986 года). Сегодня судоку — обязательный компонент многих газет. Среди них много изданий с многомиллионными тиражами, например, немецкая газета «Die Zeit», австрийский «Der Standard». Также публикует судоку российская газета «Труд».

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

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

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

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

К:Википедия:Статьи без источников (тип: не указан)

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

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

Интересный подход к решению судоку использовал Cleve Moler, создатель пакета для научных расчётов MATLAB.

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

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

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

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

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

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

• Sudoku — из набора игр GNOME Games.
• KSudoku — из набора игр KDE Games.

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

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

См. также

• Какуро
• Кроссворд
• Японский кроссворд
• Латинский квадрат
• Четыре четверки

Ссылки

• [7xsudoku.ru/t1 Правила игры судоку и её разновидностей].
• [www.sudoku-club.ru/howto.html Как решать судоку].
• [biblprog.org.ua/pages_ru/pages_statti_ru/sudoku/step1.html Более полное объяснение решения судоку (включая сложные методы)].

Литература

• Эндрю Херон, Эдмунд Джеймс. Судоку для «чайников» = Su Doku for Dummies (Sudoku). — М.: «Диалектика», 2007. — С. 336. — ISBN 978-0-470-01892-7.
• К. Кноп. [www.arbuz.uz/knopki/kvadrat.htm Магический квадрат или Числа на плацу] // Компьютерра. — Вып. 09.09.2000.
• И. Г. Сухин. Судоку и суперсудоку на шестнадцати клетках для детей. — М.: АСТ, Астрель, 2006. — 128 с. — ISBN 5-17-036566-7.

Отрывок, характеризующий Судоку

– Ну, что ж это, господа, – сказал штаб офицер тоном упрека, как человек, уже несколько раз повторявший одно и то же. – Ведь нельзя же отлучаться так. Князь приказал, чтобы никого не было. Ну, вот вы, г. штабс капитан, – обратился он к маленькому, грязному, худому артиллерийскому офицеру, который без сапог (он отдал их сушить маркитанту), в одних чулках, встал перед вошедшими, улыбаясь не совсем естественно.
– Ну, как вам, капитан Тушин, не стыдно? – продолжал штаб офицер, – вам бы, кажется, как артиллеристу надо пример показывать, а вы без сапог. Забьют тревогу, а вы без сапог очень хороши будете. (Штаб офицер улыбнулся.) Извольте отправляться к своим местам, господа, все, все, – прибавил он начальнически.
Князь Андрей невольно улыбнулся, взглянув на штабс капитана Тушина. Молча и улыбаясь, Тушин, переступая с босой ноги на ногу, вопросительно глядел большими, умными и добрыми глазами то на князя Андрея, то на штаб офицера.
– Солдаты говорят: разумшись ловчее, – сказал капитан Тушин, улыбаясь и робея, видимо, желая из своего неловкого положения перейти в шутливый тон.
Но еще он не договорил, как почувствовал, что шутка его не принята и не вышла. Он смутился.
– Извольте отправляться, – сказал штаб офицер, стараясь удержать серьезность.
Князь Андрей еще раз взглянул на фигурку артиллериста. В ней было что то особенное, совершенно не военное, несколько комическое, но чрезвычайно привлекательное.
Штаб офицер и князь Андрей сели на лошадей и поехали дальше.
Выехав за деревню, беспрестанно обгоняя и встречая идущих солдат, офицеров разных команд, они увидали налево краснеющие свежею, вновь вскопанною глиною строящиеся укрепления. Несколько баталионов солдат в одних рубахах, несмотря на холодный ветер, как белые муравьи, копошились на этих укреплениях; из за вала невидимо кем беспрестанно выкидывались лопаты красной глины. Они подъехали к укреплению, осмотрели его и поехали дальше. За самым укреплением наткнулись они на несколько десятков солдат, беспрестанно переменяющихся, сбегающих с укрепления. Они должны были зажать нос и тронуть лошадей рысью, чтобы выехать из этой отравленной атмосферы.
– Voila l'agrement des camps, monsieur le prince, [Вот удовольствие лагеря, князь,] – сказал дежурный штаб офицер.
Они выехали на противоположную гору. С этой горы уже видны были французы. Князь Андрей остановился и начал рассматривать.
– Вот тут наша батарея стоит, – сказал штаб офицер, указывая на самый высокий пункт, – того самого чудака, что без сапог сидел; оттуда всё видно: поедемте, князь.
– Покорно благодарю, я теперь один проеду, – сказал князь Андрей, желая избавиться от штаб офицера, – не беспокойтесь, пожалуйста.
Штаб офицер отстал, и князь Андрей поехал один.
Чем далее подвигался он вперед, ближе к неприятелю, тем порядочнее и веселее становился вид войск. Самый сильный беспорядок и уныние были в том обозе перед Цнаймом, который объезжал утром князь Андрей и который был в десяти верстах от французов. В Грунте тоже чувствовалась некоторая тревога и страх чего то. Но чем ближе подъезжал князь Андрей к цепи французов, тем самоувереннее становился вид наших войск. Выстроенные в ряд, стояли в шинелях солдаты, и фельдфебель и ротный рассчитывали людей, тыкая пальцем в грудь крайнему по отделению солдату и приказывая ему поднимать руку; рассыпанные по всему пространству, солдаты тащили дрова и хворост и строили балаганчики, весело смеясь и переговариваясь; у костров сидели одетые и голые, суша рубахи, подвертки или починивая сапоги и шинели, толпились около котлов и кашеваров. В одной роте обед был готов, и солдаты с жадными лицами смотрели на дымившиеся котлы и ждали пробы, которую в деревянной чашке подносил каптенармус офицеру, сидевшему на бревне против своего балагана. В другой, более счастливой роте, так как не у всех была водка, солдаты, толпясь, стояли около рябого широкоплечего фельдфебеля, который, нагибая бочонок, лил в подставляемые поочередно крышки манерок. Солдаты с набожными лицами подносили ко рту манерки, опрокидывали их и, полоща рот и утираясь рукавами шинелей, с повеселевшими лицами отходили от фельдфебеля. Все лица были такие спокойные, как будто всё происходило не в виду неприятеля, перед делом, где должна была остаться на месте, по крайней мере, половина отряда, а как будто где нибудь на родине в ожидании спокойной стоянки. Проехав егерский полк, в рядах киевских гренадеров, молодцоватых людей, занятых теми же мирными делами, князь Андрей недалеко от высокого, отличавшегося от других балагана полкового командира, наехал на фронт взвода гренадер, перед которыми лежал обнаженный человек. Двое солдат держали его, а двое взмахивали гибкие прутья и мерно ударяли по обнаженной спине. Наказываемый неестественно кричал. Толстый майор ходил перед фронтом и, не переставая и не обращая внимания на крик, говорил:
– Солдату позорно красть, солдат должен быть честен, благороден и храбр; а коли у своего брата украл, так в нем чести нет; это мерзавец. Еще, еще!
И всё слышались гибкие удары и отчаянный, но притворный крик.
– Еще, еще, – приговаривал майор.
Молодой офицер, с выражением недоумения и страдания в лице, отошел от наказываемого, оглядываясь вопросительно на проезжавшего адъютанта.
Князь Андрей, выехав в переднюю линию, поехал по фронту. Цепь наша и неприятельская стояли на левом и на правом фланге далеко друг от друга, но в средине, в том месте, где утром проезжали парламентеры, цепи сошлись так близко, что могли видеть лица друг друга и переговариваться между собой. Кроме солдат, занимавших цепь в этом месте, с той и с другой стороны стояло много любопытных, которые, посмеиваясь, разглядывали странных и чуждых для них неприятелей.
С раннего утра, несмотря на запрещение подходить к цепи, начальники не могли отбиться от любопытных. Солдаты, стоявшие в цепи, как люди, показывающие что нибудь редкое, уж не смотрели на французов, а делали свои наблюдения над приходящими и, скучая, дожидались смены. Князь Андрей остановился рассматривать французов.
– Глянь ка, глянь, – говорил один солдат товарищу, указывая на русского мушкатера солдата, который с офицером подошел к цепи и что то часто и горячо говорил с французским гренадером. – Вишь, лопочет как ловко! Аж хранцуз то за ним не поспевает. Ну ка ты, Сидоров!
– Погоди, послушай. Ишь, ловко! – отвечал Сидоров, считавшийся мастером говорить по французски.
Солдат, на которого указывали смеявшиеся, был Долохов. Князь Андрей узнал его и прислушался к его разговору. Долохов, вместе с своим ротным, пришел в цепь с левого фланга, на котором стоял их полк.
– Ну, еще, еще! – подстрекал ротный командир, нагибаясь вперед и стараясь не проронить ни одного непонятного для него слова. – Пожалуйста, почаще. Что он?
Долохов не отвечал ротному; он был вовлечен в горячий спор с французским гренадером. Они говорили, как и должно было быть, о кампании. Француз доказывал, смешивая австрийцев с русскими, что русские сдались и бежали от самого Ульма; Долохов доказывал, что русские не сдавались, а били французов.
– Здесь велят прогнать вас и прогоним, – говорил Долохов.
– Только старайтесь, чтобы вас не забрали со всеми вашими казаками, – сказал гренадер француз.
Зрители и слушатели французы засмеялись.
– Вас заставят плясать, как при Суворове вы плясали (on vous fera danser [вас заставят плясать]), – сказал Долохов.
– Qu'est ce qu'il chante? [Что он там поет?] – сказал один француз.
– De l'histoire ancienne, [Древняя история,] – сказал другой, догадавшись, что дело шло о прежних войнах. – L'Empereur va lui faire voir a votre Souvara, comme aux autres… [Император покажет вашему Сувара, как и другим…]
– Бонапарте… – начал было Долохов, но француз перебил его.
– Нет Бонапарте. Есть император! Sacre nom… [Чорт возьми…] – сердито крикнул он.
– Чорт его дери вашего императора!
И Долохов по русски, грубо, по солдатски обругался и, вскинув ружье, отошел прочь.
– Пойдемте, Иван Лукич, – сказал он ротному.
– Вот так по хранцузски, – заговорили солдаты в цепи. – Ну ка ты, Сидоров!
Сидоров подмигнул и, обращаясь к французам, начал часто, часто лепетать непонятные слова:
– Кари, мала, тафа, сафи, мутер, каска, – лопотал он, стараясь придавать выразительные интонации своему голосу.
– Го, го, го! ха ха, ха, ха! Ух! Ух! – раздался между солдатами грохот такого здорового и веселого хохота, невольно через цепь сообщившегося и французам, что после этого нужно было, казалось, разрядить ружья, взорвать заряды и разойтись поскорее всем по домам.
Но ружья остались заряжены, бойницы в домах и укреплениях так же грозно смотрели вперед и так же, как прежде, остались друг против друга обращенные, снятые с передков пушки.


Объехав всю линию войск от правого до левого фланга, князь Андрей поднялся на ту батарею, с которой, по словам штаб офицера, всё поле было видно. Здесь он слез с лошади и остановился у крайнего из четырех снятых с передков орудий. Впереди орудий ходил часовой артиллерист, вытянувшийся было перед офицером, но по сделанному ему знаку возобновивший свое равномерное, скучливое хождение. Сзади орудий стояли передки, еще сзади коновязь и костры артиллеристов. Налево, недалеко от крайнего орудия, был новый плетеный шалашик, из которого слышались оживленные офицерские голоса.
Действительно, с батареи открывался вид почти всего расположения русских войск и большей части неприятеля. Прямо против батареи, на горизонте противоположного бугра, виднелась деревня Шенграбен; левее и правее можно было различить в трех местах, среди дыма их костров, массы французских войск, которых, очевидно, большая часть находилась в самой деревне и за горою. Левее деревни, в дыму, казалось что то похожее на батарею, но простым глазом нельзя было рассмотреть хорошенько. Правый фланг наш располагался на довольно крутом возвышении, которое господствовало над позицией французов. По нем расположена была наша пехота, и на самом краю видны были драгуны. В центре, где и находилась та батарея Тушина, с которой рассматривал позицию князь Андрей, был самый отлогий и прямой спуск и подъем к ручью, отделявшему нас от Шенграбена. Налево войска наши примыкали к лесу, где дымились костры нашей, рубившей дрова, пехоты. Линия французов была шире нашей, и ясно было, что французы легко могли обойти нас с обеих сторон. Сзади нашей позиции был крутой и глубокий овраг, по которому трудно было отступать артиллерии и коннице. Князь Андрей, облокотясь на пушку и достав бумажник, начертил для себя план расположения войск. В двух местах он карандашом поставил заметки, намереваясь сообщить их Багратиону. Он предполагал, во первых, сосредоточить всю артиллерию в центре и, во вторых, кавалерию перевести назад, на ту сторону оврага. Князь Андрей, постоянно находясь при главнокомандующем, следя за движениями масс и общими распоряжениями и постоянно занимаясь историческими описаниями сражений, и в этом предстоящем деле невольно соображал будущий ход военных действий только в общих чертах. Ему представлялись лишь следующего рода крупные случайности: «Ежели неприятель поведет атаку на правый фланг, – говорил он сам себе, – Киевский гренадерский и Подольский егерский должны будут удерживать свою позицию до тех пор, пока резервы центра не подойдут к ним. В этом случае драгуны могут ударить во фланг и опрокинуть их. В случае же атаки на центр, мы выставляем на этом возвышении центральную батарею и под ее прикрытием стягиваем левый фланг и отступаем до оврага эшелонами», рассуждал он сам с собою…