Он же «Магический Кубик». И действительно, когда его первый раз берешь в руки поражаешься его простоте (конструкции) и в тоже время сложности (для сборки).
Классический кубик 3х3х3 венгр Эрнё Рубик придумал еще в далеком 1975 году (за год до моего рождения, ну, это к слову). В конце семедисятых – начале восьмидесятых эта головоломка «ворвалась» и покорила СССР с такой скоростью, что многим военным захватчикам и не снилась даже.
Задача очень проста: собрать кубик так, чтобы каждая из граней была окрашена в один из шести цветов. Но эта задача только на первый взгляд кажется простой: у кубика есть
всего лишь 43 252 003 274 489 856 000 различных сочетаний раскраски.
Алгоритмы.Спустя какое-то время в журнале «Наука и Жизнь» (а это, я вам скажу был один из самых интереснейших журналов в то время) начали публиковать алгоритмы сборки кубика. Но их там было так много, что для изучения не подходили вообще. Сотни комбинаций поворотов, понятное дело, запомнить их все было нереально для среднестатистического обывателя.
Анекдоты.Тут я хотел написать пару анекдотов про Кубик, но вы, наверняка их и так уже их знаете. Поэтому просто напомню про кубик для блондинок 1х1х1, про кубик 3х3х3 но одного цвета для прапорщиков, про кубик 0х0х0, который еще пока никто не видел.
Развитие кубика.
Очевидно, что на 3х3х3 Рубик не остановился, и были созданы варианты 4х4х4, 5х5х5 (вплоть до 7х7х7), додекаэдр, пирамидка, 2х2х2 и много других форм, уже ни никак не похожих на форму куба. В целом, алгоритмы для кубика 3х3х3 стали основами для сборки и этих. Одних только 3х3х3 было продано по всему миру более 350 миллионов, и продаются до сих пор. А сколько было «китайских аналогов», одному Богу известно. Кстати, о нем. Точнее, о его числе.
Продолжу в комментариях, на случай обрезки поста. 
Через некоторое время после создания кубика (1981 году) была выдвинута теория «52 ходов». Ну то есть из любой позиции кубик может быть собран максимум за 52 хода. И понеслось. Начали искать «минимальное число Бога» и «максимальное» (минимальное необходимое и максимальное достаточное количество поворотов из любой комбинации). В итоге исследований множества людей, в 2008 году (то есть всего-то пять лет назад) было доказано, что для сборки кубика нужно от 20 до 22 ходов. Есть информация, что в 2010 году доказали что 20 ходов это и минимум и максимум одновременно, но доказательство еще не подтверждено. Подробностей доказательств я рассказать вам не могу, скажу только что для вычисления этих чисел (22 и 20, как минимум) применялись суперкомпьютеры и каким-то образом там еще Гугл к этому причастен. Я к тому, что «на бумаге» это не вычислишь.
Отсебятина.
Я совершенно честным образом сам, самостоятельно, научился собирать кубик за исключением угловых элементов последнего слоя. Мучался, не передать как. И вот однажды, как сейчас помню, в парикмахерской, ожидая своей очереди какой-то дядечка, увидев мои мучения решил мне рассказать то, чего мне не хватало до полной сборки. Я запомнил, повторил многократно, и… я стал звездой класса в школе! Уметь собирать кубик Рубика в то время считалось не просто круто, а очень круто. Это как сейчас с Бэнтли пересаживаясь на Феррари кататься.
Мои рекорды: 3х3х3: 1 минута 20 секунд, 4х4х4: 5 минут (примерно, точно уже не помню), 5х5х5 – около 20 минут.
Мировой рекорд сборки 5,55 секунд (предыдущий 5,66)
Интересно, как они там все это меряют, но сил на изучение этого сегодня у меня уже нет, может позже, в комментариях подклюсь исследованиями этого вопроса.
А какие у вас рекорды с кубиком?
Однажды я все же попытался собрать его сам. Не читая литературы и зная только, что его надо собирать по поясам. Часа через два я его-таки собрал.
И эм... было это в туалете, извиняюсь.
PS. Кстати, именно в туалете приходят многие удачные идеи, решения и мысли. Это не только мое наблюдение, но и многих моих знакомых. Лично я связываю это с тем, что когда человек сидит на толчке, пережимаются довольно крупные артерии, находящиеся в бедрах. Таким образом в ноги попадает меньше крови. Это обеспечивает приток крови к остальным органам и к мозгу в том числе.
Hint: лечь на изящную кушетку красного дерева и слоновой кости, дабы питательный раствор полноценно прилил к процессору — ещё более результативно.
Исправляюсь: wiki, 11x11x11, лурк.
На этом видео интересное выражение лица у чувака сзади.
Уже какой-то прогресс. В 80-х они злее были.
Сначала они разбили все комбинации на 2,2 миллиарда групп, в каждой из которых было около 20 миллиардов вариантов, потом, исключая одинаковые и симметричные варианты количество групп было сведено к 56 миллионам.
Далее была написана программа, которая решала одну расцветку примерно за 20 секунд и не более чем за 20 шагов.
Ну и далее был получен доступ к компьютерному парку гугла, с помощью которого удалось перебрать все эти варианты и действительно убедиться в правильности оценки.
Эти оценки ещё не проверены (то есть не проверена верхняя оценка, для нижней есть пример), потому что, не смотря на то, что код программы, использованной в исследовании, выложен в открытый доступ, у вас просто не хватит времени. Так как подсчет затратил 35 процессорных лет, то есть если запустить программу на вашем четырехъядерном компьютере, то время проверки всех вариантов займет 35 лет.
А после я собирал куб довольно быстро — выдавливался угловой сегмент, конструкция рассыпалась и собиралась заново в нормальном законченном порядке — быстрее любого рекорда. Кто также делал?
Был ещё способ из собранного кубика, через хаос промежуточных этапов, сделать красивый шахматный узор, а потом вернуть обратно. Верхняя грань с каждой стороны на два влево, кажется.
Marcello Barenghi и его реалистичные рисунки