50 лет кубику Рубика

Культовая механическая 3D-головоломка "Кубик Рубика" была изобретена в 1974 году и в этом году отмечает свое 50-летие. Помимо того, что это популярная головоломка, которую может попытаться решить каждый, она затрагивает некоторые интересные математические концепции и ставит перед учеными-компьютерщиками задачу создания эффективных алгоритмов поиска.

Если вам нужно напомнить, Кубик Рубика - это пластиковый куб, покрытый разноцветными квадратами, который игрок пытается повернуть так, чтобы все квадраты на каждой грани были одного цвета. Изначально его изобретатель, венгерский архитектор и профессор Эрнё Рубик, хотел создать учебное пособие, чтобы помочь своим студентам в Академии прикладного искусства и ремесел в Будапеште понять трехмерные объекты. Во время подготовки курса по начертательной геометрии в 1974 году и работы с пятью платоновыми твердыми телами он особенно заинтересовался кубом, и, как он написал в своих мемуарах 2020 года "Cubed, The Puzzle of Us All",

"мне ни разу не пришло в голову, что я создаю головоломку".

На самом деле его целью было решить структурную проблему, связанную с перемещением частей независимо друг от друга, чтобы весь механизм не развалился. Он понял, что случайно создал головоломку, только когда разбил свой "Волшебный куб" и попытался его восстановить. В 1976 году Рубик получил патент в Венгрии, а первые пробные партии "Волшебного куба", скрепленные между собой пластиковыми деталями, которые не позволяли легко разобрать головоломку, были изготовлены в конце 1977 года и продавались в магазинах игрушек в Будапеште. Именно когда бизнесмен Тибор Лацци в феврале 1979 года взял "Волшебный кубик" на Нюрнбергскую ярмарку игрушек в Германии в попытке популяризировать его, произошел прорыв. К 1980 году он был переименован в кубик Рубика, принял свою легендарную форму и название, а также выиграл премию "Игра года" (Spiel des Jahres) в Германии. В течение десятилетий были проданы сотни миллионов экземпляров игры, из них 200 миллионов только в период с 1980 по 1983 год, что позволило ей стать самой продаваемой головоломкой в мире. Кубик Рубика пользуется большой популярностью у компьютерщиков. По данным New York Times, Дональду Кнуту потребовалось менее 12 часов, чтобы решить головоломку, начав за обеденным столом вечером и работая до самого утра. I Programmer следил за математическими открытиями на протяжении многих лет, начиная с открытия в июле 2010 года, когда мы сообщили: как бы вы ни тасовали кубик, как бы долго и сколько бы хитрых поворотов вы ни применяли, кубик можно вернуть в исходное состояние всего за 20 ходов.

В то время этот результат называли "числом Бога", поскольку только божество могло обладать способностью проверять миллионы различных комбинаций в мгновение ока, и мы прокомментировали, что его нахождение после 30 лет усилий математиков кажется тем более удивительным, когда вам говорят, что существует 43 252 003 274 489 856 000 потенциальных позиций. Число Бога 20 было найдено для кубика Рубика 3x3x3 и было найдено методом грубой силы. В следующем году в статье Rubik's Cube - The Order Of God's Number мы рассказали о том, что Эрик Демейн, Сара Айзенштат и Михаил Рудой обнаружили, что наименьшее количество ходов, необходимое для решения nxnxn кубика Рубика, пропорционально n^2/log(n).

"Это также поднимает вопрос о том, является ли поиск оптимального решения общего кубика NP трудным или нет". На этот вопрос был дан ответ шесть лет спустя, в 2017 году, той же командой исследователей и опубликовано сообщение в статье Rubik's Cube Is Hard - NP Hard, в котором говорится.

Теперь доказано, что выяснение того, можно ли решить случайный кубик ровно за n ходов, является NP-полным. Как мы сообщали в то время, в 2015 году было достигнуто замечательное компьютерное достижение, когда кубик 17x17x17 с 66 и 1053 нулями в различных возможных положениях был решен за семь с половиной часов, см. ou. Совсем недавно за эту задачу взялся искусственный интеллект, как сообщается в статье AI Learns To Solve Rubik's Cube - Fast! А что произойдет, если объединить ИИ и робототехнику? Узнайте об этом в статье AI Wins At Rubik's Cube With Just One Hand, посвященной подвигу, продемонстрированному Open AI. Спасибо Эрне Рубику, чье изобретение уже полвека служит источником веселья и, несомненно, будет продолжать открывать новые горизонты.