Трое математиков из Ирландии выяснили, что головоломка
Правила судоку, популярность которой начала быстро расти в восьмидесятых годах, известны, наверное, всем читателям «КЛ». Напомним лишь о том, что валидная головоломка этого типа по определению имеет уникальное решение; другими словами, подсказки должны быть размещены таким образом, чтобы каждой из оставшихся клеток поля стандартного размера (9×9) соответствовала только одна цифра, а любая попытка поменять внесённые игроком цифры местами давала бы неверную комбинацию.
Судоку, которые публикуются в прессе, обычно содержат около 25 подсказок. Поскольку такие головоломки намеренно делают не слишком сложными, это число далеко от минимально необходимого: сейчас известно уже около 50 000 отвечающих правилам судоку числовых сеток 9×9, которые можно преобразовать в одну или несколько головоломок с семнадцатью подсказками. Однако ни одной конфигурации с 16 стартовыми цифрами найдено не было, и математики предполагали, что любая такая головоломка будет иметь как минимум два решения.
Один из множества примеров судоку с 17 подсказками и уникальным решением (иллюстрация с сайта Sudoku-solutions.Com). |
Чтобы доказать это гипотезу, ирландцы постарались проверить все 6 670 903 752 021 072 936 960 (≈6,7•1021) возможных вариантов заполненных судоку. Никакой необходимости тщательно исследовать каждый, разумеется, нет, так как многие варианты эквивалентны друг другу; выполнив необходимые расчёты, авторы сократили количество числовых сеток до 5 472 730 538. Каждую из них анализировала написанная учёными программа Checker, искавшая головоломки с 16 подсказками, единственным решением которых была бы проверяемая сетка.
Checker запускали на суперкомпьютере, установленном в
Отчёт о своих вычислениях математики