20 ходов для решения кубика

Любая позиция Кубика Рубика может быть решена не более, чем за 20 шагов.

Несколько лет назад было доказано, что для Кубика Рубика есть решение за 23 хода. Теперь это число сократилось до 20. Чтобы это сделать, потребовалось 35 (тридцать пять) лет компьютерного времени, пожертвованного Гуглом.

Каждый блок решения использовал свой алгоритм — последовательность шагов для достижения нужной конфигурации. Например, один алгоритм предназначался для решения верхней грани, а другой — для позиционирования средних краев. Есть множество различных алгоритмов, различающихся по степени сложности и количеству требуемых шагов, но те, которые может запомнить человек, обычно требуют больше 40 шагов.

Разумно полагать, что Бог может использовать более эффективный алгоритм, который решает задачу за наикратчайшее число шагов. Этот алгоритм известен как “алгоритм Бога”. Число шагов в худшем случае называется числом Бога. В конце концов, было показано, что это число — 20.

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

Содержание

История создания
Завоевание планеты
Божественный алгоритм
Как собрать кубик рубика?

История создания

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

Долгое время Рубик не мог понять, как подступиться к реализации этой идеи. Однажды он, сидя на берегу Дуная, меланхолично наблюдал, как волны перекатывают гальку, выстраивая из нее объёмные геометрические фигуры и обтачивая острые края камней. И… эврика! Вернувшись домой, Рубик начинает лихорадочно продумывать проект. Отбросив картон и древесину, он останавливает выбор на пластмассе. Чтобы элементы в виде маленьких кубиков могли вращаться по трём осям, изобретатель применил внутренний цилиндрический механизм. Перебрав множество вариантов, Рубик выбрал простую шестицветную гамму для внешнего оформления головоломки. Студенты пришли в восторг от кубика, и тут Эрнё понял, что, создавая учебное пособие, он явил на свет игрушку, которая может стать популярной во всем мире.

Завоевание планеты

К счастью, в Будапешт приехал коммивояжер одной из немецких фирм, венгр по национальности, Тибор Лакзи. С удивлением понаблюдав, как столичные жители от мала до велика крутят в руках кубик, он зашёл в магазин и тоже купил себе разноцветную игрушку. Закончивший Венский университет, экономист по профессии, Тибор считал, что справится с задачей за считанные минуты. Пришел в себя он только под утро, с удивлением констатировав, что собрал только одну грань. И после этого твёрдо решил заняться продвижением кубика на международном рынке. Он привёз в Будапешт владельца фирмы «Seven Towns Ltd» Тома Кремера. Тот тоже был потрясен количеством разноцветных кубиков в руках горожан и взялся за масштабное производство игрушки. Так, в 1980 году кубик Рубика начал свое триумфальное шествие по планете. Подобного ажиотажа изготовители игрушки не ожидали — чуть ли не во всех странах мира появились поклонники этой игры.

Божественный алгоритм

К сожалению, существует и негативная составляющая этого развлечения. С появлением головоломки сначала увеличилось количество пациентов психиатрических клиник, потом тревогу забили травматологи – обратившиеся к ним больные жаловались на боли в запястьях. В результате чего в медицине даже появился новый термин – «синдром Рубика». Ну и, конечно, разноцветная игрушка отбирает массу времени – на неё даже можно «подсесть», как на компьютерные игры… в результате у некоторых геймеров страдает личная и профессиональная жизнь.

История поиска «алгоритма Бога» для кубика Рубика началась в 1980 году — с тех пор математики, программисты и просто любители начали целенаправленно искать алгоритм, который бы позволил решать кубик Рубика за минимальное число ходов. В июле 2010 года программист из Пало-Альто Томас Рокики, учитель математики из Дармштадта Герберт Коцемба, математик из Кентского университета Морли Дэвидсон и инженер компании «Google Inc.» Джон Детридж доказали, что каждая конфигурация кубика Рубика может быть решена не более чем в 20 ходов (при этом любой поворот грани считается одним ходом). Объём вычислений составил около 35 лет процессорного времени, пожертвованного компанией «Google».

Как собрать кубик рубика?

2-3. Второе и третье действие похожи, так как они нацелены на послойную сборку кубика. На втором действии необходимо собрать сторону, на которой уже есть крест, полностью, то есть вся сторона должна быть одного цвета. Причём нужно сделать так, чтобы фрагменты кубика по бокам образовывали пояс, расположенный около уже собранной грани. Третье действие — это продолжение второго, где нужно собрать второй пояс.

4-5. Четвёртое и пятое действие — это зеркальное отражение первого и второго действий. На четвёртом этапе необходимо собрать крест на стороне, противоположной той, на которой собирался крест на первом действии, а на пятом действии надо полностью собрать эту сторону.

6-7. На шестом действии нужно расположить в правильном порядке угловые части кубика, чтобы все три их стороны подходили по цвету к граням. Осталось только расположить боковые части кубика (у которых две грани) по местам, чтобы они соответствовали граням кубика – теперь головоломка полностью собрана!

Получайте на почту один раз в сутки одну самую читаемую статью. Присоединяйтесь к нам в Facebook и ВКонтакте.

В 1980 году открылся список рассылки для любителей кубика Рубика. С тех пор тысячи ценителей головоломки, среди которых ошеломляющее количество математиков, инженеров и программистов, объединили усилия, чтобы найти «алгоритм Бога» : способ, как собрать кубик за минимальное количество ходов. В июле 2010 года программист из Пало-Альто Томас Рокики, учитель математики из Дармштадта Герберт Коцемба, математик из Кентского университета Морли Дэвидсон и инженер компании Google Inc. Джон Детридж доказали, что каждая конфигурация кубика Рубика может быть решена не более чем в 20 ходов. А действующий рекорд – 4.94 секунды . Что ж, метод, описанный ниже, не гарантирует скоростного решения. Но почему бы не проверить теорию на практике?

Автор метода утверждает, что он может собрать кубик Рубика, повторяя всего лишь две комбинации . Начать можно с любой позиции.

Просто поверните левую грань.

Теперь поверните верхнюю грань.

Повторяйте эти две комбинации друг за другом. Сколько раз? Пока не соберете!

Видео-демонстрация этого метода собрала уже более 14 миллионов просмотров. Конечно, в комментариях нашлось немало недовольных, которым не удалось решить головоломку. Может, они просто недостаточно долго повторяли комбинацию?

Обращали внимание, как стремительно «летают» грани кубика в руках профессионалов? Оказывается, и тут есть маленькая хитрость. Чтобы ускорить процесс, нужно использовать…смазку! Подойдёт жидкий силикон.