СУДОКУ - это популярная игра - пазл, которая представляет собой головоломку с цифрами, одолеть которую можно только строя логические умозаключения. В названии Судоку в переводе с японского «су»— «цифра», а doku «доку»— «стоящая отдельно». Следовательно, «СУДОКУ» в приблизительном переводе означает «одиночная цифра».
Название "Sudoku" дало этой головоломке японское издательство Nicoli в 1984 году. Sudoku - это сокращение от "Suuji wa dokushin ni kagiru", что в переводе с японского означает "число должно быть единственным". Издательство Nikoli не только придумало звучное имя, но и впервые ввело симметрию в заданиях для своих головоломок. Название головоломке дал руководитель Nicoli - Кaji Maki. Весь мир принял это новое японское название, но в самой Японии головоломку называют "Nanpure". Nicoli зарегистрировало в своей стране слово "Sudoku" как торговую марку.
История происхождения СУДОКУ
Родиной шахмат считается Индия, родиной футбола - Англия. У игры судоку (sudoku), быстро распространившейся по всему миру, родины как таковой нет. Прообразом судоку можно считать головоломку “Магический квадрат”, которая появилась Китае 2000 лет назад.
История судоку как игры восходит к имени знаменитого швейцарского математика, механика и физика Леонарда Эйлера (1707 - 1783).
В бумагах его архива, датированных 17 октября 1776 года, содержатся записи о том, как образовать магический квадрат с определенным числом ячеек, особенно 9, 16, 25 и 36. В другом документе, озаглавленном «Научное исследование новых разновидностей магического квадрата» Эйлер помещал в клетки латинские буквы (Латинский квадрат), позже он заполнил клетки греческими буквами и называл квадрат греко-латинским. Исследуя различные варианты магического квадрата, Эйлер обратил внимание на проблему комбинации символов таким образом, чтобы не один из них не повторялся ни в одной строке и ни в одном столбце.
В современном виде головоломки судоку впервые были опубликованы в 1979 году в журнале Word Games magazine. Автором головоломки был Гарвард Гарис из Индианы. Головоломку «Number Place» (в переводе на русский - "место числа") - это можно считать одним из первых выпусков современных судоку. В ней были добавлены блоки размером 3х3 клетки, что было важным усовершенствованием, так как позволило сделать головоломку более интересной. Он использовал принцип латинского квадрата Эйлера, применил его в матрице размерностью 9х9 и добавил дополнительные ограничения, цифры не должны повторяться и во внутренних квадратах 3х3.
Таким, образом, идея судоку пришла не из Японии, как думают многие, однако название игры действительно японское.
В Японии эта головоломка была опубликована компанией Nicoly Inc., крупным издателем сборников различных головоломок, в газете Monthly Nicolist в апреле 1984 года под заголовком «Число может использоваться только один раз». 12 ноября 2004 года газета The Times впервые на своих страницах опубликовала головоломку судоку. Эта публикация стала сенсацией, головоломка быстро распространилась по всей Британии, Австралии, Новой Зеландии; приобрела популярность и в США.
Варианты судоку
Итак, что же собой представляет судоку? В настоящее время появилось множество модернизаций для этого популярного вида головоломок, но классическая судоку представляет собой квадрат 9х9 клеток, разбитый на подквадраты со сторонами по 3 клетки каждый. Таким образом, общее игровое поле составляет 81 клетку. В приложении к моей работе я помещу разные виды судоку и варианты решений (их мне помогали решить родители).
Судоку различаются по уровню сложности в зависимости от размера квадрата:
- 1. Для маленьких любителей головоломок делаются судоку с полями 2х2, 6х6 клетки.
- 2. Для профессионалов существуют судоку 15х15 и 16х16 клеток
Судоку бывают разных уровней:
- легкий
- средний
- сложный
- очень сложный
- суперсложный
Правила решения
У головоломок судоку всего одно правило. Необходимо заполнить свободные клетки так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3Х3 каждая цифра от 1 до 9 встречалась бы только 1 раз. Часть клеток в судоку уже заполнена цифрами, и вам остается заполнить остальные. Чем больше цифр стоит изначально, тем проще решить головоломку. Кстати, правильно составленная судоку имеет только одно решение.
Решение судоку
Стратегия решения судоку включает в себя три этапа:
- изучение расположения цифр в головоломке
- предварительная расстановка цифр
- анализ
Лучший способ решения — записывать числа-кандидаты в вершине левого угла ячейки. После этого можно увидеть именно те числа, которые должны занимать данную ячейку. Играть в судоку нужно медленно, так как это расслабляющая игра. Некоторые головоломки можно решить за несколько минут, но на другие можно потратить часы или, в отдельных случаях, даже дни.
Математическая основа. Количество возможных комбинаций в судоку 9x9 составляет по расчётам Бертхама Фельгенхауэра 6 670 903 752 021 072 936 960.
Доброго Вам времени суток, дорогие любители логических игр. В этой статье я хочу изложить основные методы, способы и принципы решения судоку. На нашем сайте представлено множество видов данной головоломки, а в будущем несомненно будет представлено ещё больше! Но здесь рассмотрим только классический вариант судоку, как основной для всех остальных. И все приёмы, изложенные в данной статье, будут также применимы и ко всем прочим видам судоку.
Одиночка или последний герой.
И так, с чего начинается решение судоку? Не важно простого уровня сложности или нет. Но всегда в начале идёт поиск очевидных клеток для заполнения.
На рисунке показан пример одиночки - это цифра 4, которую смело можно поставить на клетку 2 8. Так как шестая и восьмая горизонтали, а также первая и третья вертикали, уже четвёркой заняты. Они показан стрелками зелёного цвета. И в левом нижнем малом квадрате у нас остаётся только одна незанятая позиция. На картинке цифра помечена зелёным цветом. Так же расставлены остальные одиночки, но без стрелок. Они окрашены в синий цвет. Таких одиночек может быть довольно много, особенно если цифр в начальном условии много.
Различают три способа поиска одиночек:
- Одиночка в квадрате 3 на 3.
- По горизонтали
- По вертикали
Конечно можно хаотично просматривать и выявлять одиночек. Но лучше придерживаться какой-либо определённой системы. Самым очевидным будет начинать с цифры 1.
- 1.1 Проверить квадраты, где нет единицы, проверить горизонтали и вертикали, которые пересекают данный квадрат. И если в них уже стоят единички, то исключаем полностью линию. Таким образом ищем единственное возможное место.
- 1.2 Далее проверяем горизонтали. В каких присутствует единичка, а где нет. Проверяем в малых квадратах, в которые входит данная горизонталь. И если в них присутствует единичка, то пустые клетки данного квадрата исключаем из возможных кандидатов на искомую цифру. Так же проверим все вертикали и исключим те, в которых так же присутствует единичка. Если остаётся единственное возможное пустое место - то ставим искомую цифру. Если осталось два и более пустых кандидатов, то оставим данную горизонталь, переходим к следующей.
- 1.3 Аналогично предыдущему пункту проверяем все горизонтали.
"Скрытые единицы"
Ещё подобную методику называют "а кто, если не я?!" Посмотрите на рисунок 2. Поработаем с левым верхним малым квадратом. Сначала пройдёмся первым алгоритмом. После чего удалось выяснить, что в клетке 3 1 есть одиночка - цифра шесть. Ставим её, А во все остальные пустые клетки проставим мелким шрифтом все возможные варианты, применительно к малому квадрату.
После чего мы обнаруживаем следующее, в клетке 2 3 может стоять только одна цифра 5. Конечно в данный момент пятёрка может стоять и на других клетках - этому ничто не противоречит. Это три клетки 2 1, 1 2, 2 2. Но в клетке 2 3 цифры 2,4,7, 8, 9 стоять не могут, так как они присутствуют в третьей строке или во втором столбце. Исходя из этого мы с полным правом ставим цифру пять на это клетку.
Голая пара
Под это понятие я объединил несколько видов решения судоку: голая пара, тройка и четвёрка. Это сделано в связи с их однотипностью и различия лишь в количестве задействованных цифр и клеток.
И так, давайте разберёмся. Посмотрите на рисунок 3. Здесь мы обычным способом проставляем мелким шрифтом все возможные варианты. И подробно рассмотрим верхний средний малый квадрат. Здесь в клетках 4 1, 5 1, 6 1 у нас получился ряд одинаковых цифр - 1, 5, 7. Это голая тройка в истинном виде! Что это нам даёт? А то, что только в этих клетках будут расположены эти три цифры 1, 5, 7. Таким образом мы можем в среднем верхнем квадрате на второй и третьей горизонтали исключить эти цифры. Так же в клетке 1 1 мы исключим семёрку и сразу же ставим четыре. Так как других кандидатов нет. А в клетке 8 1 мы исключим единицу, насчёт четвёрки и шестёрки следует подумать дальше. Но это уже иная история.
Следует сказать, что выше рассмотрен только частный случай голой тройки. На самом деле комбинаций цифр может быть множество
- // три числа в трех ячейках.
- // любые комбинации.
- // любые комбинации.
Скрытая пара
Этот способ решения судоку позволит сократить количество кандидатов, и даст жизнь другим стратегиям. Посмотрите на рисунок 4. Средний верхний квадрат как обычно заполнен кандидатами. Цифры записаны мелким шрифтом. Зелёным цветом выделены две клетки - 4 1 и 7 1. Чем они нам примечательны? Только в этих двух клетках имеются кандидаты 4 и 9. Это и есть наша скрытая пара. По большому счёту она такая же пара, как и в пункте третьем. Только в клетках имеются и другие кандидаты. Вот этих других можно смело вычеркнуть с этих клеток.
Итак, сегодня я научу вас решать судоку .
Для наглядности возьмем конкретный пример и рассмотрим основные правила:
Правила решения судоку:
Желтым я выделил строку и столбец. Первое правило в каждой строке и каждом столбце могут быть цифры от 1 до 9, причем они не могут повторяться. Короче говоря – 9 клеток, 9 цифр – поэтому в 1-м и том же столбце не может быть 2-х пятерок, восьмерок и т.д. Аналогично для строк.
Теперь я выделил квадраты – это второе правило . В каждом квадрате могут быть цифры от 1-го до 9 причем они не повторяются. (Так же как и в строках и столбцах). Квадраты выделены жирными линиями.
Отсюда имеем общее правило для решения судоку : ни в строках , ни в столбцах ни в квадратах цифры не должны повторяться.
Ну что ж, давайте теперь попробуем его решить:
Я выделил единицы зеленым и показал направление, куда мы смотрим. А именно – нас интересует последний верхний квадрат. Можно заметить, что во 2-м и 3-м ряду этого квадрата не могут быть единицы иначе будет повторение. Значит – единица вверху:
Легко находится и двойка:
Теперь воспользуемся найденной только что двойкой:
Надеюсь, алгоритм поиска стал понятен, поэтому с этого момента буду рисовать быстрее.
Смотрим на 1-й квадрат 3-й строки (внизу):
Т.к. у нас там осталось 2 свободных клетки, то в каждой из них может быть одна из двух цифр: (1 или 6):
Это значит, что в столбце, который я выделил не может больше быть ни 1 ни 6 – значит в верхним квадрате ставим 6.
За неимением времени на этом и остановлюсь. Очень надеюсь, что логику вы уловили. Кстати, я взял не самый простой пример, в котором скорее всего не будут сразу видны все решения однозначно, а поэтому лучше пользоваться карандашом. Мы пока не знаем насчет 1 и 6 в нижнем квадрате, поэтому их рисуем карандашом – аналогично в верхнем квадрате будут карандашом нарисованы 3 и 4.
Если ещё немного порассуждать, используя правила - избавимся от вопроса где 3, а где 4:
Да, кстати, если вам какой-то момент показался непонятным – напишите, я поясню подробнее. Удачи с разгадыванием судоку.
Многим нравится заставлять себя думать: кому-то - для развития интеллекта, кому-то - для поддержания своих мозгов в хорошей форме (да-да, не только телу нужна зарядка), и лучшим тренажёром для ума являются различные игры на логику и головоломки. Одним из вариантов подобных развивающих развлечений можно назвать судоку. Однако некоторые и не слышали про такую игру, что уж говорить про знание правил или другие интересные моменты. Благодаря статье вы узнаете всю необходимую информацию, например, как разгадать судоку, а также их правила и виды.
Общее
Судоку - это головоломка. Иногда сложная, трудно раскрываемая, но всегда интересная и затягивающая любого человека, решившегося на эту игру. Название произошло от японского: «су» означает «цифра», а «доку» - это «стоящая отдельно».
Не все знают, как разгадывать судоку. Сложные головоломки, например, под силу либо умным, хорошо соображающим новичкам, либо профессионалам своего дела, практикующим игру не один день. Просто так взять и за пять минут решить поставленную задачу будет далеко не каждому возможно.
Правила
Итак, как разгадывать судоку. Правила очень просты и понятны, запомнить их легко. Однако не думайте, что несложные правила сулят «безболезненное» решение; думать придётся много, применять логическое и стратегическое мышление, стремиться воссоздать картину. Наверное, нужно любить цифры, чтобы разгадывать судоку.
Сначала чертится квадрат 9 х 9 клеток. Затем более жирными линиями он разделяется на так называемые «регионы» по три квадратика в каждом. В итоге получается 81 клетка, которая в конечном итоге должна быть полностью заполнена числами. В этом и заключается сложность: расставленные по всему периметру цифры от 1 до 9 не должны повторяться ни в «регионах» (квадратах 3 х 3), ни в линиях по вертикали и/или горизонтали. В любом судоку изначально присутствуют некоторые заполненные клетки. Без этого игра просто невозможна, поскольку иначе получится не разгадывание, а придумывание. От количества цифр зависит сложность головоломки. Сложные судоку содержат немного чисел, расставленных зачастую так, что придётся изрядно поломать голову, прежде чем решить их. В лёгких - около половины цифр уже стоят на своих местах, благодаря чему разгадать становится в разы проще.
Полностью разобранный пример
Сложно понять, как разгадать судоку, если нет конкретного образца, пошагово показывающего, как, куда и что нужно вставлять. Предоставленная картинка считается несложной, поскольку многие мини-квадраты уже заполнены необходимыми цифрами. К слову, именно на них мы и будем опираться для решения.
Для начала можно посмотреть на линии или квадраты, где особенно много цифр. Например, прекрасно подходит второй столбец слева, там не хватает всего двух чисел. Если посмотреть на те, что уже есть, становится очевидно, что не хватает 5 и 9 в пустующих клетках на второй и восьмой строках. С пятёркой пока не всё ясно, она может быть и там, и там, но если взглянуть на девятку - всё становится понятно. Так как на второй строке уже есть цифра 9 (в седьмом столбце), значит, чтобы не было повторов, девятку нужно поставить вниз, на 8-ю строчку. Методом исключения добавляем 5 на 2-ю строку - и вот у нас уже есть один заполненный столбец.
Аналогичным способом можно решить всю головоломку судоку, однако в более сложных вариантах, когда в одном столбце, строке или квадрате не хватает не пары цифр, а гораздо больше, придётся применять немного иной способ. Его мы тоже сейчас разберём.
На сей раз возьмём за основу средний «регион», в котором не хватает пяти цифр: 3, 5, 6, 7, 8. Каждую клетку мы заполняем не большими результативными числами, а маленькими, «черновыми». Просто пишем в каждый квадратик те цифры, которых не хватает и которые могут быть там из-за их нехватки. В верхней клетке это 5, 6, 7 (3 на этой строке уже есть в «регионе» справа, а 8 - слева); в клетке слева могут быть 5, 6, 7; в самой середине - 5, 6, 7; справа - 5, 7, 8; снизу - 3, 5, 6.
Итак, теперь смотрим, какие мини-цифры содержат отличные от прочих числа. 3: есть только в одном месте, в остальных её нет. Значит, её можно исправлять на большую. 5, 6 и 7 есть как минимум в двух клетках, значит, оставляем их в покое. 8 есть только в одной, значит, остальные цифры отпадают и можно оставлять восьмёрку.
Чередуя эти два способа, продолжаем разгадывать судоку. В нашем примере мы будем применять первый способ, однако следует напомнить, что в сложных вариациях второй необходим. Без него будет крайне сложно.
Кстати, когда в верхнем «регионе» обнаружилась серединная семёрка, её можно убрать из мини-цифр среднего квадрата. Если это сделать, можно заметить, что в том регионе осталась одна 7, поэтому можно только её и оставить.
Вот и всё; готовый результат:
Виды
Головоломки судоку бывают разными. В каких-то обязательным условием является отсутствие одинаковых цифр не только в строках, столбцах и мини-квадратах, но также по диагонали. В каких-то вместо привычных «регионов» содержатся другие фигуры, из-за чего решить задачу становится в разы сложнее. Так или иначе, как разгадать судоку, по крайней мере, основное правило, что действует на любой вид, вы знаете. Это всегда поможет справиться с головоломкой любой сложности, главное - пытаться изо всех сил добиться поставленной цели.
Заключение
Теперь вы знаете, как разгадать судоку, а потому можете скачивать подобные головоломки с различных сайтов, решать их онлайн или покупать в газетных киосках бумажные варианты. В любом случае, теперь у вас появится занятие на долгие часы, а то и дни, потому что затягивают судоку нереально, особенно когда приходится на деле разобраться в принципе их решения. Практика, практика и ещё раз практика - и тогда вы будете щёлкать эту головоломку как орешки.
ВКонтакте Facebook Одноклассники
Для тех, кому нравится решать загадки cудоку самостоятельно и неспешно, формула, позволяющая быстро вычислить ответы, может показаться признанием слабости или жульничеством
Но для тех, кому разгадывание судоку стоит слишком больших усилий, это может быть буквально идеальным решением.
Два исследователя разработали математический алгоритм, который позволяет решать судоку очень быстро, без предположений и перебора с возвратом.
Исследователи комплексных сетей Золтан Торожкай и Мария Эркси-Раваз из Университета Нотр-Дама также смогли объяснить, почему некоторые загадки судоку более сложные, чем другие. Единственный недостаток в том, что для того, чтобы понять, что они предлагают, нужна степень доктора математики.
Вы можете решить эту головоломку? Она создана математиком Арто Инкалой, и, как утверждают, это самая сложная судоку в мире. Фото с сайта nature.com
Торожкай и Эркси-Раваз начали анализировать судоку как часть своего исследования теории оптимизации и вычислительной сложности. Они говорят, что большинство любителей судоку используют для решения этих задач подход «грубой силы», основанный на технике предположения. Таким образом, любители судоку вооружаются карандашом и пробуют все возможные комбинации чисел, пока не будет найден правильный ответ. Этот метод неизбежно приведет к успеху, но он трудоемок и занимает много времени.
Вместо этого Торожкай и Эркси-Раваз предложили универсальный аналоговый алгоритм, который абсолютно детерминирован (не использует предположение или перебор) и всегда находит правильное решение задачи, причем довольно быстро.
Исследователи использовали «детерминированный аналоговый решатель», чтобы заполнить эту судоку. Фото с сайта nature.com
Исследователи также обнаружили, что время, которое требуется, чтобы решить головоломку с использованием их аналогового алгоритма, коррелируется со степенью сложности задачи, которая оценивается человеком. Это вдохновило их на то, чтобы развивать шкалу ранжирования для трудности загадки или проблемы.
Они создали шкалу от 1 до 4, где 1 - «легко», 2 - «средняя степень сложности», 3 - «сложно», 4 - «очень сложно». Для решения головоломки с рейтингом 2 требуется в среднем в 10 раз больше времени, чем для задачки с рейтингом 1. Согласно этой системе, самая сложная загадка из известных до сих пор имеет рейтинг 3.6; более сложные задачи судоку пока неизвестны.
Теория начинается с картографии вероятностей для каждого отдельного квадрата. Фото с сайта nature.com
«Я не интересовался судоку, пока мы не начали работать над более общим классом выполнимости Булевых проблем, - говорит Торожкай. - Так как судоку - часть этого класса, латинский квадрат 9-го порядка оказался для нас хорошим полем для испытаний, так я с ними и познакомился. Меня и многих исследователей, изучающих такие проблемы, захватывает вопрос, как далеко мы, люди, способны зайти в решении судоку, детерминировано, без перебора, который является выбором наугад, и, если догадка не верна, нужно вернуться на шаг или на несколько шагов назад и начать сначала. Наша аналоговая модель решения детерминирована: в динамике нет никакого случайного выбора или возвращения».
Теория хаоса: степень сложности загадок показывается здесь как хаотическая динамика. Фото с сайта nature.com
Торожкай и Эркси-Раваз полагают, что их аналоговый алгоритм потенциально подходит для применения к решению большого количества разнообразных задач и проблем в промышленности, информатике и вычислительной биологии.
Опыт исследования также сделал Торожкая большим любителем судоку.
«У моей жены и у меня есть несколько приложений судоку на наших iPhone, и мы, должно быть, сыграли уже тысячи раз, соревнуясь за меньшее время на каждом уровне, - говорит он. - Она часто интуитивно видит комбинации паттернов, которых я не замечаю. Я должен их выводить. Для меня становится невозможным решить многие головоломки, которые наша шкала категоризирует как трудные или очень трудные, без того, чтобы записывать вероятности карандашом».
Методология Торожкая и Эркси-Раваз была впервые опубликована в журнале Nature Physics, а затем - в журнале Nature Scientific Reports.
