Эрно Рубик

Кубик Рубика (первоначально был известен как «Магический кубик», венг. Buvos kocka) — механическая головоломка, изобретённая в 1974 году венгерским скульптором и преподавателем архитектуры Эрнё Рубиком.

Головоломка представляет собой пластмассовый куб, составленный из 26 кубиков меньшего размера, способных вращаться вокруг невидимых снаружи осей. В центре конструкции вместо «невидимого кубика» — крестовина. Каждый из девяти квадратов на каждой стороне кубика окрашен в один из шести цветов, как правило расположенных парами друг напротив друга: белый-жёлтый, синий-зелёный, красный-оранжевый. Повороты сторон кубика позволяют переупорядочить цветные квадраты множеством различных способов. Задача игрока заключается в том, чтобы, поворачивая стороны куба, вернуть его в такое состояние, когда каждая сторона состоит из квадратов одного цвета («собрать кубик Рубика»).

Считается, что кубик Рубика — лидер среди игрушек по общему количеству продаж: по всему миру было продано порядка 300 млн кубиков Рубика, как оригинальных, так и различных аналогов.

Существуют компьютерные игры, моделирующие «Магический кубик», но они не получили, по сравнению с оригинальной механической головоломкой, широкого распространения.

Сегодня права на кубик Рубика и другие головоломки Эрнё Рубика принадлежат английской компании Seven Towns Ltd., которой вот уже 40 лет владеет близкий друг Эрнё Рубика — Том Кремер. Под контролем англичан кубик Рубика производится и продаётся во всем мире. Удивительно, но в последнее время рост продаж головоломки начал бить все рекорды — похоже, что в Европе и США начинается очередная волна всеобщего увлечения кубиком Рубика.

Название «Кубик Рубика» принято в большинстве языков мира, за исключением венгерского, немецкого и португальского, где распространённым осталось его первоначальное наименование («Магический куб», венг. Buvos kocka; нем. Zauberwurfel; порт. Cubo Magico), в китайском и иврите, в которых его называют «венгерским кубиком».

Из каждого кубика с внутренней стороны вырезан фрагмент таким образом, что получается шарообразная полость. Помимо этого, на рёберных и угловых кубиках имеются выступы особой формы. Эти выступы образуют фрагмент шара, плотно входящий в полость. Благодаря такой конструкции, грани кубика свободно крутятся.

Нахождение оптимального решения

Так называемый «алгоритм бога» для сборки Кубика Рубика не найден. С помощью больших по объёму расчётов на компьютере (7,8 ядро-лет) математик Томас Рокики (Tom Rokicki) доказал, что из любой начальной конфигурации кубик можно собрать не более чем за 23 хода, улучшив тем самым своё же прежнее достижение в 25 ходов. Для доказательства достаточности 23 ходов использовалось свободное машинное время компьютерного кластера, который использовался для создания фильмов «Человек-паук 3» и «Лови волну!».

Также, известны конфигурации, требующие для сборки не менее 20 ходов. Это существующая на сегодняшний день нижняя граница.

Прежнее доказательство для верхней границы — 26 ходов — было сделано исследователями Дэниелем Канклом и Джином Куперманом (Kunkle and Cooperman).