Пассажир в метро развлекал нас собиранием кубика Рубика
Ехал в метро домой. Рядом с местом, где я стоял, сидел парень и собирал кубик Рубика. Сам он был увлечен процессом и не смотрел по сторонам. Зато на него смотрели все, кто ехали с ним рядом. Кубик явно разработан, потому что парень поворачивал его грани одним пальцем. После того, как он собрал, рядом стоящие граждане потеряли к представлению интерес. Зато оживилась девушка, сидевшая рядом. Первую сборку она слала кому-то смски, поэтому вторую наблюдала практически в полном одиночестве.
Лично я свой первый кубик собрал, просто переклеев наклейки. Увы, этот способ быстро портил кубик, наклейки переставали клеиться. Пришлось искать новый способ. Вскоре он был найден. Я вытаскивал кубики, а затем вставлял их обратно нужной стороной. Получалось гораздо быстрее.
С появлением легкодоступного интернета я наконец смог посмотреть, как нужно собирать кубик. Этот способ не произвел на меня должного впечатления. Я по прежнему считаю, что вытаскивать кубики практичнее.
Зашел в википедию, а там пишут страшное:
Алгоритм, собирающий кубик Рубика за минимальное число ходов, традиционно называется «алгоритмом Бога». Максимальное возможное число ходов, которое такой алгоритм может сделать, называется «числом Бога». Долгое время о числе Бога были известны только нижние и верхние оценки. Однако, последний анонсированный (хотя и не проверенный) результат утверждает, что число Бога равно 20. Простого описания «алгоритма Бога» при этом по-прежнему не найдено, оптимальная сборка кубика осуществляется с помощью трудоёмких вычислений.
Нижние оценки
Известны конфигурации, требующие для сборки не менее 20 ходов, что является наибольшей известной нижней границей для числа Бога. Предположительно эта граница точна, и число Бога в точности равно 20.
Верхние оценки
Нахождение верхних оценок для числа Бога имеет богатую историю.
Доказательство верхней границы в 26 ходов было сделано исследователями Дэниелем Канклом и Джином Куперманом (Kunkle and Cooperman).
С помощью больших по объёму расчётов на компьютере (7,8 ядро-лет) математик Томас Рокицки (Tom Rokicki) доказал, что из любой начальной конфигурации кубик можно собрать не более чем за 23 хода, улучшив тем самым своё же прежнее достижение в 25 ходов. Для доказательства достаточности 23 ходов использовалось свободное машинное время компьютерного кластера, который использовался для создания фильмов «Человек-паук 3» и «Лови волну!» Впоследствии Томас Рокицки доказал достаточность 22 ходов для сборки.
Наконец в августе 2010 года группа под руководством профессора Морли Дэвидсона сообщила, что, используя свободное от обработки поисковых запросов машинное время одного из суперкомпьютеров Google Inc., им удалось доказать, что из любого положения кубик Рубика можно собрать не более, чем за 20 ходов. Однако этот результат пока еще не проверен.
Особенно в статье порадовало описание того, как исследователи использовали рабочее положение в личных целях. Ну и конечно рассчитывать вариант сборки кубика на компьютере, на мой взгляд, уже за гранью.
Пожалуйста, оставляйте комментарии в моем блоге.