Конференція Високопродуктивні обчислення, Київ, 13-15 жовтня 2014

Математики розв’язали задачу про підказки в судоку

4 січня 2012

Ірландські вчені Gary McGuire, Bastian Tugemann та Gilles Civario розв’язали так звану проблему в судоку. Препринт їх статті з’явився на сайті ArXiv.org.

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

В рамках нової роботи вчені отримали відповідь на питання, скільки мінімум таких підказок необхідно, щоб судоку мало однозначний розв’язок. Виявилось, що підказок повинно бути не менш, ніж 17. Раніше вже був відомий приклад судоку з 16-ма підказками, який мав рівно два розв’язки.

Для роботи вчені використовували досить потужний алгоритм відсікання зайвих варіантів. Для цього вони описали так звані «погані множини» – набори цифр в заповненій таблиці, які можуть бути замінені на інші (звідки і виникає неоднозначність). Потім вони обчислювали, скільки таких «поганих множин» можна виключити тою чи іншою підказкою.

Як наслідок, перебір вдалось звести до 5,5 мільярдів варіантів. Для порівняння, усього правильних варіантів заповнення судоку близько 1021. Ці обчислення, яким передувало дворічне тестування алгоритму, були виконані на суперкомп’ютері. В результаті вчені встановили, що 16 і менше підказок не досить для того, щоб виключити всі «погані множини», тому придумати ломиголовку з такою кількістю підказок з однозначним розв’язком неможливо.

За словами вчених, створена ними схема зменшення кількості варіантів за допомогою «поганих множин» може бути застосована до інших областей досліджень, наприклад, у біоінформатиці чи автоматизованому тестуванні програм.

Теги: математика

Матеріали за темою:

Коментарі

Коментарі до "Математики розв’язали задачу про підказки в судоку":

це не головоломка, а задача 5-ого класу )=

коля08.09.2013

складіть задачу за таким виразом 2.150= 3.47= замість крапки множення

Дуже цікава головоломка. Добре сушить мозок