Доброго Вам времени суток, дорогие любители логических игр. В этой статье я хочу изложить основные методы, способы и принципы решения судоку. На нашем сайте представлено множество видов данной головоломки, а в будущем несомненно будет представлено ещё больше! Но здесь рассмотрим только классический вариант судоку, как основной для всех остальных. И все приёмы, изложенные в данной статье, будут также применимы и ко всем прочим видам судоку.
Одиночка или последний герой.
И так, с чего начинается решение судоку? Не важно простого уровня сложности или нет. Но всегда в начале идёт поиск очевидных клеток для заполнения.
На рисунке показан пример одиночки - это цифра 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. Это и есть наша скрытая пара. По большому счёту она такая же пара, как и в пункте третьем. Только в клетках имеются и другие кандидаты. Вот этих других можно смело вычеркнуть с этих клеток.
В предыдущих статьях мы рассматривали разные подходы в решении проблем на примерах головоломок судоку. Пришло время попытаться, в свою очередь, проиллюстрировать возможности рассмотренных подходов на достаточно сложном примере решения проблем. Итак, сегодня мы приступим к самому "невероятному" варианту судоку. Терминологию и предварительные сведения вы, уж будьте так любезны, посмотрите в , иначе вам трудно будет понять содержание данной статьи.
Вот какие сведения я нашел об этом сверхсложном варианте в интернете:
Профессор Хельсинского университета Арто Инкала (Arto Inkala) утверждает (2011г.), что он создал самый сложный в мире кроссворд судоку. Эту сложнейшую головоломку он создавал три месяца.
По его словам, созданный им кроссворд невозможно решить с помощью одной лишь только логики. Арто Инкала утверждает, что даже самые опытные игроки на решение потратят не меньше нескольких дней. Изобретение профессора получило название AI Escargot (AI – инициалы ученого, Escargot – от англ. «улитка»).
Для решения этой непростой задачи, как утверждает Арто Инкала, в голове одновременно нужно держать восемь последовательностей, в отличие от обычных головоломок, где помнить нужно об одной-двух последовательностях.
Ну, "последовательности переборов" – это все же отдает машинным вариантом решения проблем, а те, кто решал задачу Арто Инкала посредством собственных мозгов, говорят об этом по-разному. Кто-то решал ее пару месяцев, кто-то объявил о том, что на это потребовалось лишь 15 минут. Ну что ж, чемпион мира по шахматам возможно и справился бы с задачей за такое время, а экстрасенс, если таковые обитают на нашей плане, возможно и еще быстрее. А еще мог быстро решить задачу тот, кто случайно с первого разу подобрал несколько удачных цифр для заполнения пустых ячеек. Скажем, одному из тысячи решателей задачи могло бы подобным образом и повезти.
Так вот, о переборе: если удачно выбрать две три правильных цифры, то перебирать восемь последовательностей (а это десятки вариантов) может и не потребоваться. Такое у меня было соображение, когда я решил приступить к решению указанной задачи. Для начала я, будучи уже подготовленным в рамках методик предыдущих статей, решил забыть о том, что знал до сих пор. Есть такой прием, заключающийся в том, что поиск решения должен протекать свободно, без навязанных ему схем и идей. А ситуация для меня была новой, так что требовалось на нее и по-новому взглянуть. Я расположил (в Эксель) исходную таблицу (справа) и рабочую таблицу, о смысле которой я уже имел случай рассказать в первой о судоку моей статье :
Рабочая таблица, напомню, содержит предварительно допустимые сочетания цифр в исходно пустых ячейках.
После обычной почти рутинной обработки таблиц ситуации немного упростилась:
Эту ситуацию я и начал изучать. Ну а поскольку я уже подзабыл, как именно я решал эту задачу несколькими днями раньше, то начинаю осмысливать ее по новой. Прежде всего, я обратил внимание на два числа 67 в ячейках четвертого блока и совместил их с механизмом вращения (перемещения) ячеек, о котором рассказывал в предыдущей статье. Перебрав все варианты вращения трех первых столбцов таблицы, я пришел к выводу, что цифры 6 и 7 не могут находиться в одном столбце и не могут вращаться асинхронно, они, в процессе вращения, могут лишь следовать одна за другой. Также, если присмотреться, семерка с четверкой как бы передвигаются синхронно по всем трем столбцам. Поэтому я делаю правдоподобное предположение, что в нижней левой ячейке блока 4 должна разместиться цифра 7, а в правой верхней – соответственно 6.
Но этот результат я пока принимаю лишь как возможный ориентир в опробовании других вариантов. А основное внимание я обращаю на число 59 в ячейке 4-го блока. Здесь может быть либо цифра 5, либо 9. Девятка обещает уничтожить очень много лишних цифр, т.е. упростить дальнейший ход решения задачи, и я начинаю с этого варианта. Но довольно быстро захожу в "тупик", т.е. далее надо снова делать какой-то выбор и как знать, как долго мой выбор будет проверяться. Я предполагаю, что если бы девятка действительно была когда-то правильным выбором, то Инкала вряд ли бы оставил такой очевидный вариант на виду, хотя механизм его программы мог и допустить подобный ляпсус. В общем, так или иначе, я решил сначала досконально проверить вариант с цифрой 5 в ячейке с числом 59.
Но уже позже, когда решил задачу, я, так сказать для очистки совести, все же вернулся к варианту с цифрой 9, чтобы определить как долго пришлось бы его проверять. Проверять пришлось не очень долго. Когда у меня в правой верхней ячейке блока 4 оказалась цифра 6, как и полагалось по предварительно выбранному ориентиру, то в правой средней ячейке возникло число 19 (убралась 6 из 169). Я выбрал для дальнейшего опробование цифру 9 в этой ячейке и быстро пришел к противоречивому результату, т.е. выбор девятки не верен. Тогда выбираю цифру 1 и снова проверяю, что из этого выйдет.
На каком-то шаге прихожу к ситуации:
где снова приходится делать выбор – цифру 2 или 8 в верхней средней ячейке блока 4. Проверяю оба варианта (2 и 8) и в обоих случаях заканчиваю противоречивым (не отвечающим условию судоку) результатом. Так что мог бы проверить вариант с цифрой 9 в средней нижней ячейке блока 4 с самого начала и много времени на это не потребовалось бы. Но я все же, как уже говорил, остановился на цифре 5 в упомянутой ячейке. Это привело меня к следующему результату:
Расположение цифр 4 и 7 в первых трех столбцах (колонках) свидетельствует о том, что они вращаются синхронно, что собственно и предполагалось при выборе цифры 7 для нижней левой ячейки 4-го блока. При этом двойка или девятка, будь любая из них требуемой цифрой в средней левой ячейке этого блока, должны соответственно двигаться асинхронно паре 4 и 7. Предпочтение в данном случае я отдал цифре 2, так как она "обещала" устранить много лишних цифр из чисел ячеек и, соответственно, быструю проверку допустимости данного варианта. А девятка быстро заводила в тупик – требовала подбора новых цифр. Таким образом, в левой средней ячейке блока с числом 29 я проставил не мой взгляд более предпочтительную из цифр – 2. Результат вышел следующим:
Далее мне пришлось еще раз сделать так сказать полупроизвольный выбор: выбрал двойку в ячейке с числом 26 в девятом блоке. Для этого достаточно было заметить, что 5 и 2 в трех нижних строках вращаются синхронно, так как 5 не вращалась синхронно ни с 1, ни с 6. Правда, синхронно могли вращаться еще 2 и 1, но из каких-то соображений – точно не помню – я выбрал 2 вместо числа 26, возможно потому, что этот вариант, по моей оценке, быстро проверялся. Впрочем, уже оставалось немного вариантов, и можно было достаточно быстро проверить любой из них. Можно было также вместо варианта с двойкой предположить, что цифры 7 и 8 вращаются синхронно в последних трех столбцах (колонках), а отсюда следовало, что в левой верхней ячейке 9-го блока могла быть только цифра 8, что также приводит к быстрой развязке задачи.
Надо сказать, что задача Арто Инкала не допускает чисто логического решения в рамках возможностей обычного человека – так она задумана, – но все же позволяет заметить некоторые перспективные варианты перебора возможных подстановок цифр и существенно сократить этот перебор. Попробуйте начать перебор с иных, чем в данной статье, позиций, и вы, убедитесь, что почти все варианты очень быстро заводят в тупик и требуется делать все новые и новые предположения относительно дальнейшего выбора подходящих подстановок цифр. Месяца два назад я уже пытался решить эту задачу, не имея той подготовки, которую я описал в предыдущих статьях. Проверил вариантов десять ее решения и оставил дальнейшие попытки. Последний же раз, уже будучи более подготовленным, я решал эту задачу полдня или немного более, но при этом с одновременным обдумыванием выбора с моей точки зрения наиболее показательных для читателей вариантов и также с предварительным обдумыванием текста будущей статьи. А окончательный результат решения получился следующий:
Собственно, данная статья не имеет самостоятельного значения, она написана лишь для иллюстрации того, как приобретенные навыки и теоретические соображения, описанные в предыдущих статьях, позволяют решать довольно сложные проблемы. А статьи были, напомню, не о судоку, а о механизмах решения проблем на примере судоку. Предметы, как по мне, совершенно разные. Однако поскольку судоку интересует многих, то я таким образом решил привлечь внимание к более существенному вопросу, касающемуся не собственно судоку, но решения проблем.
А в остальном – желаю вам успехов в решении всех проблем.
Цель судоку – расставить все цифры так, чтобы в квадратах 3х3, строках и столбцах не было одинаковых цифр. Вот пример уже решенного судоку:
Можно проверить, что в каждом из девяти квадратов, а и так же во всех строках и столбцах нет повторяющихся чисел. Решая судоку нужно пользоваться этим правилом «уникальности» числа и, последовательно исключая кандидатов (маленькие числа в клетке обозначают какие числа, по мнению игрока, могут стоять в этой клетке), находить места, где может стоять только одно число.
Открыв судоку, мы видим, что в каждой клетке проставлены все маленькие серые числа. Можно сразу убрать отметки с уже выставленных чисел (отметки убираются щелчком правой мыши по маленькому числу):
Начну с числа, которое в данном кроссворде есть в одном экземпляре - 6, чтобы было удобнее показать исключение кандидатов.
Числа исключаются в квадрате с числом, в строке и столбце, убираемые кандидаты отмечены красным – по ним мы и кликнем правой кнопкой мыши, отметив, что здесь шестерок в этих местах быть не может (иначе получится две шестерки в квадрате/столбце/строке, что противоречит правилам).
Теперь, если вернуться к единицам, то картина исключений будет следующей:
Мы убираем кандидаты 1 в каждой свободной клетке квадрата, где уже есть 1, в каждой строке, где есть 1 и в каждом столбце, где есть 1. Итого для трех единиц будет 3 квадрата, 3 столбца и 3 строки.
Далее перейдем сразу к 4, цифр больше, но принцип тот же. И если присмотреться, то видно, что в левом верхнем квадрате 3х3 остается всего одна свободная клетка (отмечена зеленым), где может стоять 4. Значит, ставим туда цифру 4 и стираем всех кандидатов (других чисел там стоять больше не может). В простых судоку таким образом можно заполнить довольно много полей.
После того, как выставлено новое число – можно перепроверить предыдущие, ведь добавление нового числа сужает круг поиска, например, в этом кроссворде благодаря выставленной четверке, под единицу в этом квадрате осталась всего одна клетка (зеленая):
Из трех доступных клеток под единицу не занята всего одна, туда единицу и ставим.
Таким образом убираем всех очевидных кандидатов для всех чисел (от 1 до 9) и проставляем числа по возможности:
После удаления всех очевидно неподходящих кандидатов получилась клетка, где остался всего 1 кандидат (зеленая), значит, там это число – тройка, и стоит.
Так же числа ставятся, если кандидат остался последним в квадрате, строке или столбце:
Это примеры на пятерках, можно увидеть, что в оранжевых клетках пятерок нет, а в зеленых клетках остается единственный кандидат в области, значит, пятерки там и стоят.
Это самые начальные способы простановки чисел в судоку, можно уже опробовать их, решая судоку на простой сложности (одна звезда), например: Судоку № 12433 , Судоку № 14048 , Судоку № 526 . Указанные судоку полностью решаются с использованием информации выше. Но в случае, если не получается найти следующую цифру, можно прибегнуть к методу подбора – сохранить судоку, и попробовать наугад проставить какую-нибудь цифру, а в случае неудачи загрузить судоку.
Если хочется освоить более сложные методы, читайте далее.
Запертые кандидаты
Запертый кандидат в квадрате
Рассмотрим следующую ситуацию:
В квадрате, выделенном синим, кандидаты цифры 4 (зеленые ячейки) располагаются в двух клетках на одной линии. Если на этой линии (оранжевые клетки) будет стоять цифра 4, то в синем квадрате некуда будет поставить 4, значит – исключаем 4 из всех оранжевых клеток.
Аналогичный пример для цифры 2:
Запертый кандидат в строке
Этот пример похож на предыдущий, но здесь в строке (синяя) кандидаты 7 располагаются в одном квадрате. Это значит, что из всех оставшихся клеток квадрата (оранжевые) удаляются семерки.
Запертый кандидат в столбце
Аналогично предыдущему примеру, только в столбце кандидаты 8 расположены в одном квадрате. Так же убираются все кандидаты 8 из других клеток квадрата.
Освоив запертых кандидатов, можно решать судоку средней сложности без подбора, например: Судоку № 11466 , Судоку № 13121 , Судоку № 11528 .
Группы чисел
Группы увидеть сложнее, чем запертых кандидатов, но они помогают пройти многие тупиковые ситуации в сложных кроссвордах.
Голые пары
Самый простой подвид групп – это две одинаковые пары чисел в одном квадрате, строке или столбце. Для примера голая пара чисел в строке:
Если в любой другой клетке в оранжевой строке будет 7 или 8, то в зеленых клетках останется 7 и 7, либо 8 и 8, но по правилам невозможно, чтобы в строке было 2 одинаковых числа, значит все 7 и все 8 убираются из оранжевых клеток.
Еще пример:
Голая пара одновременно в одном столбце и в одном квадрате. Удаляются лишние кандидаты (красные) и из столбца и из квадрата.
Важное замечание – группа должна быть именно «голой», то есть не содержать других чисел в этих клетках. То есть и являются голой группой, а и – нет, так как группа уже не голая, есть лишнее число - 6. Так же и не являются голой группой, так как числа должны быть одинаковы, а здесь 3 разных числа в группе.
Голые тройки
Голые тройки похожи на голые пары, но обнаружить их сложнее – это 3 голых числа в трех клетках.
В примере числа в одной строке повторяются 3 раза. В группе всего 3 числа и они располагаются на 3-х клетках, значит лишние числа 1, 2, 6 из оранжевых клеток удаляются.
Голая тройка может не содержать числа в полном составе, например, подошла бы комбинация: , и – это все те же 3 типа чисел в трех клетках, просто в неполном составе.
Голые четверки
Следующее расширение голых групп – голые четверки.
Числа , , , образуют голую четверку из четырех чисел 2, 5, 6 и 7, расположенных в четырех клетках. Эта четверка расположена в одном квадрате, это значит, что все числа 2, 5, 6, 7 из оставшихся клеток квадрата (оранжевые) удаляются.
Скрытые пары
Следующая вариация групп – скрытые группы. Рассмотрим пример:
В самой верхней строке числа 6 и 9 расположены только в двух клетках, в других клетках этой строки таких чисел нет. И если в одной из зеленых клеток поставить другое число (например 1), то в строке не останется места для одного из чисел: 6 или 9, значит нужно удалить все числа в зеленых клетках, кроме 6 и 9.
В итоге, после удаления лишнего, должна остаться только голая пара чисел.
Скрытые тройки
Аналогично скрытым парам – 3 числа стоять в 3-х клетках квадрата, строки или столбца и только в этих трех клетках. В этих же клетках могут быть другие числа – они удаляются
В примере скрываются числа 4, 8 и 9. В других клетках столбца этих чисел нет – значит удаляем лишних кандидатов из зеленых клеток.
Скрытые четверки
Аналогично со скрытыми тройками, только 4 числа в 4-х клетках.
В примере четыре числа 2, 3, 8, 9 в четырех клетках (зеленые) одного столбца образуют скрытую четверку, так как в других клетках столбца (оранжевые) нет этих чисел. Удаляются лишние кандидаты из зеленых клеток.
На этом закончим рассмотрение групп чисел. Для тренировки попробуйте решить следующие кроссворды (без подбора): Судоку № 13091 , Судоку № 10710
X-wing и рыба меч
Эти странные слова – названия двух похожих способа исключения кандидатов в судоку.
X-wing
X-wing рассматривается для кандидатов одного числа, рассмотрим 3:
В двух строках (синие) расположены всего 2 тройки и эти тройки лежат всего на двух линиях. Данная комбинация имеет всего 2 решения по тройкам, а другие тройки в оранжевых столбцах противоречат этому решению (проверьте, почему), значит красные кандидаты на тройки должны быть удалены.
Аналогично для кандидатов на 2 и столбцов.
По факту X-wing встречается довольно часто, но не так часто встреча с этой ситуацией сулит исключение лишних чисел.
Это усложненная вариация X-wing для трех строк или столбцов:
Рассматриваем так же 1 число, в примере это 3. 3 столбца (синие) содержат тройки, которые принадлежат к одним и тем же трем рядам.
Числа могут содержаться не во всех клетках, но нам важно пересечение трех горизонтальных и трех вертикальных линий. Либо по вертикали, либо по горизонтали должны отсутствовать числа во всех клетках, кроме зеленых, в примере это вертикаль – столбцы. Тогда все лишние числа в строках должны быть убраны, чтобы 3 остались только на пересечениях линий – в зеленых клетках.
Дополнительная аналитика
Взаимосвязь скрытых и голых групп.
А так же ответ на вопрос: почему не ищут скрытые/голые пятерки, шестерки итд?
Давайте рассмотрим следующие 2 примера:
Это один судоку, где рассматривается один числовой столбец. 2 числа 4 (отмечены красным) исключаются 2 разными способами – при помощи скрытой пары или при помощи голой пары.
Следующий пример:
Другой судоку, где в одном квадрате одновременно голая пара и скрытая тройка, которые удаляют одни и те же числа.
Если вы присмотритесь в примеры голых и скрытых групп в предыдущих параграфах, то заметите, что при 4-х свободных клетках с голой группой оставшиеся 2 клетки обязательно будут голой парой. При 8-и свободных клетках и голой четверке – оставшиеся 4 клетки будут скрытой четверкой:
Если рассмотреть взаимосвязь голых и скрытых групп, то можно выяснить, что при наличии голой группы в оставшихся клетках обязательно будет скрытая группа и наоборот.
И из этого можно сделать вывод, что если у нас свободны 9 клеток в строке, и среди них точно есть голая шестерка – то проще будет найти скрытую тройку, чем выискивать взаимосвязь между 6-ю клетками. Так же со скрытой и голой пятеркой – легче отыскать голую/скрытую четверку, поэтому пятерки даже не ищутся.
И еще один вывод – искать группы чисел имеет смысл только при наличии хотя бы восьми свободных клеток в квадрате, строке или столбце, при меньшем количестве клеток можно ограничиться скрытыми и голыми тройками. А при пяти свободных клетках и меньше можно не искать тройки – двоек будет достаточно.
Заключительное слово
Здесь приведены самые известные методы разрешения судоку, но при решении сложных судоку далеко не всегда применение этих методов ведет к полному решению. В любом случае метод подбора всегда придет на помощь – сохраняете судоку в тупиковом месте, подставляете любое доступное число и пытаетесь решить головоломку. Если эта подстановка приводит вас к невозможной ситуации, то значит, что нужно загрузиться и убрать подставленное число из кандидатов.
Проверьте, нет ли на поле больших квадратов с одной отсутствующей цифрой. Проверьте каждый большой квадрат и посмотрите, нет ли среди них такого, в котором отсутствует всего одна цифра. Если такой квадрат есть, его будет легко заполнить. Просто определите, какой из цифр от единицы до девятки в нем не хватает.
- Например, в квадрате могут присутствовать цифры от одного до трех и от пяти до девяти. В таком случае там отсутствует четверка, которую и требуется вставить в пустую ячейку.
Проверьте, нет ли рядов и колонок, в которых отсутствует всего одна цифра. Пройдитесь по всем рядам и колонкам головоломки, чтобы выяснить, нет ли случаев отсутствия всего одной цифры. Если такой ряд или колонка есть, определите, какой цифры из ряда от одного до девяти не хватает, и впишите ее в пустую ячейку.
- Если в колонке цифр стоят числа от одного до семи и девятка, то становится ясно, что не хватает восьмерки, которую и требуется вписать.
Внимательно просмотрите ряды или колонки, чтобы заполнить недостающими цифрами крупные квадраты. Посмотрите на ряд из трех крупных квадратов. Проверьте его на наличие двух повторяющихся цифр в разных больших квадратах. Проведите пальцем по рядам, в которых содержатся эти цифры. В третьем крупном квадрате также должна присутствовать эта цифра, но она не может располагаться в тех же двух рядах, которые вы проследили пальцем. Она должна располагаться в третьем ряду. Иногда две ячейки из трех в этом ряду квадрата будут уже заполнены цифрами и вам будет легко вписать на свое место ту цифру, которую вы проверяли.
- Если в двух больших квадратах ряда присутствует восьмерка, ее необходимо проверить в третьем квадрате. Проведите пальцем по рядам с присутствующими двумя восьмерками, так как в этих рядах в третьем большом квадрате восьмерка стоять не может.
Дополнительно просмотрите поле головоломки в другом направлении. Как только поймете принцип просмотра рядов или колонок головоломки, добавьте к нему просмотр в другом направлении. Используйте вышеуказанный принцип просмотра с небольшим дополнением. Возможно, когда вы доберетесь до третьего большого квадрата, в рассматриваемом ряду будет присутствовать лишь одна готовая цифра и две пустые ячейки.
- В таком случае необходимо будет проверить колонки цифр над и под пустыми ячейками. Посмотрите, нет ли в одной из колонок той же цифры, которую вы собираетесь поставить. Если вы нашли эту цифру, вам нельзя ставить ее в ту колонку, где она уже есть, поэтому ее нужно вписать в другую пустую ячейку.
Работайте сразу с группами цифр. Другими словами, если вы заметите много одинаковых цифр на поле, они могут помочь вам заполнить остальные квадраты этими же цифрами. Например, на поле головоломки может присутствовать много пятерок. Используйте вышеуказанную технику просмотра поля, чтобы заполнить его оставшимися пятерками, насколько это возможно.
ВКонтакте 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.
