Самая сложная судоку в мире – таковой не является?

Фото с сайта: techhive.com

В не столь давние времена автор этих строк, набрав в поисковой системе интернета первые три слова заголовка, получил массу интересных сведений, из которых он узнал, в частности, что сравнительно недавно профессор Хельсинского университета Арто Инкала опубликовал судоку, названную им AI Escargot. Характеризуя своё детище, профессор утверждает, что это самая сложная головоломка судоку в мире, и для её решения игроку придется держать в голове вместо одной-двух сразу восемь последовательностей одновременно. Памятуя о том, что любое утверждение имеет право на существование, пока не доказано обратное, и учитывая исторический прецедент-легенду о случае с Аристотелем, заявившим, что у мухи восемь ног, когда на самом деле их только шесть, посмотрим на профессорскую «улитку» (так переводится Escargot), приведенную на рис.1, повнимательней.



На первом этапе, назовём его «нулевым уровнем перебора вариантов решений», по правилам заполнения судоку однозначно определяются только два числа: B55 и E63. Здесь нотация хода решения состоит из буквы - обозначения строки, номера колонки и собственно значения числа в данной клетке. На рис.2 клетки с этими числами выделены синим цветом. В остальных незаполненных клетках указаны варианты возможных в них чисел. Для неискушенного читателя поясним: в случае, когда значения чисел в некоторых клетках судоку нельзя определить логическим путем, дальнейшее решение осуществляется определением и перебором вариантов чисел в любой выбранной решающим клетке. Для каждого выбранного числа из набора вариантов в данной клетке возможны три исхода. 1. Полное заполнение судоку, иначе говоря, её решение. 2. Фатальная ошибка – в процессе решения в какой-либо клетке нельзя проставить ни одно число – выбранное исходное число из набора заведомо неверно, и нужно продолжать решение с другим числом этого же набора. 3. Аналогичная исходной ситуация – после простановки однозначно определяемых чисел остаются пустые клетки с наборами вариантов – возникновение новой последовательности перебора вариантов при существующей предыдущей. Иными словами, более глубокий уровень перебора.

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

На рис.2 приведены варианты 1-го уровня перебора. Начиная с самого первого числа первого же набора в первой же клетке A11 (рис.3), сразу же получаем второй уровень (рис.4), в котором после сравнительно недолгого перебора при A67 получаем полное решение (рис.5):



Замечаем: мы получили полное решение уже на 2-м уровне перебора, то есть во второй последовательности. Не утомляя читателя обилием рисунков, с приличествующей данному моменту торжественностью и полной ответственностью за сказанное ниже, называю общее количество вариантов получения решения на 2-м уровне: 98 (!). Дабы не быть голословным, привожу их полный список:

A11A67, A11A89, A11B97, A24I48, A52D29, A52H28, A52I48, A67A76, A67B39, A67B71, A67D29, A67F59, A67F91, A67H28,

A67I31, A67I48, A76A89, A76B97, A76D87, A76E79, A76G54, A76I94, A89B39, A89B71, A89I31, A89I48, A98H28, A98I48, B23I48,

B39B97, B46G54, B46I48, B64D29, B64H28, B64I48, B71B97, B71E79, B97D29, B97F59, B97F91, B97H28, B97I31, B97I48, C16I48,

C32E79, C32I48, C49D29, C49E79, C49H28, C49I48, C68D29, C68H28, C68I48, C84D29, C84E79, C84F91, C84H28, C84I48, C93I48,

D29G62, D29I94, E12I94, E44H72, E44I22, E44I48, E79G62, E79G78, E79H56, E79H72, E79I48, E79I86, E85I94, F25I94, F59I48, F59I94,

F74H72, F74I22, F74I48, F91I48, F91I94, G13I48, G54H56, G54H72, G54I48, G54I86, G62H28, G62I48, G81I48, H28I94, H56I94, H72I94,

H95I94, I15I94, I22I48, I31I48, I48I53, I48I94, I86I94.

Естественно, практически у любого читателя возникает вполне закономерный вопрос: а как обстоят дела с другими уровнями перебора (количествами последовательностей)? Ответ: на прочих исследованных уровнях существуют сотни и тысячи вариантов получения решения (которое, следует отметить, действительно единственное, как и подобает полноценной судоку). Так как автор этих замечаний не ставил целью полномасштабный и исчерпывающий анализ «улитки», то он ограничился поиском первых нескольких сотен вариантов решения на каждом уровне вплоть до 14-го уровня включительно и, разумеется, просто обязан привести здесь хотя бы по одному варианту для каждого уровня. Нумерация (номер по порядку в ряду найденных вариантов решения) – авторская, но читатель может быть уверен: если указан вариант с порядковым номером, например, 107, то сто шесть предшествующих вариантов решения на данном уровне безусловно реально существуют, записаны на твёрдом носителе, хранятся в подходящем месте и могут быть немедленно предоставлены по первому требованию судокоинтересующейся общественности. Итак:

3-й ур.: 225. A24A52D29; 4-й: 114. A11A24C93I48; 5-й: 319. A11A24A52I31I48; 6-й: 303. A11A24A52A98H72I94;

7-й: 295. A11A24A52A98B23H72I31; 8-й: 254. A11A24A52A98B23B39I22I53; 9-й: 173. A11A24A52A98B23B39B64I22I53;

10-й: 148. A11A24A52A98B23B39B64C68I15I48; 11-й: 123. A11A24A52A98B23B39B64C68C84I22I53;

12-й: 107. A11A24A52A98B23B39B64C68C84E85I31I48; 13-й: 13. A11A24A52A98B23B39B64C68C84E38E44I31I48;

14-й: 1. A11A24A52A98B23B39B64C68C84E38E44H19I31I48.

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

Подведем итоги. В свете вышеприведенного заявленное уважаемым профессором минимальное число последовательностей 8 (восемь) не оказалось таковым: существует значительное количество вариантов решения с меньшими количествами последовательностей до 2-х включительно. Не оказалось оно и максимальным: можно прийти к решению и бо’льшими количествами последовательностей. И если не приравнивать сложность решения задачи (неважно какой!) к трудоёмкости её решения, и, в свою очередь, различать минимальную трудоёмкость от потенциальной, оказывается, что претендующая на звание «самая сложная головоломка судоку в мире» на самом деле является судоку со всего-навсего двумя последовательностями вариантов решений. И хотя, как показано выше, она имеет достаточно большое возможное количество последовательностей перебора – это пути заплутавших в поисках разгадывающих данную судоку индивидуумов, но отнюдь не достаточное условие её действительной сложности.

В чём и подписываюсь: Владимир Марциновский, автор первого 3D-Спейсворда (пространственного трёхмерного кроссворда со специализированной структурой).