9 сентября 2010 в 00:56

Кубик Рубика за 20 шагов перевод

Любая позиция Кубика Рубика может быть решена не более, чем за 20 шагов.

Несколько лет назад было доказано, что для Кубика Рубика есть решение за 23 хода. Теперь это число сократилось до 20. Чтобы это сделать, потребовалось 35 (тридцать пять) лет компьютерного времени, пожертвованного Гуглом.


Каждый блок решения использовал свой алгоритм — последовательность шагов для достижения нужной конфигурации. Например, один алгоритм предназначался для решения верхней грани, а другой — для позиционирования средних краев. Есть множество различных алгоритмов, различающихся по степени сложности и количеству требуемых шагов, но те, которые может запомнить человек, обычно требуют больше 40 шагов.

Разумно полагать, что Бог может использовать более эффективный алгоритм, который решает задачу за наикратчайшее число шагов. Этот алгоритм известен как “алгоритм Бога”. Число шагов в худшем случае называется числом Бога. В конце концов, было показано, что это число — 20.

После изобретения Кубика Рубика пятнадцать лет ушло на поиск позиции, которая наверняка решается за 20 шагов. Через 15 лет после этого мы докажем, что 20 шагов достаточно для любой позиции.

История числа Бога


К 1980 году было установлено, нижняя граница — 18, а верхняя — вероятно, около 80. В таблице ниже собраны все результаты:


Как мы это сделали



Как мы справились с 43 252 003 274 489 856 000 позициями Кубика Рубика?
  • Мы разделили все позиции на 2 217 093 120 множеств — по 19 508 428 800 позиций в каждом.
  • Мы уменьшили число множеств для решения до 55 888 296 на основе симметрии и покрытии множества.
  • Мы не искали оптимальное решение, а только решения с длиной 20 или менее шагов.
  • Мы написали программу, находящее решение для одного множества за 20 секунд.
  • Потребовалось 35 лет компьютерного времени для поиска решений всех конфигураций в каждом из 55 888 296 множеств.


Деление пространства позиций


Мы разбили большую задачу на 2 217 093 120 меньших подзадач: в каждую входило по 19,508,428,800 различных позиций. Одна такая подзадача легко помещается в память современного компьютера, и этот метод позволил достаточно быстро получить решение.

Симметрия


Если повертеть Кубик Рубика влево-вправо или вверх-вниз, то, по сути, ничего не изменится: число шагов в решении останется тем же самым. Вместо того, чтобы решать все эти позиции, можно получить решение для одной и распространить его на повернутые позиции. Есть 24 различных ориентации в пространстве и 2 зеркальных положения Кубика для каждой позиции, что позволяет уменьшить число решаемых позиций в 48 раз. Если использовать аналогичные рассуждения и воспользоваться поиском задачи “покрытия множества”, то число подзадач уменьшается от 2 217 093 120 до 55 882 296.

Хорошие и оптимальные решения


Оптимальное решение содержит достаточное количество шагов, но не больше, чем надо. Так как уже известна одна позиция, для которой требуется 20 шагов, то мы можем не искать оптимальное решение для каждой позиции, а только решения в 20 или менее шагов. Это многократно убыстряет задачу.

Оборудование


У нас была возможность решить 55 882 296 подзадач на мощностях Гугла и выполнить все вычисления за несколько недель. Гугл не раскрывает характеристики компьютеров, но было затрачено 1.1 миллиард секунд компьютерного времени (Intel Nehalem, four-core, 2.8GHz) на выполнение расчетов.

Самая трудная позииция



Мы знали в течении 15 лет, что есть позиции, которые требует 20 шагов, но мы доказали, что ни для одной позиции и не надо больше.

Позиции с решениями в 20 шагов редки, но их вполне возможно встретить в реальности. Вероятность встретить такую позицию варьируется от 10^(-9) до 10^(-8). Мы точно не знаем точное количество таких позиций. Таблица дает оценку числа позиций для каждой длины решения.


Для длин от 16 и больше, числа являются примерными. Наши исследования подтвердили все первоначальные данные до 14 строки включительно, а 15 строка — новый результат. На 11 августа мы обнаружили 12 миллионов позиций с длиной решения 20. Эта позиция была самой сложной для наших программ:

