Найдено минимальное число ходов для решения кубика Рубика

Дэниел Кункле и Жене Куперман из бостонского Северо-восточного университета создали компьютерную программу, которая за 63 часа работы нашла минимальное число ходов, которого всегда будет достаточно для сборки кубика Рубика из любого исходного положения.

Ученые сообщают, что общее число возможных комбинаций у кубика Рубика составляет 43 квинтиллиона (миллиарда миллиардов), поэтому найти оптимальное решение - это очень непростая задача. Однако специалисты бостонского университета придумали специальный алгоритм, который позволил им вплотную подступиться к нахождению числа Бога (God"s Number) - так называется наименьшее число ходов за которые, в принципе, возможна сборка кубика из абсолютно любого исходного положения.

Кункле и Куперман запрограммировали компьютер на поиск самого короткого решения для одной из 15 тысяч неких промежуточных позиций, указав при этом разумное число шагов, за которое можно собрать кубик.

Выяснилось, что из любой исходной позиции кубика его можно собрать максимум за 29 ходов. При этом большинство исходных позиций потребовало всего 26, а иногда и меньше, ходов для своего решения. Поэтому ученые сосредоточили свое внимание на нескольких позициях, решение которых требовало 27-29 ходов.

Оказалось, что даже самые трудные позиции можно решить за 26 ходов или быстрее. В следствие чего, ученые сделали вывод, что число Бога, в конечном счете, составит около 20 ходов.

По материалам Мембрана