Число Бога — как думает компьютер

43 252 003 274 489 856 000

Столько положений у кубика Рубика — сорок три квинтиллиона. Сделай из каждого положения по кубику обычного размера, 5,7 сантиметра, — и ими можно выложить всю поверхность Земли примерно в 275 слоёв. А если перебирать по одному положению в секунду, работы хватит почти на сто возрастов Вселенной.

И всё же у каждого из них есть кратчайший путь домой. Эта глава — о том, какой он длины и как компьютер его находит, не перебирая всё подряд.

Число Бога

Представь всеведущее существо: глядя на любой кубик, оно сразу видит самое короткое решение. Сколько ходов ему понадобится в самом трудном случае? Это число в шутку назвали числом Бога.

Ответ — 20. Поворот на 180° здесь считается одним ходом. Если считать его за два, выйдет 26 — это доказали позже, в 2014 году.

На кубике — одно из самых трудных положений, суперфлип. Все углы и все рёбра стоят на своих местах, но каждое ребро перевёрнуто. Выглядит почти собранным, а быстрее чем за 20 ходов его не собрать: это доказал Майкл Рид ещё в 1995 году. Вот эти двадцать ходов: U R2 F B R B2 R U2 L B2 R U' D' R2 F R' L B2 U2 F2. Нажми и заметь: тот же алгоритм и запутывает, и распутывает. Суперфлип сам себе обратный.

Лестница Тислтуэйта

Перебрать всё в лоб не выйдет даже у компьютера. Проверяя миллиард положений в секунду, он возился бы почти 1400 лет. Нужна хитрость.

В 1981 году математик Морвен Тислтуэйт придумал спускаться к решению по ступеням. На каждой ступени кубик заводят в «мир», где часть поворотов больше не нужна. Сначала верх и низ разрешено крутить только на 180°. Потом так же перед и зад. Потом вообще все грани — только на 180°. Каждый следующий мир в тысячи, а то и в миллионы раз меньше предыдущего, и искать в нём легче. Четыре ступени — и любой кубик собран не больше чем за 52 хода.

На кубике — последняя ступень. Грани крутят только на 180°, и на каждой видны лишь два цвета: свой и противоположный.

Попробуй сам: шахматка

Загляни в мир последней ступени изнутри. Собери «шахматку» — узор, где на каждой грани клетки чередуются, как на доске. Правило простое: каждую грань повернуть один раз на 180°, а противоположные грани — парой подряд: правую с левой, верх с низом, перед с задом. Порядок пар любой.

Коциемба: две ступени вместо четырёх

В 1992 году Герберт Коциемба сократил лестницу до двух ступеней.

Фаза 1 — навести порядок. Цель — чтобы все детали были правильно повёрнуты, а четыре ребра среднего слоя стояли в среднем слое, пусть и не на своих местах. Со стороны это видно так: верх и низ состоят только из жёлтых и белых наклеек.

На кубике сейчас цветные только жёлтые и белые наклейки, и они разбросаны по всем граням. Нажми B' L U' R F' — всего пять ходов, и все они соберутся наверху и внизу. Вперемешку, но на своих гранях.

Зачем это? Из такого положения кубик можно собрать, не выходя из «мира»: крутя только верх и низ и остальные грани на 180°. Положений в этом мире около 19,5 миллиарда. Много, но по сравнению с сорока тремя квинтиллионами — горстка.

Фаза 2 и таблицы-подсказки

Фаза 2 — расставить по местам. Дальше в ходу только разрешённые повороты, поэтому порядок из первой фазы уже не разрушится. Осталось переставить детали: U2 F2 D2 R2 U L2 B2 D R2 F2 U'. Посмотри: ни одного поворота боковой грани на 90°.

Как компьютер находит эти ходы? Он перебирает, но с умом. Ещё до поиска он составляет таблицы-подсказки: для каждого «упрощённого» состояния — например, если смотреть только на то, как повёрнуты углы, — записано наименьшее число ходов, за которое его можно исправить. Это как навигатор, который знает: до дома не меньше пяти километров по прямой. Если в запасе три хода, а таблица говорит «нужно хотя бы пять», ветку можно бросать, не заглядывая глубже. Так отсекаются почти все пути.

Первое найденное решение бывает длинноватым. Но программа на этом не останавливается: пробует фазу 1 чуть длиннее, чтобы фаза 2 стала короче, и за секунду-другую спускается к решениям около 20 ходов. Не всегда к самому короткому, но почти всегда к близкому.

Как доказали двадцать

Число Бога искали тридцать лет. В 1981 году знали, что хватит 52 ходов, к 2008-му — 22. Снизу границу подпирал подсчёт: различных цепочек до 17 ходов, если выкинуть заведомо лишние вроде R R', меньше, чем положений кубика. Значит, некоторым положениям нужно хотя бы 18. Суперфлип поднял эту планку до 20. Оставалось сомкнуть.

В июле 2010 года это сделали Томас Рокицки, Герберт Коциемба — тот самый, — Морли Дэвидсон и Джон Детридж. Они разбили все положения на 2,2 миллиарда групп по 19,5 миллиарда — каждая группа устроена как мир из второй фазы. Симметрии кубика и ещё пара хитростей сократили работу до 56 миллионов групп, и каждую программа проходила примерно за 20 секунд. Всего ушло около 35 лет процессорного времени — его пожертвовала Google. Итог: ни одному положению не нужно больше 20 ходов.

Сколько раз повторить

Кубик — ещё и учебник теории групп. Любой алгоритм, если повторять его снова и снова, рано или поздно вернёт кубик в исходное положение. Положений конечное число, так что когда-нибудь кубик попадёт туда, где уже был. А раз каждый ход можно отменить, первым повторится именно начало. Число повторов до возвращения называют порядком. Пиф-паф, как ты помнишь, возвращается за 6 раз.

А у простенького R U порядок — 105. Почему так много? Семь рёбер ходят по одному кругу — им нужно 7 повторов. Пять углов тоже ходят по кругу, но возвращаются повёрнутыми, и им нужно 15. А ещё один угол просто крутится на месте — ему хватает 3. Всё сойдётся, когда число повторов разделится и на 7, и на 15, и на 3. Впервые это случается на 105-м.

По дороге бывают чудеса. На кубике — R U, повторённый 35 раз: все рёбра дома, а шесть углов стоят на своих местах, но повёрнуты. После 15 повторов — наоборот: углы дома, а семь рёбер переставлены. Самый большой порядок у кубика — 1260: есть цепочка всего из пяти ходов, которую нужно повторить 1260 раз, чтобы вернуться.

Попробуй сам: думай с конца

Этот кубик запутали всего тремя ходами. Попробуй собрать его тоже за три. Подсказка: думай, как компьютер, с конца. Какой слой повернули последним? Его и раскрути первым.

Три решения одного кубика

На странице «Собрать мой кубик» можно ввести свой кубик и увидеть три решения рядом. Для новичка — послойное, 100–150 ходов, и каждый шаг знаком тебе по этому учебнику. Как у спидкуберов — CFOP, около 60 ходов. И компьютерное — по Коциембе, около двадцати.

Сравни их на одном кубике. Человеческие решения длинные, но понятные: видно, что и зачем собирается. Компьютерное короткое и загадочное: кубик почти до последних ходов выглядит перемешанным, а потом складывается разом. В этом разница между «понять» и «найти» — и хорошо уметь и то, и другое.