Перевод: Tomas Rokicki
hodik @hodik
карма
80,5
рейтинг 0,0
Похожие публикации
Самое читаемое Разработка

Комментарии (94)

  • +8
    Как бы в мозг такую программу занести :)
    • –1
      Может туда надо поставить операционку CrackOS? :)
      • +1
        Она, наверное, для хакеров :)
        • +1
          Она, наверное, для тех, кто может в уме решить Кубик Рубика :)
          • +21
            Анатолий Вассерман прежде чем досчитать до бесконечности дважды решил Кубик Рубика в уме
            • +9
              А при виде Чака Нориса кубик Рубика решает себя сам
      • 0
        А можно рассказать как в такую позицию кубик запутать? )))
    • +3
      имплантировать Intel Nehalem, four-core, 2.8GHz и 35 лет думать? :)
      • 0
        Быстрее изобретут еще более быстрые технологии )
        Нужно алгоритм, который будет спокойно портироваться на новое железо — тогда получим существенное ускорение.
    • +5
      В ваш мозг природа уже заложила программы покруче :)
  • –9
    Раза 3 собирал кубик рубика за всю жизнь, и то когда совершено нечем было заняться.
    • +4
      А у маленьких детей развивает моторику.
      • +30
        и смекалку…
        и заодно учит пользоваться клеем…
  • +5
    Кстати, когда увидел количество комбинаций, вспомнилось:

    eg.ru/daily/melochi/11995/
    • +2
      ага, но никто ведь не трубит про «рубикозависимость»?)) геймеры были всегда, игры только меняются
  • +4
    Всегда мог собрать кубика, но никогда ничего не понимал в математике. :(
    Странная штука, но меня всегда радовала, что бы расслабить мозги, всегда есть под рукой.
    • 0
      недавно тоже хотел купить, посмотрел в магазинах — везде китайское говно! помню советские были круты — именно механизм, а то что делают сейчас — даже покупать не хочется… :-(
      • –1
        Кстати, вот на этой картинке: assets2.lookatme.ru/1281808210/assets/article_image-image/d4/cd/1046663/article_image-image-article.jpg показан лучший на сегодняшний день кубик массового производства.

        Рекомендую именно такой!
        • 0
          к сожалению по картинке не виден производитель и где его заказать можно :-(
        • 0
          Извиняюсь… нашел вроде :)
        • 0
          почитал отзывы про этот кубик — если это лучшее из того что есть на рынке, то лучше поискать старый советский… обидно :-(
          • 0
            У меня 3 советских кубика, из них нормально крутить можно лишь один. Новый китайский за 200 рублей крутится ещё лучше.
            Всё-таки очарование кубика не в идеальной механике вращения, а в огромной сложности решения при элементарной формулировке задачи.
            Сейчас можно купить любые кубики от 3*3*3 до 7*7*7, и качество вращения будет достаточным, чтобы не отвлекаться на механику, а сосредоточиться на логике решения.
            А на e-bay даже 11*11*11 кажется есть, но там уже скорее всего качество сборки не ахти.
            • +2
              >Сейчас можно купить любые кубики от 3*3*3 до 7*7*7...

              От 2*2*2 ;)
        • 0
          Rubics — отстойные кубики.
          Лучшие, что я видел (да и по отзывам) — https://v-cubes.com, но там только большие.
          А маленькие (3х3) — у меня с детства чехословатский еще… Лучше не видел!
        • +1
          Зря рекомендуете. Это хреновый кубик, хоть и стоит немало.

          Те самые советские (а точнее венгерские) кубики производит до сих пор rubik's studio.
          На ebay я их видел как-то. Выглядит это так:


          Ну а если хочется спид кубик, то www.cube4you.com/
          • 0
            О как. Может это подделки уже пошли. Крутил 2 «рубикса» (один в РФ покупал, другой из Италии был). Все отлично было. Приятная механика, все смазано, даже одной рукой крутить в удовольствие.
            • 0
              У рубикса есть достойный кубик. Но не тот, что на картинке. А в speed-cube наборе. Там и смазка в комплекте и наклейки дополнительные. Вот он очень Достойно крутится
        • 0
          Это ужасный кубик, крутится как попало, смазывать особо не помогает. Из того, что продаётся в магазинах, можно взять разве что спидкуберский от Rubik's (вроде такого). Но вообще рекомендуют в Китае заказывать, там сейчас правильные кубики делают.
      • +2
        Я вот этот купил — www.dealextreme.com/details.dx/sku.16433 — вполне приличный, мне нравится. С тем, что на картинке и прочими спид- и спорт- не сравнивал. Приходит в разобранном виде с двумя комплектами наклеек. И собрать самому прикольно и клеить. Центральные кубики подпружинены. С китайскими из магазина не сравним вообще — у меня китайский есть для убиения младшим ребёнком, тк я не всегда его могу покрутить даже :). Даже с советскими не сравним (советские у меня были — хороши, но не круты — центры были без пружинок). Сравним с оригинальными венгерскими, времён, когда они только появились.
  • НЛО прилетело и опубликовало эту надпись здесь
    • 0
      Один из членов команды работает в Гугле, поэтому, наверно, было проще договориться с Гуглом о предоставлении процессорного времени.
  • +6
    А я только одну грань могу собрать…
    • +2
      По слоям надо собирать, так легче :)
      А я вот третий слой не могу сообразить как собрать.
      • +9
        интересно как можно рекомендовать способ решения, если сам не можешь его реализовать?
      • +1
        Если собирать, руководствуясь логикой и с минимумом зазубривания — вот хороший способ.
      • 0
  • –5
    Последняя пикча больше смахивает на таблицу опыта в LA2.
  • 0
    в детстве както попала мне в руки табличка как вертеть кубик чтобы он собрался 100%, жаль не помню за сколько там было шагов. с другом тогда ее выучили и выделывались в школе — собирая кубик за минуту с закрытыми глазами из любого положения. правда к самой головоломке интерес тогда пропал:(
    • 0
      интересно, что же это за алгоритм, который позволяет решить кубик из любой позиции одними и теми же действиями, да еще и за минуту? :D
      • –1
        к сожалению саму последовательность уже не помню — прошло почти 15 лет, но ничего сложного в ней не было. просто последовательность какую линию и в какую сторону поворачивать и кубик собирался. спрошу сегодня у друга возможно у него остались зарисовки с детства:)
        • 0
          вас обманули :)
      • +1
        Действия, очевидно, одни и те же для конкретных «фишек», а не в целом для всего кубика из любой позы :) Сначала собирается одна грань и прилегающий к ней слой, для этого нужно уметь две фишки — не ломая собираемую грань подставлять нужный цвет в центр и в угол. При сборке средней грани нужно уметь тоже две фишки — вставлять нужный цвет «на ребро» и разворачивать уже стоящий на нужном месте, но с перепутанными цветами. Для нижней грани уже целых четыре фишки, их описывать не буду, т.к. будет слишком непонятно, а иллюстрации мне что-то правильной сейчас не найти :)

        Главное, что алгоритм эффективен и всегда срабатывает. Самое страшное было на последних этапах случайно перепутать последовательность — сразу весь кубик превращался в кашу, а назад отмотать уже было почти нереально и приходилось собирать опять почти с самого начала :)
    • +1
      Предполагаю, что это был алгоритм не сборки из любой позиции, а вращения собранного кубика так, что он сперва эффектно запутывается, а затем аналогично распутывается.
      • 0
        нет, запутывать моджно было как угодно. но кажется я всетаки приврал, он собирался не с любого положения — сначала нужно было вручную собрать белую грань(но это легко и быстро), а потом уже последовательность поворотов для полной сборки.
        • –1
          а почему именно белую? :) разве цвет имеет значение?
          • 0
            нет не имеет:) просто такая была привычка.
        • 0
          И всё-таки в «слепой» алгоритм без ветвлений if(...){...} я не верю. Судя по статье, типичный алгоритм с ветвлениями, когда решения принимаются исходя из реального положения кубиков на местах, занимает 40+ ходов. Если даже предположить, что существует последовательность поворотов, которая собирает кубик для любого положения кубиков в двух слоях (а это огромное количество вариантов), то длина такой последовательности должна быть колоссальна.
          • +1
            ну не может быть такой последовательности вращений, которая приводила бы к одному результату из всех возможных позиций. то, что одна из сторон кубика собрана, лишь уменьшает возможное количество комбинаций.
            вот алгоритм запутывания и распутывания — да. те же самые «четверки», например.
            • +1
              Математически, такая последовательность есть. :) Она включает в себя последовательно все решения для всех 43 252 003 274 489 856 000 возможных начальных позиций. Первые X вращений будут для одной возможной позиции; если кубик не собрался, крутим следующие Y поворотов для следующей возможной позиции (с учетом того, как она видоизменилась после первых X поворотов), и т.д. На каком-нибудь шаге кубик соберется.
              Но на листочке такую последовательность не запишешь, это да. :)
            • 0
              вот еще вариант сборки в пдфке www.rubiks.ru/PDF/cubcls_hnt_RUS.pdf, а то в статье из моего комента выше картинка маленькая — ненаглядная.
          • 0
            вот кажется нагуглил notsecret.ru/other/othersecret/236-kak-sobrat-kubik-rubik.html правда не уверен на 100% что это именно тот алгоритм, но делает он тоже самое и вполне запоминаем. там в статье кстати написано о существовании 30+ разных алгоритмов сборки.
            • 0
              Это один из типичных алгоритмов, со знакомыми иллюстрациями из журнала «Наука и жизнь» 80-x годов. Наверняка он работает, и его можно запомнить. Я собираю похожим.
              Но это не «слепая» последовательность, а алгоритм с условными ветвлениями. Короче, с закрытыми глазами не соберешь, на кубик надо смотреть. :)
  • НЛО прилетело и опубликовало эту надпись здесь
  • +1
    Получается для получения просчета всех вариаций на минимальные им пришлось брутить, значит в ближайшее время можно будет ждать анализа решений для получения оптимального алгоритма. Алгоритмы решений то есть давно, интересно будут ли они подтверждены как оптимальные.
    • –1
      Вопрос, что считать оптимальным?
      В статье же написано, что те алгоритмы, которые реально запомнить позволяют собрать кубик за 40 ходов. Лично мне 100++ паттернов и формул к ним запоминать сомнительное удовольствие. С минимальным количеством формул можно собрать примерно за 200 ходов.
      • 0
        Я верю в способности человека :) Пусть может подвести память, но остается еще логика и интуиция
  • НЛО прилетело и опубликовало эту надпись здесь
  • +2
    В самом первом предложении ошибка. Менее, чем за 20 шагов — это не то же самое, что «не более, чем за 20 шагов».
  • +2
    «В течении» также режет глаз. Исправьте, пожалуйста.
  • 0
    «потребовалось 35 (тридцать пять) лет компьютерного времени, пожертвованного Гуглом.» — это как?
    • +1
      «но было затрачено 1.1 миллиард секунд компьютерного времени (Intel Nehalem, four-core, 2.8GHz) на выполнение расчетов.»
      процессор Intel Nehalem, four-core, 2.8GHz за секунду выполняет примерно 1 триллион операций с плавающей точкой (точно не помню), для решения поставленной задачи, то есть решения всех логических операций этому процессору потребуется 1.1 миллиард секунд, следовательно один такой процессор будет решать задачу в течении 35 лет. Но т.к. Google имеет при себе огромные распределённые вычислительные мощности, то выделив их «малую часть» они потратили несколько недель на решение данной задачи.
      • –1
        Давайте относительно обезьян с счетами посчитаем, что гугл пожертвовал хер знает сколько много лярдов лет. Ну и пояснение в скобках для тех кто не знает цифр тоже радует, видимо для гуманитариев.
        • НЛО прилетело и опубликовало эту надпись здесь
          • –2
            Зачем вообще его масштабировать, популистики ради?
            • НЛО прилетело и опубликовало эту надпись здесь
  • 0
    Собираю по стародедовским алгоритмам, их запомнить реально:-)
  • +4
    вкратце уже выкладывали
    habrahabr.ru/blogs/popular_science/101361/
  • 0
    «но их вполне реально встретить в реальности» -> «но их вполне возможно встретить в реальности»
  • 0
    >> Intel Nehalem, four-core, 2.8GHz
    Может, вместо «four-core» — «quad»?
    • 0
      Взято из оригинала.
  • 0
    >hodik
    Вы принимали участие изи это перевод?
    • 0
      Не понял ваш вопрос.
  • 0
    Понял, что доказано, что из любой начальной конфигурации можно собрать КР не более, чем за 20 шагов.
    Доказано ли, что существуют конфигурации, из которых нельзя собрать КР меньше, чем за 20 шагов, или гонка продолжится?
    • 0
      Упс, в табличке есть :)
  • 0
    Один парень написал новость об этом для модников — подача немного отличается :-) www.lookatme.ru/flows/42/posts/102651-holy-cube
  • –6
    о каких 35 годах идет речь? Гугл основан в 1998 году.
    Кто-то конечно потратил 35 лет, но точно не они.

    Брину 35 лет назад было всего 2 года.
    • 0
      1.1 миллиард секунд компьютерного времени из расчета на Intel Nehalem, four-core, 2.8GHz, а расчет производился явно на другом железе, соответственно его значительно сократили.
    • 0
      имеется в виду количество завтраченного процессорного времени, т.е. сколько прошло бы лет, если бы процессор был всего один и все время убил бы на решение этой задачи.
      но гугл обладает целым парком машин, поэтому тысяча машин, при распределенных вычислениях, способы потратить суммарно 35 лет процессорного времени за пару недель
    • +1
      Очевидно, когда автор писал «Потребовалось 35 лет компьютерного времени...» он не ошибся, и речь идет именно о компьютерном времени. :)
      Т.е. если предположить, что у Гугла есть ВСЕГО ОДИН компьютер, то тогда ваши слова, разумеется, обоснованы! ;)
    • +1
      Вы чувствуете разницу между компьютерным временем и _реальным_?
  • 0
    Люблю Кубик Рубика!
    Отлично расслабляет мозг.
  • +2
    Согласно Путеводителю для путешествующих по Галактике, сверхразумная раса существ создала компьютер Deep Thought — второй по производительности за всё существование времени и Вселенной, — чтобы найти Окончательный Ответ на величайший вопрос Жизни, Вселенной и Всего Такого. После семи с половиной миллионов лет вычислений, Deep Thought выдал ответ: «Сорок два». Реакция была такой:
    — Сорок два! — взвизгнул Лунккуоол. — И это всё, что ты можешь сказать после семи с половиной миллионов лет работы?
  • +6
    В русскоязычной литературе это переводится не «компьютерное время», а «машинное время».
  • –3
    »Чтобы это сделать, потребовалось 35 (тридцать пять) лет компьютерного времени, пожертвованного Гуглом.

    Как же меня вымораживает, когда говорят о времени, используя машинное исчисление, кто бы знал. Как будто это для кого-то имеет значение. Нет, я понимаю, когда говорят «Для этого потребовался мейнстрим на тысячу процессоров в 5 Ггц.» Но вот эти извращения с попугаями ничем как извращение с попугаями более не являются. Но это исключительно моё имхо.
    • 0
      В статье указан тип процессора, читайте внимательно. Общее впечатление можно составить.
      Соглашусь, что есть еще много характеристик, которые оказывают существенное влияние на скорость, таких как объем оперативной памяти, её скоростные характеристики, скорость доступа к внешней памяти и пр. пр.
  • +1
    >Любая позиция Кубика Рубика может быть решена менее, чем за 20 шагов.
    не более чем за 20 шагов.
  • 0
    После изобретения Кубика Рубика пятнадцать лет ушло на поиск позиции, которая наверняка решается за 20 шагов.

    Кажется, с этой фразой что-то не так. Может, «не менее, чем за 20 ходов»?
  • 0
    Что значит «35 лет компьютерного времени»?
    • 0
      Думаю вот что:
      К примеру, было 35 компьютеров, которые работали год без перерывов.
  • 0
    Где в Самаре можно купить более менее нормальный кубик?
  • 0
    Надо было немного аккуратней выбирать формы текста, а то звучит немного нелепо:
    Silviu Radu показал, что всегда хватит 28 шагов, Silviu Radu улучшил его результат до 27 шагов.
  • 0
    А еще проще не мучатся, а взять замазку белую 6 разноцветных маркиров. И тогда из любой позиции можно решить буквально за 54 хода, учетом 20 секунд на ход. Итого за 18 минут можно собрать 100%

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.