Суперкомпьютеры улучшили рекорд решения головоломки "кубик Рубика": теперь всего 26 ходов

Благодаря мощностям современных суперкомпьютеров люди вплотную приблизились к самому быстрому решению головоломки "кубик Рубика". Последнее исследование, проведенные двумя учеными из Северо-Восточного университета в Бостоне, показало, что головоломку можно решить за 26 ходов из любого положения. Ранее был известен способ решения головоломки за 29 ходов, сообщает3DNews.

Найти решение головоломки, даже при условии использования суперкомпьютера, непросто, поскольку требуется перебрать около 43 триллиона (это 10 в восемнадцатой степени) комбинаций.

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

Затем задача была упрощена: из всех комбинаций были выбраны только те, которые можно решить, поворачивая элементы на 180 градусов, то есть, в полоборота, не используя повороты на четверть оборота. Таким образом, было отобрано 15 тысяч комбинаций из триллиона. Это - сравнительно немного, и обычный компьютер может найти самый быстрый способ решения каждой из таких комбинаций за один день. Дав компьютеру задание решить все эти комбинации, ученые выяснили, что все они могут быть решены за 13 ходов или быстрее.

Затем ученые посчитали, сколько ходов требуется для того, чтобы из любой случайной комбинации перейти к одной из 15 тысяч решенных комбинаций. Для этого все комбинации были классифицированы по группам. В рамках одной группы все комбинации могли быть преобразованы одна в другую с использованием только полуоборота. Таким образом, число комбинаций было сокращено до 1,4 миллиарда. Все эти комбинации были решены, и было установлено, что для того, чтобы добиться перехода от любой из таких комбинаций до одной из 15 тысяч решенных комбинаций требуется не более 16 ходов. То есть, на решение самого сложного задания требуется не более 29 ходов.

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

Несмотря на то, что ученым удалось улучшить предыдущий результат на три хода, решение не является окончательным. Большинство исследователей полагают, что решить головоломку можно за 20 ходов, хотя пока что доказать это никому не удалось.