Судоку - весьма интересная головоломка. Необходимо расставить цифры от 1 до 9 в поле таким образом, чтобы каждая строка, столбец и блок 3 х 3 клетки содержали все цифры, и при этом они не должны повторяться. Рассмотрим пошаговую инструкцию, как играть в судоку, основные методы и стратегию решения.
Алгоритм решения: от простого к сложному
Алгоритм решения игры разума судоку довольно прост: необходимо повторять следующие шаги до полного решения задачи. Постепенно переходите от самых простых шагов к более сложным, когда первые уже не позволяют открыть ячейку или исключить кандидата.
Одиночные кандидаты
Прежде всего, для более наглядного объяснения того, как играть в судоку, введем систему нумерации блоков и ячеек поля. Как ячейки, так и блоки нумеруются сверху вниз и слева направо.
Начнем рассматривать наше поле. Для начала необходимо отыскать одиночных кандидатов на место в ячейке. Они могут быть скрытыми или явными. Рассмотрим возможных кандидатов шестого блока: мы видим, что лишь в одной из пяти свободных ячеек присутствует уникальная цифра, следовательно, четверку можно смело вписывать в четвертую ячейку. Рассматривая этот блок дальше, можно сделать вывод: во второй ячейке должна быть цифра 8, так как после исключения четверки восьмерка в блоке больше нигде не встречается. С таким же обоснованием ставим цифру 5.
Внимательно просматривайте все возможные варианты. Взглянув на центральную ячейку пятого блока, обнаружим, что кроме цифры 9 там не может быть больше никаких вариантов - это явный одиночный кандидат для данной клетки. Девятку можно вычеркнуть из остальных ячеек этого блока, после чего с легкостью проставляются остальные цифры. По такому же методу проходим по ячейкам других блоков.
Как обнаружить скрытые и явные «голые пары»
Проставив необходимые цифры в четвертом блоке, вернемся к незаполненным ячейкам шестого блока: очевидно, что цифра 6 должна находиться в третьей клетке, а 9 - в девятой.
Понятие «голая пара» присутствует только в игре судоку. Правила их обнаружения следующие: если в двух ячейках одного блока, строки или столбца присутствует идентичная пара кандидатов (и только эта пара!), то остальные ячейки группы их иметь не могут. Объясним это на примере восьмого блока. Проставив в каждую клетку возможных кандидатов, обнаруживаем явную «голую пару». Цифры 1 и 3 присутствуют во второй и пятой ячейках этого блока, и там и там присутствует всего лишь по 2 кандидата, следовательно, из остальных ячеек их можно смело исключать.
Завершение разгадывания головоломки
Если вы усвоили урок того, как играть в судоку, и шаг за шагом выполняли вышеперечисленные указания, то у вас должна получиться примерно такая картина, как на этом поле:
Здесь можно обнаружить одиночных кандидатов: единица в седьмой ячейке девятого блока и двойка в четвертой ячейке третьего блока. Попробуйте решить головоломку до конца. Теперь сравните полученный результат с правильным решением.
Получилось? Поздравляем, ведь это значит, что вы успешно усвоили уроки того, как играть в судоку, и научились разгадывать простейшие головоломки. Существует немало разновидностей этой игры: судоку разных размеров, судоку с дополнительными областями и дополнительными условиями. Игровое поле может варьироваться от 4 х 4 до 25 х 25 клеток. Вы можете встретить головоломку, в которой цифры не могут повторяться и в дополнительной области, например, по диагонали.
Начинайте с простых вариантов и постепенно переходите к более сложным, ведь с тренировками приходит и опыт.
Правила
Игровое поле представляет собой квадрат размером 9×9, разделённый на меньшие квадраты со стороной в 3 клетки. Таким образом, всё игровое поле состоит из 81 клетки. В них уже в начале игры стоят некоторые числа (от 1 до 9), называемые подсказками . От игрока требуется заполнить свободные клетки цифрами от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3×3 каждая цифра встречалась бы только один раз.
Сложность судоку зависит не от количества изначально заполненных клеток, а от методов, которые нужно применять для её решения. Самые простые решаются дедуктивно: всегда есть хотя бы одна клетка, куда подходит только одно число. Некоторые головоломки можно решить за несколько минут, на другие можно потратить часы.
Правильно составленная головоломка имеет только одно решение. Тем не менее, на некоторых сайтах в интернете под видом усложнённых головоломок пользователю предлагаются варианты судоку с несколькими вариантами решения, а также с ветвлениями самого хода решения.
Происхождение
Математическая основа
Долгое время оставался открытым вопрос о минимальном количестве подсказок, необходимых для однозначного решения судоку. В частности, не было известно, существует ли однозначно решаемая судоку с 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 .
Разновидности
Существует множество вариаций судоку:
Настольная игра судоку
Существуют также настольные варианты игры. Подобные игры были изданы по всему миру различными издателями и разработчиками (к примеру, известный разработчик настольных игр Reiner Knizia издал свой вариант этой логической игры). В России можно встретить настольные судоку от фирмы Астрель и польской компании Trefi .
Компьютерные игры
- KSudoku - из набора игр KDE Games .
Версии для мобильных телефонов
Существуют несколько версий игры для мобильных телефонов, а также для смартфонов. Эти версии удобны тем, что могут сами создавать условие головоломки. Также они указывают на ошибки (противоречащие цифры подсвечиваются) или могут дать подсказку в решении. 9 цифр в стандартных судоку, назначенные на 9 цифровых кнопок на мобильном телефоне, делают процесс игры очень удобным.
Соревнования по решению судоку
Во многих странах проводятся различные турниры и соревнования по решению судоку. Чемпионаты мира по решению судоку проводит Международная федерация пазлспорта , с 2007 года в них определяется и команда-победительница.
| Год | Место проведения | Чемпион | 2-й призёр | 3-й призёр | Команда-победительница |
|---|---|---|---|---|---|
| 2006 | Лукка | Jana Tylova (Чехия) | Thomas Snyder (США) | Wei-Hwa Huang (США) | |
| 2007 | Прага | Thomas Snyder (США) | Yuhei Kusui (Япония) | Peter Hudak (Словакия) | |
| 2008 | Гоа | Thomas Snyder (США) | Yuhei Kusui (Япония) | Jakub Ondrousek (Чехия) | |
| 2009 | Жилина | Jan Mrozowski (Польша) | Branko Ceranic (Сербия) | Robert Babilon (Чехия) | |
| 2010 | Филадельфия | Jan Mrozowski (Польша) | Jakub Ondrousek (Чехия) | Hideaki Jo (Япония) | |
| 2011 | Эгер | Thomas Snyder (США) | Kota Morinishi (Япония) | Tiit Vunk (Эстония) |
С 2006 года проводятся и чемпионаты России по решению судоку, организацией которых занимается клуб любителей головоломок «Диоген» .
См. также
Примечания
Ссылки
- Более полное объяснение решения судоку (включая сложные методы) .
Литература
- Эндрю Херон, Эдмунд Джеймс. Судоку для «чайников» = Su Doku for Dummies (Sudoku). - М .: «Диалектика», 2007. - С. 336. - ISBN 978-0-470-01892-7
- К. Кноп. Магический квадрат или Числа на плацу // Компьютерра . - В. 09.09.2000.
Итак, сегодня я научу вас решать судоку .
Для наглядности возьмем конкретный пример и рассмотрим основные правила:
Правила решения судоку:
Желтым я выделил строку и столбец. Первое правило в каждой строке и каждом столбце могут быть цифры от 1 до 9, причем они не могут повторяться. Короче говоря – 9 клеток, 9 цифр – поэтому в 1-м и том же столбце не может быть 2-х пятерок, восьмерок и т.д. Аналогично для строк.
Теперь я выделил квадраты – это второе правило . В каждом квадрате могут быть цифры от 1-го до 9 причем они не повторяются. (Так же как и в строках и столбцах). Квадраты выделены жирными линиями.
Отсюда имеем общее правило для решения судоку : ни в строках , ни в столбцах ни в квадратах цифры не должны повторяться.
Ну что ж, давайте теперь попробуем его решить:
Я выделил единицы зеленым и показал направление, куда мы смотрим. А именно – нас интересует последний верхний квадрат. Можно заметить, что во 2-м и 3-м ряду этого квадрата не могут быть единицы иначе будет повторение. Значит – единица вверху:
Легко находится и двойка:
Теперь воспользуемся найденной только что двойкой:
Надеюсь, алгоритм поиска стал понятен, поэтому с этого момента буду рисовать быстрее.
Смотрим на 1-й квадрат 3-й строки (внизу):
Т.к. у нас там осталось 2 свободных клетки, то в каждой из них может быть одна из двух цифр: (1 или 6):
Это значит, что в столбце, который я выделил не может больше быть ни 1 ни 6 – значит в верхним квадрате ставим 6.
За неимением времени на этом и остановлюсь. Очень надеюсь, что логику вы уловили. Кстати, я взял не самый простой пример, в котором скорее всего не будут сразу видны все решения однозначно, а поэтому лучше пользоваться карандашом. Мы пока не знаем насчет 1 и 6 в нижнем квадрате, поэтому их рисуем карандашом – аналогично в верхнем квадрате будут карандашом нарисованы 3 и 4.
Если ещё немного порассуждать, используя правила - избавимся от вопроса где 3, а где 4:
Да, кстати, если вам какой-то момент показался непонятным – напишите, я поясню подробнее. Удачи с разгадыванием судоку.
В этой статье разберём подробно каким образом решать сложные судоку на примере диагонального судоку.
Нам выпадает условие номер 437, которое показано на рисунке 1. И сразу бросается в глаза первый квадрат, он самый насыщенный на открытые цифры. Не хватает цифр 1, 3,4,9. Но так как горизонталь а тройку уже содержит, то цифра три ставится на с1. Остальные мы точно поставить не можем. Потому рассмотрим что у нас ещё есть. К примеру вертикаль 4 и здесь цифра четыре может стоять только на b4, из за наличия четвёрки в пятом квадрате и на горизонталь с. Остальные цифры мы пока ставить не будем.
Все приёмы и методы, которые мы будем применять далее относятся как к решению простых, так и сложных судоку.
А что у нас на горизонтали b? Тут не хватает тройки и стоять она может только на b8. (Во втором квадрате она уже есть и на вертикали 9). И если внимательно рассмотреть дальше горизонталь b, то мы обнаружим, что у нас есть скрытая одиночка - цифра 9 на клетке b9. Потому как остальные кандидаты (это 1 и 5) на этой клетке стоять не могут!
Что мы можем дальше сделать? Если рассмотреть квадрат пять. Тут цифры 3 и 5 могут быть либо на d5 либо на e6. Значит для остальных цифр эти клетки не рассматриваем.Исходя из этого для единички остаётся только одно место - клетка d6.
Результат наших действий на рисунке 2. Благодаря проведённому нами анализу ряд b проставляется полностью. Единица на b5, пятёрка на b6. Что даёт нам право расставить 3 и 5 в пятом квадрате!
Продолжим анализ пятого квадрата. В нём не хватает цифры 7, её же нет на главных диагоналях, а что самое интересное на вертикали 4. Благодаря этой самой вертикали мы можем точно сказать что цифра семь в пятом квадрате может стоять либо на f4 или e4. Так как горизонтали с и d семёрку уже содержат. А на е5 она не может стоять из за вертикали 4. Дальше обратимся к главным горизонталям. И тут семёрки сразу расставляются! На i9 и на f4.
Что у нас получилось можно увидеть на рисунке 3. Дальше продожим анализ главных диагоналей. Если рассмотреть идущую с клетки а1, то в ней не хватает двойки, которая ставится только на h8. Ещё в этой диагонали не хватает 1, 8 и 9 . Единичка может стоять только на а1, ставим быстренько её! А восьмёрка на d4 стоять не может, так как она есть на горизонтали d уже. Расставляем - d4 -9, e5 -8.
А вот теперь мы можем полностью заполнить пятый и первый квадраты! Что у нас получилось смотрим на рисунке 4.
Обратите внимание на вертикаль 3. Тут нужно расставить 1, 6, 7. Единица ставится только на f3, а исходя из этого расставляются остальные - e3 -7, h3-6. Дальше на очереди у нас вертикаль 9, так как она расставляется просто сказочно. d9-2, g9-6, h9-8.
А что если нам проверить на открытые одиночки?! К примеру, цифра три смело ставится на клетки d2 и h5. Хотя дальнейший анализ одиночек ничего не даёт. Тогда обратимся к оставшейся диагонали. У ннеё не хватает 6, 2, 4. Цифра шесть может быть только на c7. Остальное уже просто заполнить.
А почему у нас вертикаль 4 не проставлена до конца? Исправляем. с4 -8.
Результат наших изысканий на рисунке5. А теперь заполним горизонталь с. с8-1, с5-9, с6-2. И это всё исходя из наличия этих цифр в других вертикалях. Основываясь на горизонтали с легко заполнить горизонталь d. d1-6, d7 -4. Дальше совсем просто заполняется третий квадрат. А вот второй квадрат пока не заполнится, хотя так же только два кандидата - шестёрка и семёрка. Но по вертикалям пять и шесть они не встречаются и потому пока отложим их.
Проанализировав все вертикали и горизонтали мы приходим к выводу, что однозначно поставить нельзя ни одной цифры. Потому переходим к рассмотрению квадратов. Обратимся к шестому квадрату. Тут не хватает 5,6,8,9. Но цифры 6 и 8 мы точно можем поставить на клетки f7 и f8. Благодаря нашему анализу горизонталь f проставляется вся! f1 -9, f2 -5. И что мы тут видим - четвёртый квадрат заполняется весь! е1- 4, е2 -2.
Что у нас получилось можно посмотреть на рисунке 6. Теперь обратимся к квадрату девять. Здесь у нас появляется одна открытая одиночка - цифра один на i7. Благодаря чему мы можем поставить единичку в седьмом квадрате на g2. Восьмёрка на i2.
Которые помогут вам в развитии одного из важнейших органов — мозга. Разумеется, широко-известные японские головоломки судоку являются одними из них. С их помощью вы сможете изрядно “накачать извилины”, ведь помимо необходимости просчитывать огромное количество вариантов расположения чисел, вам также нужно уметь делать это на пару десятков ходов вперед. Одним словом, это настоящий рай, если вы хотите не дать своим нейронам “засохнуть”. И сегодня мы рассмотрим основные приемы, которые используют знатоки судоку. Это будет полезно как новичкам, так и давним фанатам этих головоломок. Ведь кому-то нужно сделать свои первые шаги в искусстве судоку, а кому-то повысить эффективность своих решений!
Правила
Если вы еще не знакомы с , то для начала вам стоит ознакомиться с правилами. Поверьте, они очень просты.
Игровое поле — это квадрат, который имеет размеры 9×9. При этом он разделен на меньшие квадраты с размерами 3×3. То есть, все поле состоит из 81 клетки.
Условие задачи — это те числа, которые уже расставлены в этих клетках.
Блок (блок ячеек) — малый квадрат, строка или строчка.
Что необходимо сделать: расставить все остальные цифры, соблюдая несколько правил. Во-первых, в каждом из маленьких квадратов не должно быть повторений. Во-вторых, во всех столбцах и строках также не должно быть повторений. То есть, каждое число должно встречаться лишь один раз в каждом из этих блоков. Для того, чтобы все стало еще понятнее, обратите внимание на решенный судоку:
Базовый способ решения
Как правило, если вы будете решать простые судоку, то все, что вам необходимо сделать — это расписать все возможные варианты для каждой из 81 клетки и постепенно вычеркивать неподходящие варианты. Это очень просто.
Но если вы перейдете на уровень выше, к более сложным судоку, то все становится интереснее. Часто будет так, что поставить новые цифры нет никакой возможности, и вам придется идти через предположения: “Пусть здесь стоит такое число”, после чего вам необходимо будет рассмотреть эту гипотезу и либо прийти к решению задачи, либо к противоречию своего предположения.
Но конечно, есть особые приемы, которые помогут делать все это более эффективно.
Приемы
1. Голые пары/тройки/четверки
Если у вас имеется две клетки в одном блоке (квадрат, строка или столбец), в которые можно поставить лишь 2 цифры, то очевидно, что эти цифры можно убрать из возможных вариантов для других клеток данного блока.
Более такого, такой трюк можно легко проделать и с тройками, и с четверками:
2. Скрытые пары
Очень полезный прием, в некотором роде, обратный голым парам. Если в каких-то двух клетках одного квадрата в “возможных вариантах” у вас есть цифры, которые больше нигде не повторяются (в рамках этого квадрата), то все остальные цифры из этих двух клеток можно убрать.
Для того, чтобы стало еще понятнее, обратите внимание на примеры (один простой и посложнее):
К счастью, это работает и для троек, и для четверок, но стоит упомянуть очень важную и очень крутую фишку. Не обязательно, чтобы в трех/четырех ячейках были одинаковые 3 цифры вида (a;b;c) (a;b;c) (a;b;c). Вам будет достаточно такого варианта: (a;b) (b;c) (a;c).
3. Безымянное правило
Если у вас есть пара или тройка в одном столбце/строке, которые при этом располагаются в одном квадрате, можете смело убрать эти цифры из других ячеек данного квадрата.
4. Указывающие пары
Если в одной строке/столбце в “возможных вариантах” есть две одинаковые цифры, то такие цифры можно убрать из соответствующего столбца/строки.
Временами это бывает очень полезно, особенно, если вы найдете несколько таких пар:
Конечно, при этом данные цифры должны отсутствовать в других ячейках квадрата, но согласно безымянному правилу, это не требуется.
Любите судоку и другие загадки, игры, головоломки и тесты, направленные на развитие различные аспектов мышления? Получите ко всем интерактивным материалам на сайте, чтобы развиваться эффективнее.
Заключение
Мы рассмотрели основные приемы, которые используются при решении судоку. Отмечу, что это лишь начало и в следующих статьях мы рассмотрим более сложные и более интересные фишки, благодаря которым решение таких задач станет еще интереснее и проще.
В качестве тренировки редакция 4brain предлагает вам ознакомиться с файлом , в котором содержатся судоку различного уровня сложности. Не пожалейте времени на тренировки, поскольку если вы уделите этому занятию достаточно времени, то в конце данного курса статей, поверьте мне, вы станете настоящим асом в решении японских головоломок.
Если у вас есть какие-то вопросы по данным методикам или же по судоку, которые мы прикладываем к статье, можете смело задавать их в комментариях!
