Математика
Википедия
Математика
Математикой называется наука о структурах, отношениях и порядке, которая исторически сложилась на основе совершаемых операций подсчета, описания и измерен... читать далее »
Новости Математики
11.01.2012 11:59

Установлено минимально возможное число подсказок в судоку. Математика.

Установлено минимально возможное число подсказок в судоку

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

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

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

Один из множества примеров судоку с 17 подсказками и уникальным решением (иллюстрация с сайта Sudoku-solutions.Com).
Один из множества примеров судоку с 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-го, и за всё это время программа так и не обнаружила ни одной валидной головоломки с шестнадцатью подсказками.

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


Источник

© WIKI.RU, 2008–2017 г. Все права защищены.