В предыдущих статьях мы рассматривали разные подходы в решении проблем на примерах головоломок судоку. Пришло время попытаться, в свою очередь, проиллюстрировать возможности рассмотренных подходов на достаточно сложном примере решения проблем. Итак, сегодня мы приступим к самому "невероятному" варианту судоку. Терминологию и предварительные сведения вы, уж будьте так любезны, посмотрите в предыдущих моих статьях, касающихся судоку, иначе вам трудно будет понять содержание данной статьи.
Вот какие сведения я нашел об этом сверхсложном варианте в интернете:
Профессор Хельсинского университета Арто Инкала (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, что также приводит к быстрой развязке задачи.
Надо сказать, что задача Арто Инкала не допускает чисто логического решения в рамках возможностей обычного человека – так она задумана, – но все же позволяет заметить некоторые перспективные варианты перебора возможных подстановок цифр и существенно сократить этот перебор. Попробуйте начать перебор с иных, чем в данной статье, позиций, и вы, убедитесь, что почти все варианты очень быстро заводят в тупик и требуется делать все новые и новые предположения относительно дальнейшего выбора подходящих подстановок цифр. Месяца два назад я уже пытался решить эту задачу, не имея той подготовки, которую я описал в предыдущих статьях. Проверил вариантов десять ее решения и оставил дальнейшие попытки. Последний же раз, уже будучи более подготовленным, я решал эту задачу полдня или немного более, но при этом с одновременным обдумыванием выбора с моей точки зрения наиболее показательных для читателей вариантов и также с предварительным обдумыванием текста будущей статьи. А окончательный результат решения получился следующий:
Собственно, данная статья не имеет самостоятельного значения, она написана лишь для иллюстрации того, как приобретенные навыки и теоретические соображения, описанные в предыдущих статьях, позволяют решать довольно сложные проблемы. А статьи были, напомню, не о судоку, а о механизмах решения проблем на примере судоку. Предметы, как по мне, совершенно разные. Однако поскольку судоку интересует многих, то я таким образом решил привлечь внимание к более существенному вопросу, касающемуся не собственно судоку, но решения проблем.
А в остальном – желаю вам успехов в решении всех проблем.