Newsmake

Кубик Рубика

Ученые, пользуясь вычислительными мощностями Google РС, решили проблему минимального числа ходов для Кубика Рубика оно оказалось не более 20 – это число еще эксперты называют  ”числом бога”.

В течении трех десятилетий многих ученых – математиков, игроков мучил один и тот же вопрос, а какое минимальное число ходов, чтобы собрать кубик Рубика из любого положения.

Но теперь группа ученых из Пало-Альто, Калифорния пользуясь вычислительными мощностями Google РС обнаружили, что из любого положения его можно собрать не более чем за 20 ходов. Эксперты называют число 20 “числом бога”, которое основано на предположении, что если даже знать все ходы, но собрать быстрее нельзя.

Результаты просчета показали, что существует около 100 тысяч исходных комбинаций кубика Рубика, из которых на собирание уходит точно 20 ходов, остальные исходные комбинации требуют для сбора от 15 до 19 ходов.

Ученые для исследования применили гигантскую вычислительную сеть компьютеров для математической проверки более 43 триллионов исходных комбинаций (43 252 003 274 489 856 000, если быть точным), которыми обладает кубик Рубика.

Чтобы сделать эту задачу вычислимой математики воспользовались теорией групп.  В соответствии в этим ученые вначале определили 2,2 миллиона групп, каждая из которых содержала 19,5 млрд. комбинаций.  Группирование позволило ученым уменьшить число наборов до 56 млн., за счет симметрии куба.

Ученые разработали быстросходящийся алгоритм, который позволяет набор из 19,5 млрд. просчитать за 20 секунд. При этом получается для решения полной задачи потребуется 35 лет работы домашнего компьютера.  Поэтому полное решение потребовало использования гигантской сети компьютеров Google РС.

Напомним, что кубик Рубика был изобретен венгерским профессором Эрно Рубиком в 1974 году, и он сразу приобрел всемирный успех.