Форум - Интересно и познавательно - Математики решили задачу о подсказках в судоку

#46465 by Отключён (Новичок) в 2012-01-11 14:04:36 , (255 недели) назадTop




  Сообщений: N/A


Ирландские ученые решили так называемую проблему подсказок в судоку. Препринт их статьи появился на сайте arXiv.org.

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

В рамках новой работы ученые ответили на вопрос, сколько минимум таких подсказок нужно, чтобы судоку имело однозначное решение. Как оказалось, подсказок должно быть не менее 17. Примечательно, что ранее уже был известен пример задачи с 16 подсказками, у которой есть ровно два решения.

Для работы ученые использовали довольно мощный алгоритм отсечения лишних вариантов. Для этого они описали так называемые плохие множества - набор цифр в заполненной таблице, который может быть заменен на другой (отсюда и возникает неоднозначность). Затем они считали, сколько таких плохих множеств можно "убить" той или иной подсказкой.

Как следствие, перебор удалось свести к чуть менее чем 5,5 миллиарда вариантам (всего правильных вариантов заполнения судоку порядка 1021). Эти вычисления, которым предшествовало двухлетнее тестирование алгоритма, были проделаны на суперкомпьютере. В результате ученые установили, что 16 подсказок (или меньше) недостаточно для того, чтобы "убить" все плохие множества, поэтому придумать головоломку с таким количеством подсказок и однозначным решением невозможно.

По словам ученых, созданная ими схема уменьшения количества вариантов с помощью плохих множеств может быть использована в других областях исследований - например, биоинформатике или автоматизированном тестировании программ.
Отправить сообщеньку
#47572 by Ядерный взрыв (Опытный пользователь) в 2012-01-26 16:09:06 , (253 недели) назадTop




  Сообщений: 37


Интересно! Не знал!))
Отправить сообщеньку
#47573 by Ядерный взрыв (Опытный пользователь) в 2012-01-26 16:10:26 , (253 недели) назадTop




  Сообщений: 37


У меня прога бывала которая показывает куда тыкать!
Отправить сообщеньку
#47574 by Ядерный взрыв (Опытный пользователь) в 2012-01-26 16:15:22 , (253 недели) назадTop




  Сообщений: 37


Игруна на деньги можно погонять с прогой!
Отправить сообщеньку
#47575 by Ядерный взрыв (Опытный пользователь) в 2012-01-26 16:16:33 , (253 недели) назадTop




  Сообщений: 37


Я вытаскивал макс с игруна 100 руб в месяц !
Отправить сообщеньку
#47576 by Ядерный взрыв (Опытный пользователь) в 2012-01-26 16:17:57 , (253 недели) назадTop




  Сообщений: 37


Игрун полный отстой!
Отправить сообщеньку
#47634 by Отключён (Новичок) в 2012-01-26 21:19:37 , (253 недели) назадTop




  Сообщений: N/A


*93* вы зачем сами с собой говорите?
Отправить сообщеньку

       [1]       

Быстрый переход: