Математики высчитали минимальное число подсказок в головоломке судоку

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

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

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

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

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

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