ВОПРОС КЛЕТОК, ЦИФР, И ВСЕГО ТАКОГО |
|
Сколько цифр (минимум) должно присутствовать в сетке, чтобы самая сложная головоломка судоку имела однозначный ответ?
 Головоломка «судоку» представляет собой квадрат 9 на 9 клеток, разбитый на 9 квадратов поменьше, 3 на 3 клетки каждый.
Для её решения необходимо разместить цифры от 1 до 9 во всех клетках таким образом, чтобы в каждой строке, в каждом столбце и в каждом маленьком квадрате цифры встречались только однажды.
Математик Гери МакГвайр (Gary McGuire) сотоварищи доказал: судоку имеет единственное решение в том случае, когда задано минимум 17 цифр в различных клетках. При 16 (и меньше) исходных значениях возможно несколько вариантов расстановки. Обычно любителям переставлять цифры предлагаются головоломки с 25 и более исходными значениями.
На конференции в Бостоне математики посовещались и решили, что подход МакГвайра правомерен. Однако для полной проверки корректности доказательства понадобится немало времени - в первую очередь, машинного. Дело в том, что для доказательства математик использовал "брутфорс" - метод перебора. Конечно, перебрать все судоку с 16-ю исходными цифрами и доказать, что они имеют более одного решения - это нереально даже с использованием современных компьютеров, поэтому МакГвайр разработал алгоритм, использующий т.н. "неоспоримые множества" ("unavoidable sets") - последовательности цифр, присутствие которых однозначно свидетельствует о множественности решений данной головоломки. Использование этого алгоритма позволило существенно сократить число вариантов для перебора - но и в этом варианте для доказательства "теоремы судоку" потребовалось около 7 миллионов часов машинного времени.
Возможно, фанаты судоку оценят этот эпохальный труд. А сам МакГвайр признался, что больше любит кроссворды.
Ну а для тех, кто не прочь потратить несколько минут на не самую сложную головоломку - флеш-вариант судоку. Наслаждайтесь:
Добавлено: 09.01.12
|
Зарегистрируйтесь сейчас и получите 100 баллов себе на счет!
А разместив ссылку на этот материал Вы получите дополнительные баллы за каждый переход по ней.
Подробнее об условиях акции читайте в правилах.
|
|
| ИНТЕРЕСНЫЕ БЛОГИ |
|
|
|
ReadMe
1 2 След. »
|
МАГАЗИН ПМ
4
