В прошлый раз мы остановились на том, что задача перебора всех возможных состояний кубика Рубика намного превосходит возможности современных компьютеров. Но... находились и находятся программисты-безумцы, которых эти трудности не останавливают.
Одним из первых, кто привлек компьютер к исследованию кубика Рубика, был лондонец Марвин Тистлетуэйт (Morwen Thistletwaite). На самой заре кубологии - в 1980 году - он предложил совершенно новую идею алгоритма сборки. Для того, чтобы ее изложить, мне придется еще раз немножко углубиться в кубологию.
Общепринятой среди кубологов является буквенная система записи поворотов. Независимо от расцветок, грани куба обозначаются следующим образом: В - верхняя грань, Н - нижняя, Ф - фасадная, Т - тыловая, П - правая, Л - левая. (Такая система сложилась в литературе на русском языке, а международная система отличается от нее тем, что используются первые буквы английских слов Up, Down, Front, Back, Right, Left). При повороте грани на 180 градусов после буквы ставится степень 2, а если грань вращается на 270 градусов по часовой стрелке (или на 90 против часовой, что то же самое) - то после буквы ставится апостроф или степень 3.
Алгоритм Тистлетуэйта разбивает весь процесс сборки куба на 4 таких этапа:
Первый этап: разрешены любые вращения граней, то есть все повороты из множества { В Н П Л Ф Т }. Цель этапа: достичь любой позиции, принадлежащей первому классу промежуточных состояний куба.
Второй этап: грани Ф,Т,П,Л по-прежнему можно поворачивать как угодно, а грани В и Н - только на 180 градусов. Множество разрешенных поворотов - { В^2 Н^2 П Л Ф Т }. Цель этапа: попасть во второй класс промежуточных состояний.
Третий этап: Ф и Т вращаются как угодно, а остальные грани - только на 180 градусов: { В^2 Н^2 П^2 Л^2 Ф Т }. Цель этапа: придти к третьему промежуточному классу.
Наконец, четвертый этап: используя только повороты граней на 180 градусов, то есть операциями из множества { В^2 Н^2 П^2 Л^2 Ф^2 Т^2 }, собрать куб полностью.
Упомянутые классы промежуточных состояний определяются путем вычисления определенных характеристик этих состояний. Эти характеристики, сохраняющиеся при любых разрешенных действиях, математики называют инвариантами. Каждый класс соответствует своему набору инвариантов и их значений.
М.Тистлетуэйт, проделав весьма кропотливую работу по перебору алгоритмов, показал, что для первого этапа всегда достаточно 7 ходов, для второго - 13, для третьего - 15, а для четвертого - 17. Итого весь алгоритм требует не более чем 52 хода. Этот результат был намного лучше, чем могли в то время дать все остальные алгоритмы сборки кубика. У него был один-единственный "недостаток": он никак не помогал собрать кубик вручную.
В Голландии существует клуб любителей кубика Рубика, который имеет свое периодическое издание - газету "Cubism For Fun". Она выходит несколько раз в год, без какой-либо регулярности, и рассылается всем членам этого клуба.
Через много лет после того, как прошел пик интереса к кубику Рубика, а точнее, в 1992 году, в 28-м номере "Cubism For Fun" появилось сообщение математика Герберта Коцембы (Herbert Kociemba) из университета города Дармштадта (Германия). Он писал о разработанном им принципиально новом алгоритме сборки кубика, дающем воистину удивительные результаты: из любого начального положения его программе удается произвести сборку кубика не больше, чем за 20 ходов!
Собственно, идею Коцембы еще в меньшей степени, чем алгоритм Тистлетуэйта, можно назвать "алгоритмом сборки" в привычном для нас смысле этого слова. Реализовать этот алгоритм способен только достаточно быстрый компьютер с большой оперативной памятью. Однако сама идея довольно проста.
Вся сборка кубика разбивается на 2 этапа. На первом этапе допускаются любые повороты граней. Единственной целью первого этапа является приведение кубика в некоторое "промежуточное" состояние. Как только кубик после некоторого числа поворотов оказался в промежуточном состоянии, начинается второй этап. В этом этапе используются уже не все возможные повороты граней, а только такие, которые не выводят кубик из класса промежуточных состояний. Конечное состояние (полностью собранный кубик) также принадлежит этому классу, поэтому рано или поздно оно будет найдено обыкновенным перебором вариантов.
Если суммарное число ходов, затраченных на первый и второй этап, больше 21, то программа возвращается к первому этапу и берет следующее промежуточное состояние. Экономия перебора, получаемая благодаря этой идее, колоссальна: на первом этапе рассматривается примерно 2.2*10^9 вариантов, а на втором - 19.5*10^9 вариантов. Итого программа должна просмотреть около 22*10^9 вариантов, а это число на 9 порядков меньше, чем общее количество состояний куба.
У способа Коцембы и алгоритма Тистлетуэйта есть много общего. Например, оба они используют такое понятие, как класс промежуточного состояний. При этом "промежуточные состояния Коцембы" практически совпадают со "вторым классом промежуточных состояний" Тистлетуэйта. Разница только в системе обозначений - на втором этапе Коцемба разрешает произвольные вращения В и Н, и повороты на 180 остальных граней, а Тистлетуайт на своем третьем этапе оставлял для произвольных вращений грани Ф и Т. Иначе говоря, первый этап способа Коцембы соответствует двум первым этапам алгоритма Тистлетуэйта, а второй этап - двум последним. Различия между этими алгоритмами не столь заметны, но более принципиальны. А именно, Тистлетуэйт получил конкретные наборы операций и привел строгие математические доказательства, обосновывающие указанные им длины каждого этапа. А Герберт Коцемба, не утруждая себя никакими обоснованиями, просто бросил вызов всем любителям: можете присылать мне все те задачки, которые у вас не получаются, и моя программа справится с ними за 20 ходов!
Реально программа Коцембы немного сложнее, чем это описано выше. Она не делает полного перебора вариантов ни на одном из своих этапов. Вместо этого она тратит некоторое время на создание специальных фильтров: огромных массивов, содержащих списки состояний, из которых можно достичь конечного (для этого этапа) состояния за определенное число ходов (от 1 до 8). Начав сборку кубика, программа пытается выполнить первый этап за 10 ходов. Она делает первые два хода и смотрит массив-фильтр на 8 ходов. Если состояние не отсеется, то делается третий ход и просматривается фильтр на 7 ходов и т.д. В противном случае делается другой второй ход. Точно по такой же схеме выполняется и второй этап сборки - на него программа Коцембы отводит не более 14 ходов.
Сообщение Коцембы неоднократно перепроверялось и уточнялось другими специалистами по кубологии. В результате оказалось, что для обоих этапов оценки, количества ходов, приведенные Коцембой, чересчур оптимистичны: существуют начальные позиции, из которых нельзя закончить первый этап быстрее чем за 12 ходов, кроме того, существуют состояния из "промежуточного" класса, от которых нельзя перейти к собранному кубику быстрее чем за 18 ходов. Приведенные числа 12 и 18 - это точные границы: последователям Коцембы удалось произвести полный перебор для 1-го и 2-го этапов. Таким образом, доказано, что алгоритм Бога имеет длину не более 30 ходов.
А как же гарантированные Коцембой 20 ходов из любой начальной позиции?
Увы, этот эмпирический факт пока никому опровергнуть не удалось. (Чтобы
его опровергнуть, нужно привести начальную позицию, с которой программа
Коцембы не справилась бы быстрее чем за 21 ход). Таким образом,
на сегодняшний день доподлинно известно следующее:
- существуют начальные состояния, из которых нужно сделать 18 ходов;
- доказано, что для любого начального состояния кубика хватает 30 ходов;
- для всех проверенных состояний программа находит решение не более
чем из 20 ходов.
А это значит, что головоломка Рубика так и не раскрыла пока своих тайн.
При подготовке данной статьи я использовал архивные материалы клуба любителей кубика Рубика (cube-lovers@ai.mit.edu). Они доступны по ftp и находятся по адресу ftp://ftp.ai.mit.edu/pub/cube-lovers. Кстати, переписка между любителями головоломок продолжается в этом электронном клубе и поныне. Если Вы заинтересовались этим и хотите получать корреспонденцию клуба, напишите письмо-просьбу (на английском языке) и отправьте его по адресу cube-lovers-request@ai.mit.edu.
Одна из программ, реализующих алгоритм Коцембы, написана голландцем Диком Винтером (dik@cwi.nl). Ее архивная версия называется cube.tar.Z и находится по адресу ftp://ftp.cwi.nl/pub/dik (Внимание! После получения этой программы для ее разархивирования Вам понадобятся gzip и tar, а для запуска - компилятор C.)
Некоторые другие программы для любителей подобных головоломок (в частности, программу xrubik, написанную Дэвидом Бэгли - кубик Рубика размером NxNxN) можно найти на ftp://ftp.x.org/contrib/games/xpuzzles
Более подробному описанию алгоритма Коцембы посвящена статья В.Н.Дубровского и А.Т.Калинина в журнале "Квант" #11/1992.
Если Вас заинтересовала эта статья и у Вас есть какие-то свои
соображения на эту тему - пишите мне по адресу
kk@knop.spb.ru.
© Константин Кноп, 1997-98. All rights reserved.
В будущем я планирую опубликовать здесь все написанные
мною статьи, включая те, которых не было на сайте
"Компьютерры". Ваши пожелания пишите по адресу
kknop@oocities.com
Вы
-й посетитель этой странички.
Get your own Free Home Page