А как вы собираете «кубик Рубика»? // 06 Ноября 2012

Популярную головоломку «кубик Рубика» можно решить за 20 ходов независимо от исходной позиции. К такому выводу пришли члены исследовательской группы, занимающейся решением популярной математической задачи – поиском «числа Бога».

«Числом Бога» в среде «рубикоманов», практикующих научный подход, считается наименьшее количество ходов, необходимых для сборки кубика из любой возможной позиции. В 1981 году было признано, что кратчайший путь к решению равен 52 ходам, а в августе 2008 года ученые пришли к мнению, что головоломку можно решить за 22 хода. Новой группе исследователей, в состав которой входят преподаватель математики, инженер компании Google и профессиональный программист, удалось опровергнуть и это утверждение. Ученые сообщают, что, несмотря на впечатляющее количество возможных комбинаций (более 43 квинтильонов, а точнее 43’252’003’274’489’856’000) для сборки кубика необходимы всего два десятка движений.

Напомним, что популярная трехмерная игрушка была изобретена в 1974 году венгерским скульптором Эрно Рубиком (Erno Rubik) и довольно быстро стала одной из самых популярных в мире головоломок. К январю 2009 года во всем мире было продано 350 миллионов экземпляров кубиков.

Время, необходимое для сборки кубика, может составлять от нескольких секунд до нескольких часов. Наиболее искусные сборщики даже принимают участие в специальных чемпионатах. Нынешний мировой рекорд, установленный в 2008 году, составляет 7,08 секунд.

«Спустя полтора десятка лет с момента поступления кубика в продажу была обнаружена исходная позиция, из которой кубик собирается за 20 ходов, - сообщают члены исследовательской группы на официальном сайте, - «Нам потребовалось еще столько же времени, чтобы доказать, что такое количество движений необходимо для сборки кубика из любой возможной позиции».

Разумеется, поиск самого короткого решения представляет собой весьма ресурсоемкую задачу, «неподъемную» для обыкновенных настольных ПК. Организаторам проекта пришлось разделить основную задачу (сборка «кубика Рубика») на 2’217’093’120 подзадач, каждая из которых предполагает обработку 19’508’428’800 возможных позиций. Выполнение необходимых расчетов на достаточно мощной машине (на базе четырехъядерного процессора Intel Nehalem с тактовой частотой 2,8 гигагерц) заняло бы около 35 лет. Ученым пришлось воспользоваться вычислительными ресурсами, любезно предоставленными компанией Google. К сожалению, исследователи не предоставляют более подробной информации об используемой аппаратной платформе.

По материалам сайта Wired.