И снова о кубике
АрхивНаши постоянные читатели наверняка помнят, что почти год назад ("Компьютерра" ##14 и 15 за 1997 год) я уже писал о кубике Рубика. Как ни удивительно, эта когда-то суперпопулярная, а ныне полузабытая головоломка так и не открыла исследователям всех своих тайн, и находятся все новые и новые любители повозиться с кубиком, которые и делают в этой области пусть небольшие, но самые настоящие открытия.
В тех номерах я рассказывал о нескольких направлениях, в которых энтузиасты кубика ведут поиск, - в частности, о так называемом алгоритме Бога и о создании компьютерных программ, способных за небольшое число ходов (поворотов граней) собирать кубик, то есть из любого допустимого положения приводить его в начальное. Оказалось, что я несколько опередил события - именно в прошедшем 1997 году исследователи существенно продвинулись в этом направлении. В частности, сегодня каждый обладатель компьютера с Windows может совершенно свободно сгрузить из Интернета и запустить у себя на машине программу Cube Explorer, которая собирает кубик практически из любого положения не больше чем за 24 хода.
С помощью этой программы можно самому задавать различные узоры на кубике (причем иметь механическую головоломку вовсе не обязательно - вполне достаточно ее изображения на экране). А потом программа расщелкивает ваши узоры как орехи. Начинает с решения, содержащего 26 ходов, затем быстренько находит 25, 23, 20, 18, немного притормаживает, обнаруживает 15 и - после длительного перебора - 14 ходов. Кто сказал, что компьютер бывает умным только против Каспарова? Это неправда. Каждый компьютер имеет такого хозяина, который его заслуживает.
Рисунок 1.
Вот один из примеров того, как Cube Explorer расправляется с очень сложными задачами. На первом рисунке изображен "крест третьего порядка". Это совсем не тот крест, который многие собирают с закрытыми глазами. Здесь - обратите внимание - желтая, синяя и красная грани образуют кресты только желтого, синего и красного цвета, а белая, зеленая и оранжевая грани также меняются крестами друг с другом. Алгоритм сборки такого рисунка, приведенный когда-то в одном из номеров журнала "Наука и жизнь" (кажется, за 1983 год), состоял из тридцати с хвостиком ходов. А теперь решение из 16 ходов находится примерно за 30 секунд счета. Выглядит оно так: L2 R' F D2 L' F' D U' B F' D R F2 D' L R2. Буквами здесь обозначаются грани куба, а цифрами и апострофами - углы, на которые эти грани нужно вращать. R (от слова right, в русской нотации обычно писали П) - правая грань, L (left, по-русски Л) - левая, F (front, Ф) - фасадная, то есть ближняя к нам, B (back, Т) - тыльная, то есть дальняя от нас. Наконец, U (up, В) - верхняя и D (down, Н) - нижняя. Обратите внимание, что буквы обозначают именно положение граней относительно наблюдателя, а не цвета. Кубик можно взять в руки по-разному - и в результате тех же вращений мы получим другой узор. Цифра 2 после буквы означает, что грань нужно повернуть на 180 градусов. Апостроф соответствует повороту на 90 градусов против часовой стрелки. А если после буквы не стоит ни двойка, ни апостроф - грань вращается на 90 градусов по часовой стрелке. Любой из этих трех поворотов в "кубологии" считается одним ходом.
Рисунок 2.
На втором рисунке изображен другой, не менее известный узор. Его традиционное название - "куб внутри куба". Не правда ли, похоже? Хорошо виден один из "кубов внутри куба", но на самом деле их два. Другой находится с противоположной стороны, но грани, его образующие, нарисованы на развертке так, что, лишь обладая хорошим пространственным воображением, можно понять, что три этих квадратика тоже относятся к одному кубу со стороной 2.
Решение этой сложной задачи, оказывается, требует всего 15 ходов! Вот оно: L F L D' B D L2 F2 D' F' R U' R' F2 D. Кстати, если у вас есть не "электронный", а обыкновенный механический (чуть не написал "живой"!) кубик Рубика, но вы давно его не брали в руки, не торопитесь вращать грани в соответствии с этими формулами и любоваться "картинками". Подумайте сначала, сумеете ли вы потом вернуть кубик в исходное состояние? Это не так сложно, как может показаться на первый взгляд. Сообразили, как это сделать? Если еще нет, то вспомните, каким образом Тесей сумел выйти из лабиринта Минотавра.
Рисунок 3.
Третий рисунок может вообще показаться совершенно беспорядочным, но на самом деле это не так. Присмотритесь внимательно: на каждой из шести граней один и тот же узор, правда, нарисованный разными цветами. Чем же замечателен именно этот узор? Скорее всего, почти ничем. Но одна особенность у него все-таки есть. Это один из очень немногих рекордных узоров, с которыми Cube Explorer справляется только за 24 хода и никак не быстрее (R U D2 R' B D' L' F' R F2 U B U' L2 U' L2 B2 L2 U' B2 R2 U B2 U2). Разумеется, это не означает, что к данному узору нельзя прийти за меньшее число ходов - просто алгоритм, заложенный в программе, тоже несовершенен. Полный же перебор всех вариантов состояний кубика Рубика сегодня не под силу не только персоналкам, но и мощным рабочим станциям. Даже если ограничиться только "легальными" состояниями, то есть теми, которые можно получить, не ломая механическую головоломку и не переклеивая на ней цветные наклейки, все равно число состояний кубика имеет тот же порядок, что и ответ в знаменитой древней задаче о награждении изобретателя шахматной игры. Помните эту историю? "На первую клетку, о господин, положи мне одно зернышко пшеницы, на вторую - два зернышка, и так далее, на каждую следующую клади вдвое больше, чем на предыдущую". При таких скромных запросах изобретателя на доске оказывается ни много ни мало, 264-1 зерен пшеницы - намного больше, чем может взрастить вся наша планета за один год.
Впрочем, компьютерная техника вот уже тридцать лет развивается по тому же закону. Скорость вычислений, объем хранимых данных, количество выпущенных компьютеров - все это растет в геометрической прогрессии. И, значит, недалек тот день, когда перебор вариантов порядка 1020 станет таким же обыденным делом, как сейчас - перебор десятков или сотен тысяч. Вот тогда все тайны кубика будут раскрыты полностью. А пока всех желающих приглашаю к открытию. Адрес программы Cube Explorer (текущая версия имеет номер 1.5, объем архива 140 килобайт) - http://home.t-online.de/home/kociemba/cube.htm. Успехов вам в кубоверчении!
Ну и последнее. В Интернете разбросано довольно много страниц, посвященных кубику Рубика и другим аналогичным головоломкам. Увы, среди них нет ни одной русской страницы. Может быть, среди моих читателей найдутся желающие исправить это досадное недоразумение? Пишите мне по адресу kk@knop.spb.ru
