10 января 2012 года, 21:53 | Текст: Дмитрий Сафин

Трое математиков из Ирландии выяснили, что головоломка судоку должна иметь не менее 17 подсказок — цифр, предварительно расставленных на игровом поле.

Правила судоку, популярность которой начала быстро расти в восьмидесятых годах прошлого века, известны, вероятно, всем читателям «КЛ». Стоит напомнить лишь о том, что валидная головоломка этого типа по определению имеет уникальное решение; другими словами, подсказки должны быть размещены таким образом, чтобы каждой из оставшихся клеток поля стандартного размера (9x9) соответствовала только одна цифра, а любая попытка поменять внесённые игроком цифры местами давала бы неверную комбинацию.

Судоку, которые появляются в самых разных газетах и журналах, обычно содержат около 25 подсказок. Поскольку такие головоломки намеренно делают не слишком сложными, это число далеко от минимально необходимого: в настоящее время известно уже около 50 000 отвечающих правилам судоку числовых сеток 9x9, которые можно преобразовать в одну или несколько головоломок с семнадцатью подсказками. Ни одной конфигурации с 16 стартовыми цифрами, однако, найдено не было, и математики предполагали, что любая такая головоломка будет иметь как минимум два решения.

Один из множества примеров судоку с 17 подсказками и уникальным решением (иллюстрация с сайта Sudoku-solutions.Com).

Чтобы доказать это гипотезу, ирландцы постарались проверить все 6 670 903 752 021 072 936 960 ( 6,7•1021) возможных вариантов заполненных судоку. Никакой необходимости тщательно исследовать каждый из них, разумеется, нет, так как многие варианты эквивалентны друг другу; выполнив необходимые расчёты, авторы сократили количество числовых сеток до 5 472 730 538. Каждую из них анализировала написанная учёными программа Checker, искавшая головоломки с 16 подсказками, единственным решением которых была бы проверяемая сетка.

Checker запускали на суперкомпьютере, установленном в Ирландском центре высокопроизводительных вычислений и оснащённом 640 шестиядерными процессорами Intel Xeon X5650. Расчёты стартовали год назад и завершились в декабре 2011-го, и за всё это время программа так и не обнаружила ни одной валидной головоломки с шестнадцатью подсказками.

Отчёт о своих вычислениях математики опубликовали девять дней назад. Никаких серьёзных ошибок в нём пока не нашли, и приведённое авторами доказательство большинство их коллег считает верным.

Подготовлено по материалам Nature News.

Источник