Все рубрики раздела
- Ученые обнаружили в человеческом мозге новый участок14:12
- У человечества есть лишь 20 лет: в ООН сказали о климатической катастрофе14:41
- Ученые нашли доказательства существования снежного человека08:01
- Ученые назвали самый плохой сценарий для Земли19:40
- Американские ученые предупредили о грядущей катастрофической жаре на планете21:43
- Ученый сделал сенсационное заявление о лекарствах18:48
- Через 10 лет мир ждет полный хаос: неутешительный прогноз ученых09:30
- Врачи объяснили, почему нельзя отказываться от завтрака08:00
- Огромная проблема для всего мира: ученые заявили о таянии крупного ледника в Антарктиде16:40
- Загадочная "воющая" аномалия на дне Тихого океана потрясла ученый мир 18:10
Ученые определили минимальное число подсказок в судоку
Трое математиков из Ирландии выяснили, что головоломка судоку должна иметь не менее 17 подсказок - цифр, предварительно расставленных на игровом поле
Как известно, головоломка судоку, популярность которой начала быстро расти в восьмидесятых годах, по определению имеет уникальное решение; другими словами, подсказки должны быть размещены таким образом, чтобы каждой из оставшихся клеток поля стандартного размера (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 каждая цифра встречалась бы только один раз.
По материалам: focus.ua
Теги: исследования, ученые, открытие, математика, головоломка, судоку
- За 11 мая россияне ранили 2 жителей Донетчины - ОВА13:00
- Оперативная информация Генштаба ВСУ о ситуации на Донбассе10:00
- ВСУ нанесли удар по месту празднования боевиков в Донецке - соцсети14:00
- За 10 мая россияне убили 2 и ранили 3 жителей Донетчины - ОВА12:00
- Оперативная информация Генштаба ВСУ о ситуации на Донбассе10:00
- Фонд Ахметова передал продуктовые наборы в прифронтовое Щурово17:00
- Полицейские доставили гуманитарную помощь в прифронтовую Макеевку13:00
- За сутки россияне 15 раз обстреляли населенные пункты Донетчины - ОВА12:00
- Оперативная информация Генштаба ВСУ о ситуации на Донбассе09:00
- Появились спутниковые снимки последствий удара по нефтебазе в Луганске16:00