Решение задач методом последовательных упрощений

О методе последовательных упрощений в решении задач я не однажды говорил в нескольких своих статьях данного подраздела. Суть его в том, чтобы находить в задаче отдельные подлежащие упрощению фрагменты и таким образом постепенно упрощать задачу всюду, где она позволяет себя упростить. Сегодня попробуем применить этот метод в такой непростой ситуации, как "самая трудная в мире" задача судоку, разработанная финским математиком Арто Инкала в 2012 году.

 

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

 

Однако меньше слов и ближе к делу. Перед нами вновь представлена рабочая таблица задачи Арто Инкала.

 

 

Черным и боле крупным шрифтом здесь выделены цифры-ключи, указанные в исходной задаче.

 

Рабочая таблица, еще раз напомню, составляется первоначальным заполнением пустых ячеек задачи числами 123456789 с последующим удалением, "вычеркиванием" лишних цифр. Рабочая таблица первоначально обрабатывается простыми, всем известными, "стандартными", средствами решения задач судоку.

 

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

 

Первый вопрос, который мы можем себе задать после уяснении описанного механизма и задачи: какой вид вращения мы имеем в наиболее разряженных и удобных для применения идеи вращения строках 4, 5 и 6 таблицы – парный или триплетный. Для триплетного подходит только триплет '(7+9+3), а для парного – только пара (7+3). Чтобы это понять, достаточно проанализировать ячейки A6, B6, C6 в шестой строке и возможную трансформацию входящих в эти ячейки цифр в строках 5 и 4. Главный вывод простой и очевидный для освоивших идею механизма вращения: в любом из этих альтернативных вариантов имеем один и тот же результат A6=7. Так что подставим этот результат в таблицу (примечание: в более строгом первоначальном варианте статьи эта подстановка была сделана после анализа и обработки столбцов GHI - см. ниже) и обработаем ее простым способом "по стандарту":

 

 

Аналогичным образом мы можем подойти к анализу столбцов GHI. Если в GHI есть триплет, то возможно предположить только триплет левого вращения '(7+4+8), но тогда не получаются еще два триплета левого вращения в GHI. То есть, в GHI триплетного вращения нет:

 

 

А левое вращение, отвечающее '(7+4+8), это переход этого триплета по ячейкам, выделенным желтым цветом, в направлении сверху-влево-вниз.

 

Теперь, обзаведясь некоторыми познаниями в части модели механизма вращения цифр и даже одним весьма упрощающим задачу результатом A6=7, можем приступить к более детальному анализу столбцов GHI. Еще раз смотрим таблицу с внесенным в нее результатом A6=7:

 

 

Цифра 3 может здесь двигаться только по правому вращению: сверху-вниз по столбцам IGH, сочетаясь последовательно с цифрами 14786, 1249 и 1456. В этих трех группах цифр совпадают только цифры 1 и 4, что мы запишем в символьном виде:

     3+R14786+R1249+R1456>3+R14

Аналогичным образом запишем возможные сочетания и для других цифр, используя L как символ левого вращения:

 

 

Запишем этот результат в более компактном виде:

 

        

 

7 и 8 не встречаются в правом вращении, т.е. не сочетаются как пара и одиночка, в то же время они встречаются только два раза в сочетаниях пар, где параобразующие 7 или 8. Так что (7+8) – пара левого, парного вращения. Подставим эту пару в таблицу соответственно левому вращению и обработаем ее обычным методом, "по стандарту":

 

 

Обратите внимание на то, что в 3-м блоке (верхнем, правом) образовалась "голая" четверка цифр 1469, занявшая 4 ячейки. Следовательно, таких цифр не должно быть в остальных ячейках блока. Вы, конечно, эти простые вещи знаете, но можно их случайно пропустить. Итак, продолжим обработку с учетом данной четверки:

 

 

Далее мы имеем следующую ситуацию. В строках 456 теперь уже не проходит триплет '(7+9+3), следовательно здесь не триплетное, а парное вращение: тройка пар и тройка одиночек, вращающихся в направлении, противоположном вращению пар.

 

В столбцах GHI цифра 5 либо одиночка (правое вращение), либо (5+1) левого вращения.

 

Пара (5+1) в GHI - не проходит по стандартной обработке, в чем вы можете достаточно просто убедиться при желании это проверить обработкой таблицы. Следовательно, в GHI цифра 5 – одиночка.

 

Пара (5+1) в столбцах DEF тоже не проходит по результатам стандартной обработки, следовательно 5 в DEF - одиночка, а 3, которая вращается противоположно 5, - параобразующая.

 

Тот факт что Е2=5 свидетельствует о том, что ее "соседка" Е3=1 - параобразующая левого, как и 3, вращения. Подставим эти левые вращения в столбцах DEF, а также одиночное вращение 5 в GHI в обрабатываемую обычным способом таблицу:

 

 

В блоке GHI теперь проявились три одиночки 2+3+5 и три пары (7+8)+(6+х1)+(9+х2), причем (х1+х2)=(1+4).

 

Если в строках 789 предположить триплет, то это только '(7+6+1), но он приводит к отрицательному результату при его подстановке и обработке таблицы стандартными средствами. Так что в строках 789 не триплеты, но есть проявленные пары (6+7) и (9+х).

 

В строках 123 также не получаются триплеты. Например, из тройки чисел 5+49+38 в G3, H3 и I3 допустимы только пара (5+4) или (5+9). При этом если подставим в таблицу пару (5+9), то получим быстрый отрицательный результат. Так что подставляем в строки 1, 2 и 3 пару (5+4), обрабатываем таблицу обычными средствами и получаем решение задачи:

 

 

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

 

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

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