Кубик Рубика. За гранями головоломки, или Природа творческой мысли

Один из самых трудных уроков, который усвоил каждый, кто занимался программированием, в том, что, если вы пишете программу и допускаете крошечную ошибку, одну букву, один плюс или минус, система просто перестает работать. Последствия серьезны. То же происходит с Кубом. Если вы нарушите один элемент порядка (я предпочитаю называть это порядком, а не алгоритмом), вы собьетесь с пути. Более того, вы потеряете уже полученные результаты. Вы не только не продвинетесь к цели, но и ухудшите положение, перечеркнув все предыдущие старания. И дальше снова надо начинать с нуля.

Я вижу в программах для Куба особую встречу – настоящей и виртуальной реальностей. Я нашел более 2600 приложений на многих платформах, таких как Linux, Mac, Windows и Android, большинство из которых бесплатные. Весьма интересно наблюдать, как ИТ-специалисты вдохновляются этой задачей. Я представляю миллионы пользователей, которые держат в одной руке смартфон, а в другой – Куб.

Существует 43 252 003 274 489 856 000 (то есть 43 квинтиллиона 252 квадриллиона 3 триллиона 274 миллиарда 489 миллионов 856 тысяч) возможных состояний Куба. Только одно из них является начальным – когда каждая из шести сторон окрашена в свой цвет. Для любой из многочисленных комбинаций существует своя дистанция, измеряемая количеством ходов, движений, вращений или поворотов, выполнение которых приведет к изначальному состоянию Куба. Один такой ход можно использовать как единицу измерения этого расстояния, так же как ярд когда-то стал мерой длины от размера человеческого шага.

Представьте, что вы лежите на траве в прекрасную ясную летнюю ночь и смотрите в небо. Вокруг почти нет источников света, поэтому небо усыпано звездами, которых никогда не увидишь в городе. Случайным образом выберите две из них. Затем в своем воображении попробуйте перенестись с одной на другую. Если ваши звезды находятся рядом, потребуется всего один ход. Если между ними еще одна звезда – два хода. А теперь вам предстоит добраться из одного дальнего конца галактики в другой. Как бы вы начали действовать, чтобы использовать наименьшее количество ходов? В этом вопросе кроется интересная загадка.

Невероятный масштаб задачи не испугал математиков и специалистов в области вычислительной техники. Подобные вызовы лишь вдохновляют тех, кто работает с суперкомпьютерами. Они используют метод так называемой грубой силы, некоторые называют это «доказательством исчерпывания» всевозможных вариантов, сложный математический метод полного перебора возможностей, когда каждая из них разбивается на конечное число других возможностей. Они, в свою очередь, проверяются на предмет выполнения условия.

Благодаря вычислительным мощностям Google и группе математиков наконец было определено наименьшее число ходов, необходимых для сборки Куба из всех возможных его состояний. Их нужно двадцать, на куберском жаргоне – «число Бога» для Куба 3 × 3 × 3.

Еще в июле 1981 года Морвен Тистлетвэйт доказал: чтобы собрать Куб из одного состояния в любое другое, всегда достаточно 52 ходов. Другими словами, никогда не будет двух разных положений Куба, которые потребовали бы для сборки более 52 ходов в любом направлении.

Лет тридцать спустя, в июле 2010 года, программист Томаш Рокицки и его коллеги также заинтересовались решением этой задачи. Они взяли за основу находку другого математика, который разделил сборку Куба на два этапа. Для решения Куб брался в двух уже частично собранных состояниях, так что количество потенциальных ходов измерялось уже не в квинтиллионах, а составляло 19,5 миллиарда. Исследователи обнаружили, что, используя эту стратегию, Куб можно собрать не более чем за тридцать ходов. Рокицки сгруппировал возможные состояния, используя специальный набор частично собранных состояний, и это означало одновременное решение невероятных 19,5 миллиарда конфигураций (что по-прежнему намного меньше 43 квинтиллионов). На своем веб-сайте cube20.org Рокицки сообщил, что «сгруппировал возможные состояния на 2 217 093 120 наборов по 19 508 428 800 состояний в каждом». Решая 2,2 миллиарда задач, а не первоначальные 43 квинтиллиона, и используя мощности суперкомпьютеров Google, Рокицки и его коллеги доказали, что число Бога действительно равно 20. То есть в любое конкретное состояние Куба можно попасть из любого другого состояния не более чем за 20 ходов. Одним ходом считается поворот вокруг одной оси – это может быть либо четверть оборота, либо пол-оборота по часовой стрелке или против часовой стрелки. Если считать ходом только четверть оборота, то это число будет равняться 26.