Найдено число Бога (для Кубика)

Я ни разу не собирал Кубик Рубика. Даже в детстве у меня всегда было много более интересных дел. Но если честно — у меня просто не получалось.

^{— Эрно Рубик, архитектор, создатель Кубика Рубика}

На прошлой неделе произошло событие, которое заставило меня узнать, что такое Алгоритм Бога, Число Бога, и как это связано с кубиками.

Три на три на три — не так уж и сложно

Комбинаторика — это такой раздел математики, в котором все можно по-разному перемешать. Этот беспорядок всем нравится, но любишь кататься, люби и саночки возить. В комбинаторике все эти перемешивания принято подсчитывать. Это не так уж и просто, почти как собирать Кубик Рубика.

Допустим, вы нашли три разноцветных кубика Лего в кафе, где вы ждете кого-то, но этот кто-то опаздывает. Вы начинаете по-разному соединять эти три кубика, создавая всяческие комбинации из них. Вам конечно все равно, вы думаете только о времени. Но комбинаторика знает — вы можете собрать 3! уникальных конфигураций. 3! это не тройка, которая должна вас удивить, это факториал тройки. 3! = 1 × 2 × 3 = 6. «Больше шести конфигураций собрать не получится», — говорит комбинаторика, но нам все равно, время поджимает.

^{— 3! вариантов перестановок трех кубиков и человечек А. Но разве Лего может ассоциироваться с кафе?}

Так вот, если бы вы крутили в кафе Кубик Рубика, дело было бы немного более безнадежным. Когда мы крутим Кубик Рубика, комбинаторика говорит нам следующее:

Я хотел придумать, как бы наглядно объяснить, насколько это много. Как вам такое — если бы все жители Земли смотрели на каждое состояние по 1 секунде, то им понадобилось бы 211 лет, чтобы все пересмотреть*. То есть, чтобы досмотреть до 2010, надо было начинать с 1799 года (представляете, родился Пушкин**, и давай на Кубик глядеть). Но тогда население Земли было меньше, поэтому все равно не успели бы.

^{— То, что может занять 211 человечеств на целый год, можно купить за 30 рублей. Меня это никогда не перестанет поражать.}

Причем тут Бог

Алгоритм Бога — это такой алгоритм, который решает Кубик Рубика за минимальное число ходов. Самое интересное, что никто даже не знает, существует ли этот алгоритм или нет. Это, видимо, единственное, что у них общего с Богом.

Число Бога для Кубика Рубика — минимальное число ходов за которое Алгоритм Бога гарантированно решит любую конфигурацию Кубика. То есть существуют конфигурации, которые Алгоритм Бога решает за 1 ход. Но не сущетсвует таких, на которые он тратит больше ходов, чем Число Бога.

^{— Версия кубика на неодимовых магнитах, которую могут использовать слепые, больные дальтонизмом и очень нетерпеливые (ее легко разобрать). Возможно, никто кроме Бога так и не узнает алгоритм Бога для Кубика Рубика, но играть в него могут почти все. Автор идеи и фотографии — Эндрю Кертис.}

На прошлой неделе несколько исследователей заявили, что они вычислили число Бога.

Число Бога для алгоритма Кубика Рубика — 20. Да, жаль, что не 42.

20 — это довольно обычное число, но в контексте Кубика Рубика нет числа более саркастичного и издевательского. Дело в том, что в Кубике Рубика 20 подвижных деталей. Признайтесь, отчаившись вы хоть раз хотели разобрать Кубик, чтобы потом правильно его собрать и успокоиться? В это время число Бога смеялось над вами!

Ведь деталей-то тоже 20.

Слишком много цифр для одной статьи

Существуют такие конфигурации Кубика Рубика, которые требуют 20 ходов для решения — это стало известно еще в 1995 году. Все, что оставалось доказать исследователям — отсутствие конфигураций, требующих 21 или более ходов для решения.

Что может быть проще, осталось только поперебирать комбинации. Вот как они решили это сделать***:

1. Разбить исходные 43 252 003 274 489 856 000 состояний на 2 217 093 120 подмножеств
2. Сократить число подмножеств до 55 882 296, потому что одни получаются из других поворотами или зеркальными отражениями Кубика
3. Не искать оптимальное решение для каждого состояния, довольствоваться любым не длиннее 20 ходов
4. Написать программу, которая решает одно подмножество за примерно 20 секунд

Пункт 1) очень важен для того, чтобы выполнить пункт 2). Надо быть хитрым лисом, чтобы составить подмножества именно так, чтобы их потом сократить.

Нежелание искать оптимальные пути в пункте 3) тоже не каприз. Они конечно могли бы делать это, но им незачем — они просто хотели проверить, что Число Бога это 20, а не найти все оптимальные пути для всех конфигураций.

Обработав все подмножества, они не нашли ни одного состояния, которое требует 21 или более ходов для решения. А значит доказали — Число Бога для Кубика Рубика равно 20.

Как проверить, что вы все поняли?

Найти Число Бога не значит найти Алгоритм Бога. Если вы понимаете это и согласны, то вы все поняли. Иначе, можете попробовать перечитать определение Алгоритма Бога и Числа Бога.

Как утереть парням нос?

Вы можете обставить их, я не шучу. Для это вам надо придумать алгоритм, который в пункте 3) будет искать только оптимальные ходы. Это и будет Алгоритмом Бога, а вам, вероятно, будут целовать ноги.

Интересные факты по теме

• Конфигурации Кубика, которые требуют 20 ходов для решения, не так уж часто встречаются (примерно 0,0000000007% от общего числа конфигураций). Первая была обнаружена только через 15 лет после появления Кубика на свет. 
  
• Компьютеры решают Кубик Рубика быстрее, чем люди на них смотрят. Для перебора всех вариантов понадобилось 35 ядро-лет. Это значит, что одно ядро одного компьютера, на котором производились вычисления, справилось бы с ними за 35 лет. Сколько ядер было у них в распоряжении, исследователи не сообщают.
  
• Компьютерные мощности для решения задачи предоставила компания  Google, в которой работает один из исследователей.
  

Зачем?

Иногда в конце статей я задаю вопрос — почему? Но сегодня другая история, ведь не совсем понятно, зачем знать число Бога для Кубика Рубика. Если вы думаете, что я сейчас скажу: «Попались!», — пошучу шутку и невзначай расскажу, какую великую пользу принесет это открытие, то вы ошибаетесь. Я не знаю зачем. Но я знаю, что мы можем вынести для себя из всего этого.

На самом деле, мы давно уже это вынесли это для себя — если разбить задачу на подзадачи, то ее решение заметно упрощается. Вся проблема в том, чтобы правильно разбить.

А еще наступают новые времена для науки, когда некоторые вещи становится быстрее проверить, чем доказать. Но об этом я однажды уже писал мельком.

Разделяйте и властвуйте!

^{* — в большом числе одинаковые конфигурации Кубика, повернутые и отраженные, учитываются как разные; а под населением Земли понимается 6,5 миллиардов человек, которые не спят, не едят, а только пялятся на кубики 24 часа в сутки
** — в 1799 году родился самый неоцененный мною писатель Александр Сергеевич Пушкин
*** — пункты «???» и «PROFIT» опущены из-за уважения к читателю}

See you!