Каждый индивид, как дознано наукой, говорит на своем языке, отображающем модели его внутреннего мира. Поэтому, если не договориться о смысле употребляемых слов, то может исчезнуть и предмет, о котором можно говорить. Ну например, "искривление пространства" в современных полумистических физических теориях. Словосочетание из знакомых слов есть, а смысла, пригодного для обсуждения какого-либо предмета, нет. Правда, если в этом покопаться, то оказывается, что искривление – это не искривление, и пространство – это не пространство, а нечто, имеющее совершенно посторонний смысл, против принятого в языке нормального общения. Вот так и с проблемой решения сверхсложных задач судоку. Возможно ли их аналитические решения: без перебора вариантов, без возвратов и допущений? Не найдя нигде удовлетворительного ответа, я решил сам его объяснить тем, кто взял на себя труд прочесть мои статьи - о судоку в частности, и об общих подходах в решении проблем.
Перебор вариантов, сразу скажу, можно сократить по мере знания структуры задачи. Так, большинство таблиц для сверхсложных задач судоку строится по следующему принципу: три пары цифр как бы движутся "вращаются" в одном направлении по строкам или столбцам, а остальная тройка цифр вращается асинхронно, т.е. противоположно вращению пар. Например, полная структура "самой сложной задачи судоку", созданной Арто Инкала, имеет следующий вид:
Слева структура таблицы, а справа внешний вид задачи. Если совместить структуру и собственно задачу – наложить ее как кальку на структуру, - то окажется, что решение находится автоматически, и не надо никакого перебора вариантов, потому что все иксы известны по результату совмещения структуры и задачи.
Теперь представим, что образ задачи, как она задана Арто Инкала, уже есть в памяти супермощного компьютере. Один миг, и задача будет решена, а уж считать это решение аналитическим или каким-то иным – это уже вопрос договоренности о том, что мы будем понимать под употребляемым сочетанием слов.
Правда, знаток может возразить, что по расчетам Б. Фельгенхауэра количество вариантов судоку составляет 6 670 903 752 021 072 936 960, поэтому подобное решение просто не возможно – не хватит компьютерных ресурсов. Ну что ж, подождем пару сотен лет, пока появятся компьютеры должной мощности, и задача описанным способом все равно будет решена.
Однако, оказывается, что для запоминания и распознания образа задачи вовсе не обязательно знать конкретику чисел. Достаточно знать лишь позиции иксов в задаче, а цифры можно подбирать любые в количестве 8*7*6*5*4*2*1 вариантов. Кроме того, можно делать разные другие эквивалентные преобразования задачи: менять местами строки, столбцы и т.п. Не знаю, все ли эти варианты учел Б. Фельгенхауэр, но "за вычетом разных групп симметрии" остается 2 297 902 829 591 040 вариантов судоку по его расчетам. Так что потребуется подождать даже не пару, а лишь одну сотен лет до появления компьютера должной мощности применительно к обсуждаемой проблеме решения задач.
Но ведь и в этом случае учтены не все ограничения. Если учесть специфическую структуру таблиц, применяемую для сверх сложных задач судоку, то количество возможных вариантов, приложимым к этим структурам, сократится еще эдак на миллиардик. Так что и сотню лет тоже ждать нам не обязательно.
Кроме того, оказывается, что и держать полные варианты задач в памяти компьютера тоже не обязательно. Достаточно хранить в памяти лишь ее куски: паттерны, как их называет супружеская пара исследователей комплексных сетей Золтан Торожкай и Мария Эркси-Раваз из Университета Нотр-Дама. Вот и представим, что эта пара нам любезно подсказала паттерн для задачи Арто Инкала, и посмотрим что из этого может получиться.
Рассмотрим рабочую таблицу задачи Арто Инкала:
Рабочая таблица, напомню, создается первоначальным заполнение всех пустых клеток числами 123456789 с последующим "вычеркиванием", т.е. удалением, из чисел лишних цифр. В этой таблице, как видим, есть две эксклюзивные цифры E2=5 и F5=3, которые выделены красным цветом и которые учтем в дальнейшей обработке таблиц.
Теперь о паттерне. Пусть мы здесь знаем лишь вращение по строкам 1, 2 и 3: (4+5), (8+9), (2+7), (1+3+6) – в скобках три пары цифр, вращающиеся синхронно, и асинхронная им тройка цифр. Причем, взаимное расположение цифр в строке нам даже не известно. Тогда, с учетом описанного порядка, имеем отвечающий ему новый вариант рабочей таблицы:
Красным цветом здесь снова выделены эксклюзивные цифры. Мы проставляем их в соответствующих им ячейках, по этим эксклюзивным цифрам совершаем "вычеркивание" лишних цифр из других ячеек, не выходя пока за пределы паттерна (трех верхних строк), и в результате "вычеркивания" получаем новые эксклюзивные цифры:
Снова оставляем лишь эксклюзивные цифры и получаем:
Далее мы обращаем внимание на тот, следующий из заданного паттерна, факт, что х2=4 движется (или вращается) по строкам в порядке 1,2,3: с первой строки на 2-ю, затем на 3-ю. Вычеркивая цифру 4 из не отвечающих этому вращению ячеек, получим:
Далее мы видим, что х8=7 и х9=? движутся синхронной парой по строкам в порядке 1,3,2 и единственный возможный вариант, в строках 3 и 2 отвечает лишь условию х9=2:
Теперь анализируем тот факт, что х7 движется по строкам в порядке 3,2,1, а х6 по строкам 2,3,1. Этому факту отвечает таблица:
Далее оставляем в ячейках эксклюзивные цифры, которые были выделены выше красным цветом, и получаем:
Теперь в паттерне остаются три варианта расположения 6 и 9, но дальнейшая обработка – уже всей таблицы – не сложна. После простого вычеркивания лишних цифр (с учетом вычеркивания – по ячейкам D2 и D3 – лишних цифр 6 и 9 из ячеек в столбце D) получаем:
Продолжаем вычеркивание по F5=3, H7=1 и далее по появившейся F7=2, при этом возникают все новые эксклюзивные цифры:
Повторяем операции, и аналогичным образом, путем самых простейших действий приходим к завершению задачи:
Но используемый паттерн, должен сказать, для умелого решателя может быть даже меньше того, что в приведенном выше примере. Пусть, скажем, нам известно движение по трем верхним строкам лишь тройки (1+3+6), о которой говорилось выше. Правильный учет этого вращения приведет нас к результату:
Далее мы видим, что B2=3 и C2=6 не совместимы в любом варианте вращения, поэтому оставляем C2=9; а также эксклюзив B1=4:
В итоге у нас остается единственный допустимый вариант (4+5), (8+9), (2+7) и (1+3+6), который уже рассматривали выше и который привел к решению задачи.
Теперь представим иной вариант: мы разложили три верхних строки рабочей таблицы на полное количество возможных вариантов. Их – разложений – окажется не столь уж много, как может показаться на первый взгляд. И среди них – наш паттерн (1+3+6). Далее представьте, что объем вашей оперативной памяти никак не меньше, чем у чемпиона мира по шахматам. Вы просматриваете все разложения и обнаруживаете вариант (1+3+6), приводящий к решению задачи. Вопрос: будет ли это решение задачи вариантом с перебором или нет? Ответ будет зависеть от нашей договоренности относительно того, что мы будем иметь в виду под переборным вариантом.
Но мы можем, аналогичным образом, обойтись и компьютерной памятью. Разлагаем ситуацию на все возможные варианты и далее проверяем последовательно каждый вариант на предмет его дальнейшей оценки в части перспективности для решения задачи. Получается, что какие-то варианты сразу же оказываются не совместимыми с любым возможным порядком вращения цифр. Другие – через некоторое количество шагов приводят к результату, противоречащему условию задачи. Третьи – завершаются тупиком, так как мы условились считать не допустимым выход из тупика посредством каких-либо допущений. Все это, повторюсь, делается для того, чтобы далее построить оценки перспективности для каждого из разложений. Это можно не считать перебором вариантов, если мы таким образом об этом договоримся. Но вот незадача: при некотором количестве разложений (а мы вольны сколько угодно увеличивать количество анализируемых вариантов) обязательно окажется не менее одного варианта, который уже в процессе "предварительной" его проверки приведет к решению задачи. Так как здесь считать: мы решили задачу переборным или не переборным путем? А если машина выбрала для нас из миллиона заготовок единственный подходящий паттерн с уже готовым решением задачи – как тогда считать?
Может быть договоримся о том, что проблема не в том, что считать переборным или не переборным вариантом, а в том, чтобы суметь достигнуть решения задачи с использованием минимума затраченных на это решение ресурсов? Любая проблема требует затраты каких-то ресурсов в некотором рациональном размере. По жизни это вроде бы и очевидно. Так что, может быть, и проблема решения задач судоку тоже должна рассматриваться в подобном же ключе.
Но проблема может лежать и в иной плоскости: найти формальные способы решения задач судоку, применимые для решения других задач. Я вот, тоже в своих статьях занимался в основном не проблемами собственно судоку, а общими подходами к решению проблем, используя для этого решение задач судоку как пример.
А еще: судоку есть хорошее средство для разминки мозгов, что, в свою очередь, является полезным средством для решения любых проблем.