Число Бога и кубик Рубика

Блог дремучего деда

Число Бога и кубик Рубика

Число Бога и кубик Рубика

Приблизительно с 1980 года, когда открылся список рассылки для любителей кубика Рубика, математики, программисты и просто любители стремились найти алгоритм, который бы позволил на практике решать эту головоломку за минимальное число ходов – «алгоритм Бога» (Бог всегда знает самый короткий путь). С этой проблемой была связана ещё одна – проблема определения «числа Бога» — числа ходов, всегда достаточного для сборки головоломки.

Существует два наиболее распространённых способа измерения длины решения (метрики). Первый способ — одним шагом (ходом) решения считается поворот грани на 90° (quarter turn metric, QTM). По второму способу — за 1 ход также считается и полуоборот грани (face turn metric, FTM, иногда это обозначают HTM — half-turn metric).

В июле 2010года, вычислив все возможные положения кубика Рубика, группа учёных, работавшая в рамках проекта God’s Number, установила, что каждая конфигурация кубика может быть решена не более чем в 20 ходов. При этом любой поворот грани считался одним ходом (метрика FTM). Головоломку раскусили калифорнийский программист из Пало-Альто Томас Рокики (Tomas Rokicki), математик Морли Дэвидсон (Morley Davidson) из Кентского университета (Kent University), учитель математики из Дармштадта Герберт Коцемба (Herbert Kociemba) и инженер Google Джон Детридж (John Dethridge).

Долгое время учёные полагали, что теоретический минимум необходимых ходов равняется 18, пока в 1995 году давнему фанату головоломки, математику Майклу Риду (Michael Reid), не удалось доказать, что существует позиция, требующая 20 поворотов граней. На проверку новой гипотезы ушло 15 лет, и, по словам специалистов, в глубине души они надеялись, что какая-нибудь комбинация, требующая 21 хода, всё же будет найдена.

Изначально вычислениями должен был заняться суперкомпьютер. Как в прошлый раз, в 2007 году, когда к решению подобрались другие покорители головоломки - Дэниел Кункле (Daniel Kunkle) и Жене Куперман (Gene Cooperman) из бостонского Северо-восточного университета (Northeastern University). Но распределённые вычисления на компьютерах компании Google (которая «подарила» исследователям 35 «процессоро-лет», запуская программу учёных во время простоя машин) оказались выгоднее. Они позволили всего за несколько недель выполнить все необходимые расчёты. Технические данные о производительности и количестве компьютеров не разглашаются.

Общее число состояний кубика Рубика превосходит 43 квинтиллиона (43 х 1018) , а точнее 43252003274489856000. Это число авторы проекта поделили на 2,2 миллиарда групп, каждая из которых включала порядка 20 миллиардов позиций. При последующей обработке число групп уменьшили до «всего-то» 55882296. Математики воспользовались тем, что изменение ориентации кубика в пространстве и его отражение в зеркале дают похожие позиции с аналогичными решениями.

Выяснилось, что количество начальных позиций, которые требуют 20 ходов, относительно невелико. Точное число учёные назвать затрудняются, однако, оценочная величина равна 300 миллионам вариантов. Подавляющее же большинство решений головоломки требует 15–19 ходов. А вероятность существования исходной позиции, для решения которой нужно больше 20 ходов, инициаторы поиска «числа Бога» оценили как исчезающе малую.

В августе 2014 года Томас Рокики и Морли Дэвидсон доказали, что каждая конфигурация кубика Рубика может быть решена не более чем в 26 ходов без использования поворотов на 180° (в метрике QTM). Объём вычислений составил около 29 лет процессорного времени в суперкомпьютерном центре Огайо.

Хомячковый рай. Уйти и потеряться:

Комментарии к этой заметке больше не принимаются.


июль 2015
пн вт ср чт пт сб вс
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31