Математики решили задачу о подсказках в судоку

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

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

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

 

Судоку с 16ю цифрами

 Судоку с 16ю цифрами-подсказками, имеющий 2 решения
(можете попытаться решить данный судоку тут)

 

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

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

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

 

Источник: Lenta.ru

 

комментарии (7)

Козладоев | 17.04.2012, 12:25
Задача о максимуме подсказок ИМЕЕТ СМЫСЛ!!!. Сколько же и куда надо добавить подсказок к 17, чтобы получилась задача СУДОКУ (с единственным ОТВЕТОМ). 000801000, 000000430, 500000000; 000070800, 000000100, 020030000; 600000075, 003400000, 000200600;! У меня получилось - 7: 2g2, 5h4, 5c5, 68, 8a1, 9a9, 95!!!
Козладоев | 04.03.2012, 14:05
Дошло, что задача о МАКСИМУМЕ не имеет смысла. Берём любой ОТВЕТ, удаляем одну любую цифру и получаем "максимум" 89. В этом раскладе можно выбросить 18 плохих кандидатов (они не дают ОТВЕТ, напр. 2i7), после чего получить по правилам ещё 18 (случайно совпало) "железных" цифр (напр. 2h7). При этом удалится ещё куча кандидатов - останутся всего 56 кандидатов в 22 ячейках (напр. 14569 в ячейке c6 - самые крутые). Все 56 дают 56 ОТВЕТОВ. 90-22= 68. У всех 56 ответов каркас из 68 ПОДСКАЗОК. И опять утверждаю - на любую задачу СУДОКУ (с ЕДИНСТВЕННЫМ ОТВЕТОМ) найдётся ЛОГИЧЕСКОЕ РЕШЕНИЕ. Правда, в финской пришлось применить пару раз на развилке из двух возможностей конструкцию "если..., то... близко находится тупик".
Козладоев | 03.03.2012, 21:05
Привожу этот самый злополучный расклад (для тех, кто не найдёт, но - интересно попробовать самому). 000801000, 000000430, 500000000; 000070800, 000000100, 020030000; 600000075, 003400000, 000200600; Итого 17 подсказок, правда цифры 9 - ни одной. Тем не менее, беру назад утверждение о возможности решения чисто ЛОГИЧЕСКИМ путем. Правда, я плохо умею бороться с лишними кандидатами и ненавижу развилки без тупиков.
Козладоев | 03.03.2012, 20:43
Дополнение: по правилу для сегментов - 6h9, 5g9, 4i1, 9e8. С помощью программы "Судоку для всех" обнаружил ещё 4 подсказки на своих законных местах - 2e9, 4e7, 2a8 и 4f4. Т.о. 41 подсказка входит в любой из 118 ОТВЕТОВ, а МАКСИМУМ подсказок - 42! Проверьте, пожалуйста... Тоже задача - сколько надо добавить к этому раскладу подсказок, чтобы получилась СУДОКУ с единственным ОТВЕТОМ? Хватит ли одной? 3,4,5 не дают оснований вычеркнуть их из списка кандидатов. В списках 136, на 18 из них программа жалуется - ...мало данных для решения... и никакого ОТВЕТА не выдаёт.
Козладоев | 03.03.2012, 16:08
Не менее интересен вопрос о МАКСИМУМЕ подсказок в раскладе. См. расклад из 17 (цифры 9 нет) в Заметки на полях Галуа. Найдено 16 подсказок, и я нашел еще 4 по правилу сегментов - итого 37. Все войдут в любой из ОТВЕТОВ при ЛОГИЧЕСКОМ РЕШЕНИИ этого расклада из 37. Развилок навалом, конечно. Как бы найти алгоритм генерирующей программы? От 17 до 38 подсказок, но с ЕДИНСТВЕННЫМ ОТВЕТОМ - т.е, СУДОКУ по определению.
Козладоев | 12.02.2012, 19:40
P.S. Обратите внимание - первый и третий подъезды содержат семейные СЕГМЕНТЫ, а второй этаж - (89) - хозяйская пара и 7, 1 и 5 - гости. Это не спроста, можно в число 16 подсказок добавить хотя бы ещё одну цифру. И иметь ДВА ОТВЕТА.
Козладоев | 12.02.2012, 17:23
Молодцы ирландцы !!! См… Математики решили задачу о подсказках в судоку… Но, остаётся проблема о 16 подсказках с полным набором цифр (9) или хотя бы без одной цифры (8). Убедимся, что Судоку с 16 подсказками из 7 цифр во-первых, имеет ОТВЕТ, во-вторых, ОТВЕТОВ не более двух. А для этого требуется ЛОГИЧЕСКОЕ РЕШЕНИЕ с цепочкой ходов (не метод «тыка» и не РЕШЕНИЕ программами). Итак: 1) Стр 5 Ст E -> дублет (34) в Кв. V (центральный) -> 3G4, 4H4; 3I7, 3C9, 3A1, 3D3, 3,4V; 4F2; 2B6, 1C6, 1B3, 1G2, 4B1, 4A8, 4G9, 4I3; 2) Стр 9 Ст F -> дублет (15)кв.II -> 1E5; Дублеты (57) и (89) в Кв. V; 3) Подъезд 2: (15) – хозяева, 4,7 – гости -> 7D1; Наконец-то программе « Судоку для всех» хватило данных, показала ОТВЕТ и… успокоилась на этом. Программа из Blogint (была такая на сайтах в прошлом году) показывала этот же ОТВЕТ через пару секунд (ей хватает и 16 данных), но тоже не проверяет ЕДИНСТВЕННОСТЬ. Продолжаем наше РЕШЕНИЕ: 7H3, 7I8, 7A7, 7F9, 7C4, 7E6, 5E4; 4) 2F8, 2H9, 2I5, 2G1, 2E2; 5H1, 5G6, 5A5, 5C2; 6A6 (Кв.), 6H5 !!! Осталось 28 клеток заполнить 2 цифрами 1, 2 -5, 6 -6 и по 9 цифр 8 и 9. На втором этаже (в Кв. V) пробуем оба варианта для 8 и 9. И получаем ДВА ОТВЕТА !!!
Добавить комментарий