Опробовав несколько собственных подходов в решении задач судоку, в том числе "самой сложной в мире" таблицы судоку Арто Инкала, я, дабы продвинуться дальше в этом же направлении, решил попытаться ознакомиться с тем, как развязывает подобные проблемы ученый мир.
Применяемый порой подход решения судоку с привлечением для этой цели булевой алгебры меня не воодушевил. Попробовал кое-что в этой части на детском варианте судоку (4 квадрата по 4х4), получилось нечто нудное и громоздкое. Правда, булева алгебра в судоку там, где я о ней прочел, использовалась не вручную, а в машинном варианте: здесь может быть она и к месту.
На форумах в интернете встретил сообщение одного из участников форума о том, что теория групп абстрактной алгебры позволяет в некоторых случаях продвинуться там, где до этого решение задачи судоку мог продолжить лишь чисто переборный вариант: "метод тыка" или выбор наугад. Другой участник форума подтвердил, что группы Ли могут обеспечить в судоку некоторый прогресс, но лично для него судоку до лампочки, так как у него есть иное занятие: переложить ОТО на группы Ли. ОТО, насколько я знаю, это или отдел технического обслуживания, или общая теория относительности Альберта Эйнштейна. Подозреваю, что имеется в виду последнее и что переложение ОТО на группы Ли может быть интереснее, чем подобное переложение для судоку. Но в том, что избранное форумчанином занятие полезнее, чем времяпрепровождение с судоку, я как-то твердо не уверен. Мне бы больше импонировало, если бы этот достойный участник форума взялся переложить ОТО на язык реальности, заодно очистив ОТО от мистических компонентов.
Ну а поскольку с Ли я лично не знаком, то решил как-то все же продвинуться в решении задачи Арто Инкала без советов уважаемого Ли.
Задача Инкала после предварительной обработки рабочей таблицы (пустые клетки заполняются числами 123456789 затем удаляются лишние цифры) с обычным незатейливым подходом имеет следующий вид:
В черном цвете представлены цифры исходной задачи, а синим цветом выделены цифры, полученные в результате традиционной ее обработки.
Далее я обратил внимание на то, что три пары цифр в рабочей таблице переходят от блока ("квадратика") к блоку, двигаясь синхронно по строкам или столбцам, а остальная тройка цифр переходит от блока к блоку, двигаясь в противоположном направлении. Это перемещение я назвал вращением цифр. Анализируя в этом плане таблицу, я выяснил, что цифры 6 и 7 в четвертом (левом среднем) блоке рабочей таблицы не могут асинхронно переходить в первый или седьмой блоки, так как в этом случае эти цифры попадали бы в средний столбец указанных блоков, что, как видно по таблице, не допустимо.
Продолжив этот анализ, я аналогичным образом выяснил, что цифры 7 и 4 могут вращаться лишь синхронно, откуда следует, что в нижней левой ячейке четвертого блока (это ниже цифры 4) может находиться лишь эксклюзивная (единичная) цифра 7. После дальнейшей обычной обработки таблицы с учетом данной дополнительно выявленной цифры приходим к следующей ситуации:
Но здесь я уже застопорился: Ли рядом не было, а сам я не смог выявить еще хотя бы один подобный вариант с выявлением эксклюзивных цифр. Да сильно и не старался – непростое это занятие: разбираться как может перемещаться каждая из цифр.
Далее я решил обратиться к сведениям, любезно предоставленным Александром Федоровым
http://www.km.ru/science-tech/2012/10/19/issledovaniya-rossiiskikh-i-zarubezhnykh-uchenykh/695292-matematiki-pridumal
в статье " Математики придумали формулу для решения cудоку ".
Оказывается, что исследователи комплексных сетей Золтан Торожкай и Мария Эркси-Раваз из Университета Нотр-Дама смогли найти новый подход к решению задач судоку. Единственный недостаток его лишь в том, что для того, чтобы понять, что они предлагают, нужна степень доктора математики.
Торожкай и Эркси-Раваз, как сообщает Федоров, предложили универсальный аналоговый алгоритм, который абсолютно детерминирован (не использует предположение или перебор) и всегда находит правильное решение задачи, причем довольно быстро. И далее:
«Я не интересовался судоку, пока мы не начали работать над более общим классом выполнимости Булевых проблем, – говорит Торожкай. – Так как судоку – часть этого класса, латинский квадрат 9-го порядка оказался для нас хорошим полем для испытаний, так я с ними и познакомился. Меня и многих исследователей, изучающих такие проблемы, захватывает вопрос, как далеко мы, люди, способны зайти в решении судоку, детерминировано, без перебора, который является выбором наугад, и, если догадка не верна, нужно вернуться на шаг или на несколько шагов назад и начать сначала. Наша аналоговая модель решения детерминирована: в динамике нет никакого случайного выбора или возвращения.
... У моей жены и у меня есть несколько приложений судоку на наших iPhone, и мы, должно быть, сыграли уже тысячи раз, соревнуясь за меньшее время на каждом уровне, – говорит он. – Она часто интуитивно видит комбинации паттернов, которых я не замечаю. Я должен их выводить. Для меня становится невозможным решить многие головоломки, которые наша шкала категоризирует как трудные или очень трудные, без того, чтобы записывать вероятности карандашом».
Торожкай и Эркси-Раваз полагают, что их аналоговый алгоритм потенциально подходит для применения к решению большого количества разнообразных задач и проблем в промышленности, информатике и вычислительной биологии.
Согласно Википедии, паттерн (англ. pattern — образец, шаблон, система) — закономерная регулярность, встречающаяся в природе и в человеческом дизайне, а также повторяющийся шаблон, образец. Элементы паттерна предсказуемо повторяются.
Мысль о паттернах или чем-то подобном высказывалась не единожды и в моих статьях. Например, я говорил о том, что опытный следопыт не разгадывает каждый отпечаток в серии запутанных следов, а попросту их читает. А вот вероятности в контексте вышесказанного меня несколько смущают. Там, где вероятности, там и случайности, а где случайности – там и возможность неудач. Так что это уже никак не полный детерминизм при всех его паттернах и т.п. Скажем, идем по улице и вдруг мгновенно узнаем в лице прохожего своего знакомого. Это потому, что где-то у нас зафиксирован его паттерн. Однако ошибка все же и здесь возможна. Так, влюбленный видит свой актуальный объект едва ли не в каждой случайной встречной (мне тоже доводилось быть молодым).
Но так или иначе, а идея с паттернами – хороша идея и попробуем ее применить. Правда, мы не располагаем женой Торожкая, которая указала бы нам паттерны, так что придется каким-то образом поэксплуатировать собственную интуицию.
Паттерн, как я понимаю, это некий образ, который следует расположить в собственном воображении, чтобы затем наложить его, как кальку, на исследуемый объект и распознать, что этот объект собой представляем или может представлять с точки зрения его применимости к решаемой задаче.
Итак, вернемся к нашей задаче, вернее задаче Инкала, и построим паттерны, например, для цифры 5.
Старт начинается с ячейки B6, где предполагается разместить единственную цифру 5, почему она и выделена красным цветом. Ячейка B6 с цифрой 5 распространяет свое воздействие на ячейки, выделенные желтым цветом, поэтому эта цифра потенциально исчезает в ячейках A5 B89 (B8 и B9), а также в I6. Но, дойдя до I6, мы должны мысленно остановиться по двум причинам. Во-первых, когда уберем цифру 5 в ячейке I6, то в ячейку H5 нужно будет записать эксклюзивную (единственную) цифру 5, так как другой ячейки с цифрой 5 в шестом блоке не остается. Во-вторых, мы обязательно должны обратить внимание, что когда выполняем действие H5-5 (т.е. в H5 помещаем эксклюзивную цифру 5), то при этом в ячейке H5 уничтожаются цифры 4 и 9. По этой причине в шестом блоке цифры 4 и/или 6 могут, в свою очередь, тоже оказаться эксклюзивными, что следует проверить непременно во избежание в дальнейшем ошибок или излишних неэффективных шагов в обработке таблицы. Аналогичным образом, означенные цифры могут оказаться эксклюзивными в строке и/или столбце, которым принадлежит ячейка H5. Но в данном случае новых эксклюзивных цифр не объявилось, а H5-5 продолжило свое действие на H9, на чем воздействие ячейки B6 в цепочке паттерна и прекратилось. На другие соседние желтым ячейки, выделенные бледно голубым цветом, описанное воздействие не распространилось.
Надеюсь, главную идею изображения паттерна вы поняли, а далее, с вашего позволения, я буду выражаться более лаконично. Итак, мы имели дело с паттерном B6=5 и далее переходим к паттерну A5=5 – другому паттерну со стартовой цифрой 5 в ячейке A5:
Ячейке A5 распространяет свое непосредственное воздействие на ячейки, выделенные желтым цветом, оставляя эксклюзивные пятерки в ячейках I6, H9 и заканчивая его на ячейке B8, где также останется эксклюзивная цифра 5 в седьмом блоке таблицы. Эти результаты, в дополнение или в качестве расширения для нашего осмысливаемого паттерна можно записать как I6-5, H9-5 и B8-5.
Но кроме непосредственного воздействия, выбор пятерки в качестве единственной цифры для A5 имеет и опосредствованное воздействие на ячейки таблицы, расширяя таким образом паттерн A5=5. Это опосредствованное воздействие начинается с ячейки B6=9, где пятерка удалилась в результате выбора A5=5. Опосредствованный паттерн B6=9, являющийся частью паттерна A5=5, выделен зеленым цветом.
На данном этапе рассмотрения варианты B6=5 и A5=5 представляются как равновероятные кандидаты на получение конечного положительного результата решения судоку Инкала. Но паттерн A5=5 гораздо мощнее своего собрата, он обещает удаление из ячеек большего количества лишних цифр и, соответственно, более быструю развязку с приходом либо к положительному, либо к отрицательному результату для данного варианта. Но даже отрицательный результат здесь дал бы полезную информацию и старт для правильного паттерна B6=5.
Если бы я раскручивал паттерны с пятерками, то выбрал бы вариант A5=5, хотя в конечном итоге и пришел бы к отрицательному результату. Но я, отыскивая новые подходы к проблемам судоку, и не собирался начинать с этого варианта. Меня в большей мере привлекает ячейка B6. О ней я достоверно знаю, что входящая в нее неизвестная единственная цифра "двигается" асинхронно паре 4 и 7, о которой уже говорил выше. А достоверной информацией грех не воспользоваться: будь Ли рядом, он наверное мне тоже бы этого не простил. Ну и кроме этого, варианты с B6 автоматически включают в себя и паттерны пятерок.
Итак, есть три варианта асинхронного движения 2 или 5 или 9, предположительно присутствующих в B6. Самый мощный из этих трех паттернов – B6=2.
Он имеет два собственных паттерна, выделенных желтым и бирюзовым цветами. Желтый – это обычный вариант, как и демонстрировавшийся для пятерок, а бирюзовый вариант возникает в связи с тем, что цифра 2 не может находиться в колонке B – там, где есть цифра 4, – иначе ее вращение было бы синхронным с парой 4 и 7. Таким образом, цифра 2 в первом блоке может разместиться лишь в ячейке C3, что дает старт паттерну C3=2. В целом, паттерн B6=2 включает в себя также целый ряд опосредованных (косвенных, производных) паттернов, стартовые ячейки которых выделены зеленым цветом, а стартовые цифры – лиловым цветом. Так что этот развитый паттерн обещает быструю развязку в смысле последующего завершения выбранного варианта положительным или отрицательным итогом. А результат применения паттерна B6=2 к обрабатываемой таблице выглядит так:
Теперь мы имеем дело с уже значительно упрощенной таблицей, которую несложно довести до дальнейшей полной развязки варианта B6=2.
Далее можно обратить внимание на то, что в первом блоке для цифры 1 возможны лишь два варианта – нахождение ее в A1 или С2. Паттерн C2=1 очень короткий (вы это можете легко проверить), и мы снова отдаем предпочтение гораздо более мощному паттерну A1=2: ну не я же виноват в том, что профессор Арто Инкала оставил в своей таблице столь "разорительные" для нее паттерны. Итак:
Непосредственный паттерн, ячейки которого выделены желтым цветом, заканчивается результатом C9-1. В ячейках B8 и B9, выделенных зеленым цветом, и только в них в пределах блока 7, может находиться цифра 8 (выделена лиловым цветом), которая воздействует на B4=89 и обеспечивает результат B4-9, дающий старт новому паттерну с цифрой 9, что в совокупности применения паттернов приводит к еще большему упрощению таблицы:
Здесь я обращаю ваше благосклонное внимание на то, что цифры 7 и 3 таблицы перемещаются синхронно в пределах 4-й, 5-й и 6-й строк, а та цифра, что в ячейке D5 (это либо 4, либо 9), должна перемещаться асинхронно этой паре. Паттерны D5=4 и D5=9 выглядят равными по своей мощности, но цифра 4 идет впереди 9 и я, не мудрствуя лукаво, выбираю первый паттерн. В результате его применения, через небольшое количество шагов приходим к решению задачи Арто Инкала:
Вариант D5=9 тоже приводит к быстрой развязке примерно за такое же количество шагов, как в предыдущем варианте:
В трех нижних строках таблицы появились недопустимые повторения цифр 2, 6 и 4 – они выделены коричневым цветом.
Но главное, что мне хотелось бы здесь сказать, - давайте учиться работать с паттернами, отрабатывать и запоминать их, и тогда мы сможем, надеюсь, быстро распознавать свои проблемы и способы их решения в лицо. Правда, о свободном, не шаблонном поиске тоже не надо забывать: такова уж диалектика решения проблем.
P.S. Сравнивая последние две таблицы, я вижу совпадение цифр в ячейках H7, F8, а также I6, G2, F6, D2, E8. Эти совпадения не случайны и говорят о том, что они были уже предопределены еще до выбора D5=4. То, что в H7 и F8 должна быть 1 - это моя оплошность: не заметил единственную единицу в столбце H. Цифра 6 не может вращаться синхронно в одном ряду с 4, а 4 - с 1: остается синхронная пара 6,1 и т.п. Если бы я определил в упомянутых ячейках хотя бы часть из цифр по их вращениям (перемещениям по столбцам), то задача была бы решена еще при выборе A1=1. А будь я поискуснее с этим вращением, то может быть и раньше.
И действительно, стоит лишь, еще при выборе A5=2 (до выбора A1=1), заметить, что 6 и 1 в столбцах G,H,I вращаются синхронно, а 2 - им асинхронно, то определяются несколько полезных цифр, а далее таблица "рассыпается" в процессе уже обычной обработки и завершается решением задачи. Однако... на сегодня поставим на этом точку.
20.10.2015 Ваш Протасов Н.Г.