Вероятности в решении проблем – супер сложные судоку

Вероятности – это непременный элемент в решении любых проблем, не поддающихся точному расчету. Задача Арто Инкала "самая сложная" среди задач судоку являет собой в этом отношении подходящий пример. Есть даже супер научный алгоритм, якобы позволяющий посредством расчета вероятностей однозначно и без перебора (без проб и ошибок) решать самые сложные задачи сверх судоку.

 

У меня такого алгоритма нет, но все же попробую что-то представить по части возможности решения задачи Арто Инкала, не прибегая к картам таро, помощи экстрасенсов и даже к такому многократно проверенному в России методу, как гадание на кофейной гуще.

 

В предыдущей статье мы начали с того, что, обрабатывая таблицу Арто Инкала обычными способами, мы довели ее до состояния:

 

 

Затем нам удалось эту таблицу еще раз дополнительно упростить, решив правдоподобным образом, что цифры 7 и 4 в первом, четвертом и седьмом блоках (три левых блока 9х9) должны переходить из столбца в столбец синхронно:

 

 

Для последующего рассмотрения задачи переведем эту рабочую таблицу в более удобный для ее изучения формат:

 

 

Мы видим, что какие-то цифры в ячейках встречаются чаще, какие-то – реже. Вероятности можно оценивать по-разному, но все же, если какая-то цифра встречается сразу в нескольких ячейках, то вероятность нахождения ее в некоторой конкретной, интересующей нас ячейке уменьшается. Я специально это проверял и в большинстве, хотя и не во всех, случаях так и бывает. А нас могли бы, например, заинтересовать ячейки 4-го (среднего левого) блока. Цифр там относительно немного и неплохо бы попытаться их еще раз разредить, чтобы приблизиться к конечному решению. Скажем, попытаемся ответить на вопрос вероятного нахождения цифры 2 в упомянутом блоке. С равной вероятностью эта цифра может находиться в верхней и в средней строке блока, но в средней строке эта цифра занимает две позиции, против одной – в верхней. Получается два шанса против одного, что цифра 2 находится в средней строке и не находится в верхней. Точнее, или более по научному, можем сказать, что эта цифра не находится в верхней строке блока с большей вероятностью, против вероятности ей там находиться. Придя к такому вероятностному заключению, мы "запрещаем" цифре 2 находиться в ячейке B4, что, с вашего позволения, запишем кратко в символьном виде:

  B4/2

Это действие B4/2 приводит к ситуации B4=89 и E4=89, а далее к целому ряду изменений в рабочей таблице в результате ее обработки обычными, традиционными способами, о которых можно прочесть в интернете или в моих предыдущих статьях. Итак, B4/2:

 

 

Теперь мы не с меньшим вожделением обращаем свой взор на цифру 8 в 7-м блоке таблицы. Она есть в двух ячейках среднего столбца этого блока и лишь в одной ячейке правого столбца. Так что вероятность нахождения ее здесь меньше, чем в среднем столбце, и мы, со спокойной душой, совершаем новую экзекуцию C9/8, результат которой после обычной дальнейшей обработки имеет достаточно впечатлительный вид. Итак, C9/8:

 

 

Здесь надо обратить внимание на описанный в моих предыдущих статьях момент относительно перемещения цифр в таблице Инкала: три пары цифр перемещаются синхронно в строках или столбцах таблицы, а остальная тройка цифр – асинхронно, т.е. противоположно направлению движения синхронных пар. По этой причине цифры 7 и 4 "вращаются" синхронной парой, а цифра 2 – асинхронно им: см. ячейки A4=4, A6=7 и A5=2. В результате асинхронного вращения цифры 2 она попадает в единственно возможную для нее позицию C3=2 в первом блоке. Подобный принцип асинхронного вращения применяется в большинстве сложных задач судоку. Теперь, после подстановки C3=2 и дальнейшей обычной обработки таблицы, приводим ее к виду:

 

 

Здесь и далее, можно подойти к решению задачи, исходя из таких вероятностно оценочных соображений: цифра 4 занимает две позиции в нижней строке 9-блока и лишь одну – в его левом столбце, где ее нахождение, соответственно, менее вероятно. Плюс к этому, по аналогичным вероятностным соображениям, эта цифра должна находиться в левом столбце 6-го блока. Оба эти вероятностные соображения приводят к действию G7/4 и, соответственно, к быстрому окончанию решения задачи Арто Инкала.

 

Конечно, в части оценки вероятностей мы действовали не столь изощренно, как Золтан Торожкай из Университета Нотр-Дама, придумавший свой метод детерминированной вероятности вместе с собственной супругой Марией Эркси-Раваз, который при решении задач судоку вычислял, машинным способом или карандашиком, вероятности успешных ходов. Но главное для нас, все же, - понимание идеи учета вероятностей в решении встречающихся в жизни проблем, а не только лишь частный случай их решения в среде судоку.

 

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

 

Список и краткий обзор статей, касающихся судоку

Copyright © 2009 - 2022 Алгоритмист | Правовая информация
Сделано в JustCreative | Карта сайта
Яндекс.Метрика