17 "ключей" – один ответ: математики решили судоку на свой лад

Ставшая в последние годы очень популярной японская логическая игра судоку привлекла внимание математиков, поставим перед ними свою задачу.

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

Ирландский математик Гэри Макгир из Дублинского университетского колледжа изобрел довольно сложный алгоритм для суперкомпьютера и доказал, что минимальное число ключей для судоку равно семнадцати. При числе 16 или ниже задачка судоку имеет более одного решения. В газетах, по словам ученого, обычно используют не менее 25 ключей, и чем больше их, тем проще разгадывается задачка.

Макгир утверждает, что на решение задачи при помощи суперкомпьютера в Дублине у него (и его команды) ушло около семи миллионов часов машинного времени ЦПУ. Кроме того, по его словам, методика, примененная при решении "Великой теоремы судоку", берет начало из статей по секвенированию геномов и клеточных сетей, а потому разработанный им алгоритм может быть с успехом использован и в этих областях.