Как работает судоку

Если вы были в книжном магазине за последние шесть месяцев — или в аэропорту , зале ожидания или на лекции в колледже — вы, вероятно, видели, как кто-то смотрит на судоку. Учитывая его популярность, можно подумать, что это какой-то новый вид порно. Но нет, это просто головоломка. Это широко распространенная, основанная на логике головоломка, которая достаточно проста, чтобы затянуть вас, и достаточно сложна, чтобы удержать вас на крючке.

В этой статье мы узнаем, что влечет за собой головоломка судоку, как решить ее и откуда возникла эта концепция (подсказка: это не Япония. Давайте начнем.

Основы судоку

Судоку (или судоку) — это игра с числами, в частности, числами от 1 до 9, но на самом деле она не связана с математикой. Это про логику . Вместо цифр от 1 до 9 вы могли бы использовать первые девять букв алфавита или набор из девяти символов, и это была бы та же самая игра.

Основой судоку является сетка девять на девять . У вас есть три раздела, о которых нужно подумать: строки , столбцы и блоки .

Цель судоку состоит в том, чтобы заполнить каждую строку из девяти квадратов, каждый столбец из девяти квадратов и каждую ячейку из девяти квадратов числами от 1 до 9, причем каждое число используется один и только один раз в каждом разделе. Именно взаимодействие между строками, столбцами и прямоугольниками говорит вам, куда должны идти числа. Итак, если бы вы начали с пустой сетки и заполнили числами строку 1, столбец 2 и поле 4 в соответствии с правилами судоку, это могло бы выглядеть примерно так:

Конечно, начать с пустой сетки не составит особого труда. В головоломке судоку уже есть некоторые заполненные числа, и ваша задача — выяснить, куда идут остальные числа. Вот пример реальной головоломки судоку из «Книги судоку 3» Майкла Мефэма:

У судоку есть несколько уровней сложности, от простого до очень сложного, в зависимости от того, сколько чисел вы получите для начала и где эти числа расположены. (Майкл Мефам, создатель головоломок для лондонской Daily Telegraph , оценивает свои головоломки как «мягкие», «умеренные», «сложные» или «дьявольские».) Простая головоломка дает вам достаточно чисел, расположенных в достаточном количестве стратегических позиций, чтобы вы могли найти ответ, используя довольно простую логику. Каждая головоломка имеет только один ответ .

Лучший способ научиться искусству судоку — это решить головоломку. Давайте пройдемся по простой головоломке выше, чтобы почувствовать процесс. Если вы можете решить простую головоломку, вы можете решить и сложную — просто это займет у вас больше времени.

История

Судоку, адаптированный из математической концепции под названием «латинские квадраты», начинался как «число мест» в книгах-головоломках Dell 70-х годов. "Number Place" не был очень популярен в США, но в 1984 году он попал в Японию и стал хитом. Нобухико Канамото, редактор японского издательства головоломок Nikoli, назвал его Suuji Wa Dokushin Ni Kagiru («Числа должны быть одиночными»). Позже его сократили до «судоку» или «одного числа».

В 1997 году новозеландец Уэйн Гулд открыл для себя судоку во время поездки в Японию и попытался привезти ее в Соединенные Штаты. Он потратил годы на написание компьютерной программы для создания головоломок. Гулд представил его USA Today, которое отказалось, но New York Post подхватила его в апреле 2005 года.

Содержание

1. Решение судоку: простая логика
2. Решение судоку: возможные числа
3. Решение судоку: возможные квадраты
4. Решение судоку: дьявольское и не только

Нет правильного места, чтобы начать головоломку судоку. Вы можете закрыть глаза, положить палец на загадку и начать оттуда, и это самое правильное место, как и любое другое. Однако, вероятно, наиболее логичным будет начать со строки, столбца или поля, в котором много чисел. Давайте посмотрим на головоломку с предыдущей страницы:

В столбцах 4 и 6 заполнено по шесть чисел. Давайте начнем головоломку со столбца 4, в котором уже есть числа 1, 3, 4, 5, 8 и 9.

Для того, чтобы иметь одну и только одну каждую цифру от 1 до 9, нам нужно предоставить столбцу 4 свои 2, 6 и 7. Но мы не можем просто поместить их куда угодно — каждое число имеет конкретное место в ответе головоломки. Итак, куда идет каждое число? Чтобы выяснить это, нам нужно посмотреть на строки и поля, которые взаимодействуют со столбцом 4. Взгляните на пустой квадрат в строке 3, столбце 4 (3,4), а также на строку и поле, которые с ним взаимодействуют:

Подход « простой логики » к судоку требует только визуального анализа и выглядит примерно так: может ли двойка попасть в пустой квадрат? Это невозможно, потому что в ячейке 2 уже есть 2, и в ней может быть только по одной каждой цифре. Может ли 7 пойти туда? В строке 3 уже есть 7, поэтому мы не можем поставить 7 и там. Это оставляет нас с 6. Ни в строке 3, ни в поле 2 еще нет 6, поэтому мы знаем, что 6 является правильным для этой ячейки. Мы решили наш первый номер!

Теперь давайте решим оставшуюся часть столбца 4, для которого все еще нужны 2 и 7. Пустой квадрат 5,4 взаимодействует со строкой 5 и блоком 5, а пустой квадрат 7,4 взаимодействует со строкой 7 и блоком 8.

Поскольку в ячейке 5 уже есть 7, мы не можем поставить 7 на квадрат 5,4. Итак, мы тут же знаем, что 2 идет на 5,4, а 7 должна идти на 7,4:

Теперь мы решили весь столбец 4, и мы использовали для этого только простую логику. Поскольку это простая головоломка, мы, вероятно, могли бы решить большую ее часть таким образом. Но не всегда все так однозначно. Есть стратегии, которые мы можем использовать, когда решение не столь очевидно, и все начинается с нескольких карандашных пометок.

Карандаш в возможных решениях для пустых квадратов становится критически важным, поскольку головоломки судоку становятся все сложнее. Но вы не угадываете, когда рисуете карандашом. Вы просто перечисляете возможные решения. Вы не должны угадывать судоку - это, вероятно, в конечном итоге приведет к тому, что вся головоломка будет испорчена, так что вам придется начинать все сначала, потому что все взаимосвязано.

Записывая карандашом все возможные числа для каждого квадрата в заданной строке, столбце или поле, мы можем использовать определенные стратегии для решения раздела. Давайте посмотрим на ряд 7, в котором есть четыре пустых квадрата и нужны 4, 5, 6 и 9.

Мы запишем все числа, которые могли бы решить каждый пустой квадрат соответственно. Итак, какое из чисел 4, 5, 6 и 9 может решить квадрат 7,2? 4 не может попасть туда, потому что в столбце 2 уже есть 4. Число 5 возможно, потому что ни в строке 2, ни в ячейке 7 еще нет 5. 6 отсутствует, потому что в ящике 7 уже есть 6. Здесь может быть 9, потому что в строке 2 и в ячейке 7 отсутствует 9. Итак, мы нарисуем «5 9» для квадрата:

Используя тот же процесс для квадрата 7,5, мы можем исключить 4 и 9 (в коробке 8 уже есть по одной каждой) и нарисовать 5 и 6. Для квадрата 7,6 мы можем нарисовать карандашом 5 и 6. А для квадрата 7,8 подойдет любое из чисел:

Глядя на числа, которые вы вписали карандашом, вы заметите две вещи: во-первых, два квадрата имеют одну и ту же пару чисел (и только эти два числа), а во-вторых, 4 появляется только один раз. Начнем с 4, которая появляется только в квадрате 7,8. Используя то, что мы назовем стратегией «единственного вхождения», мы знаем, что если единственное место, где может быть 4, находится в 7,8, мы решили этот квадрат, потому что в строке 7 нужна 4. Итак, теперь строка 7 выглядит как это:

Теперь давайте посмотрим на повторяющуюся пару: и 5, и 6 — и только 5 и 6 — могут входить в квадраты 7,5 и 7,6. Здесь у нас есть набор совпадающих пар. Пятерка должна попасть в одну из этих двух клеток, а шестерка — в одну из этих двух клеток. Используя стратегию сопоставления пар , мы теперь можем исключить 5 из квадрата 7,2, потому что мы знаем, что он туда не входит. Мы решили еще один квадрат:

Кстати, стратегия исключения «совпадающих пар» также работает как «совпадающие тройки», когда у вас есть три квадрата с одним и тем же трио чисел, и только это трио чисел, в каждом квадрате.

Из того, что мы нарисовали до сих пор, мы до сих пор не знаем, какой квадрат получает 5, а какой — 6, поэтому мы нарисуем еще несколько чисел. Давайте посмотрим, что мы можем сделать с коробкой 8, в которой четыре пустых клетки и нужны 1, 2, 5 и 6.

Два из этих квадратов уже закрашены соответствующей парой чисел 5 и 6, поэтому мы знаем, что можем исключить 5 и 6 из возможных решений для других квадратов. Это оставляет нам 1 и 2. Любое из этих чисел может решить квадрат 8,5 — ни в строке 8, ни в столбце 5 нет 1 или 2. Но в строке 9 есть 2, поэтому мы не можем зачеркнуть. 2 для квадрата 9,5. Вот что у нас есть:

Заметили что-нибудь? В квадрате 9,5 всего одно число. Используя то, что Мефам называет стратегией одиночного числа — вероятно, самой простой стратегией в судоку — мы знаем, что 1 — это решение в 9,5. А так как 1 для ячейки 8 находится на 9,5, мы можем удалить зачеркнутую 1 из квадрата на 8,5, оставив только 2 и еще один решенный квадрат.

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

В столбце 6 нужны 1, 5 и 6. Для квадрата 3, 6, 1 и 5 являются возможными (в третьем ряду уже есть 6). Для квадрата 5,6 единственным возможным решением будет 6, потому что в ячейке 5 уже есть 1 и 5.

Теперь мы знаем, что решение в 7,6 должно быть 5, решение в 3,6 должно быть 1, а решение в 7,5 должно быть 6.

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

На этот раз вместо того, чтобы искать правильное число для квадрата, мы будем искать правильный квадрат для числа. Для этого мы нарисуем несколько линий. Взгляните на поле 6:

Ящику 6 нужен номер 4. Давайте выясним, куда он пойдет, убрав все ящики, куда он не может попасть. В строке 5 есть 4, поэтому мы проведем линию через эту строку. Также есть 4 в строке 6 и столбцах 7 и 8. Мы проведем линии через все это.

Теперь в ячейке 6 есть только одна открытая клетка — клетка 4,9. Мы решили 4.

Давайте нарисуем еще несколько линий, чтобы найти положение 6. Мы можем зачеркнуть ряд 5, ряд 6 и столбец 9, оставив только один свободный квадрат. Мы можем поставить 6 в квадрате на 4,8.

Теперь у вас есть все необходимые знания, чтобы решить головоломку самостоятельно!

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

Хотя судоку — это логическая игра, есть некоторые головоломки, которые в конечном счете бросают вызов логике и требуют — к ужасу многих любителей судоку — угадывания.

До недавнего времени некоторые судоку Майкла Мефэма с дьявольским рейтингом в лондонской Daily Telegraph не могли быть решены одной лишь логикой. На самом деле они требовали угадывания в определенный момент, что сторонники судоку считают настоящим запретом. Из-за большого количества споров (и писем с ненавистью), которые получил Мефам, он прекратил публиковать головоломки, требующие отгадывания. Тем не менее, процесс решения одной из этих головоломок интересен хотя бы потому, что вы должны знать достаточно, чтобы быть абсолютно уверенным, что больше нет подсказок, прежде чем вы начнете процесс угадывания. Мефам назвал эту стратегию « Нить Ариадны».(см. ниже), что влечет за собой выбор одного из двух возможных решений для данного квадрата и следование ему до тех пор, пока не будет найдено решение или тупик. количество.

В «Книге судоку 3» Майкла Мефэма есть дьявольская судоку, которая начинается так:

Используя логику, вы можете получить здесь:

Но логических подсказок больше нет — мы застряли. Единственный оставшийся нам вариант — угадать — и оставить наши числа карандашом, чтобы мы могли проследить Нить Ариадны обратно к исходной точке, если наша догадка окажется неверной. Если мы выберем один из квадратов только с двумя вариантами, у нас есть 50/50 шансов выбрать правильный номер. Давайте перейдем к строке 2, столбцу 1 и выберем 4. Предполагая, что 4 является решением квадрата 2,1, мы можем решить множество других квадратов путем расширения, но в итоге мы получим проблему.

Если решение в 1,7 равно 4, то решение в 6,7 должно быть 5. Но в строке 6 уже есть 5. Итак, теперь нам нужно стереть решения, которые мы нарисовали, из нашего предположения, и вернуться к квадрату. 2,1. На этот раз мы выберем 5.

Число 5 действительно является решением квадрата 2,1, и оно позволяет нам решить всю головоломку.

Хотя Мефам перестал публиковать судоку в своей колонке, вы все еще можете получить к ним доступ на веб-сайте судоку Мефама, sudoku.org.uk.

В ответ на огромную популярность судоку появились различные версии головоломки, которые еще больше усложняют задачу. Один из видов «экстремальных судоку» — это трехмерные судоку . Просто выровняйте девять полных сеток судоку в трехмерный куб, который требует полных строк, столбцов и блоков на трех взаимосвязанных осях, и у вас есть трехмерная головоломка судоку. Применяются все те же правила, но теперь вы работаете на нескольких плоскостях. Чтобы собрать куб, вам нужно проработать решения для каждой из девяти сеток по отдельности, хотя, если вы загрузите одну из десятков компьютерных программ для трехмерных судоку, вы сможете работать над головоломкой во всей трехмерной славе.

Ответ на головоломку с предыдущей страницы

Для получения дополнительной информации о судоку и смежных темах перейдите по ссылкам на следующей странице.

Нить Ариадны

В греческой мифологии царь Крита Минос требует человеческих жертв за чудовище, которое он держит в своем лабиринте. Вместо этого молодой воин Тесей решает уничтожить чудовище, и дочь короля Ариадна влюбляется в Тесея. Она придумывает верный способ для Тесея найти выход из лабиринта после того, как он убьет зверя: Тесей проложит нить на каждом шагу пути в лабиринт. Когда он дойдет до тупика, он вернется по своим следам с ниткой в ​​руке и выберет другой маршрут. К тому времени, когда он доберется до монстра, у него будет нить, ведущая прямо из лабиринта для его обратного пути.

Первоначально опубликовано: 20 февраля 2006 г.

Есть ли формула решения судоку?

Как выиграть судоку?

Почему судоку так сложно?

Судоку это японское слово?

Какой самый сложный уровень судоку?

Статьи по Теме

Больше отличных ссылок