Количество возможных состояний кубика Рубика

·

По какому алгоритму рассчитывается количество возможных состояний кубика Рубика N * N?

размер 360*328, 13.09 kb

GD Star Rating
loading...
Количество возможных состояний кубика Рубика, 10.0 out of 10 based on 1 rating

похожие публикации

  1. Вычислите количество соударений
  2. Комбинаторные проблемы
Tagged with → •  

    7 Responses to Количество возможных состояний кубика Рубика

    1. Peels:
      05/10/2009 в 11:25

      Ну давай посчитаем. Будем делать так, разберем кубик на детали и посмотрим сколькими способами его можно собрать обратно.
      Пусть N четное.
      Кубик NxNxN состоит из:
      1) 8 угловых подкубиков, каждый из которых встает на одно из 8 мест одним из 3х способов.
      2) Реберные подкубики. Они бывают (N–2)/2 типов (по расстоянию от угла). Каждого типа имеется 2*12 кубиков, каждый из которых встает на одно из 2*12 мест одним из 2–х способов.
      3) Остальные («граневые») подкубики. Они бывают (N–2)*(N–2)/4 типов (по положению от угла).
      Каждого типа имеется 6*4 кубиков, каждый из которых встает на одно из 6*4 мест одним способом.

      Итого имеем (8!*3*(24!*2)^((N–2)/2)*(24!)^((N–2)(N–2)/4)) способов собрать сломанный кубик.
      Теперь возникает вопрос, как пространство «собранных» кубиков делится на связные компоненты касательно операций с кубиком (другими словами, если я соберу кубик по кусочкам случайным образом, смогу ли я потом вращая его привести его к «правильной раскраске»). Детский опыт с кубиком 3х3х3 подсказывает что связных компонент две, поэтому собрав кубик из кусочков случайным образом ты лишь в половине случаев получишь конфигурацию, из которой можно вернуться к «правильной раскраске». Кубик 4*4*4 мне менее понятен. С одной стороны, его как будто можно всегда собрать. С другой стороны, у него по раскраске невозможно отличить две конфигурации, различающиеся лишь перестановкой двух соседних реберных подкубиков. Для простоты предположим что у любого кубика рубика всегда две связные компоненты.

      Тогда получаем ответ (8!*3*(24!*2)^((N–2)/2)*(24!)^((N–2)(N–2)/4))/2

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

      Еще можно пытаться посчитать с учетом изоморфизма относительно поворотов и отражений, для этого есть одна клевая теорема, но там будет чуть другой ход вычислений, и я не уверен что все легко получится.

      Ответить
    2. LeBig:
      05/10/2009 в 11:43

      мне кажется гигантское количество комбинаций кубика это маркетинговый ход. Реально — гораздо меньше. Ведь не все комбинации допустсимы, если разобрать, а потом произвольно собрать.
      Если не ошибаюсь, кубик гарантировано собирается максимум за 15–20 манипуляций. Если посмотреть ролики, где кубик собирают роботы, то это порядка 10 манипуляций.

      Ответить
    3. Peels:
      05/10/2009 в 12:03

      Повторюсь, что для кубика 3х3х3, если разобрать а потом произвольно собрать, то с вероятностью 1/2 выйдет «легальная сборка» (т.е. пространство конфигураций имеет две связных компоненты). Известно что он собирается максимум за 26 ходов (см сюда, третий слайд).

      Ответить
    4. Peels:
      05/10/2009 в 12:18

      Кстати если проделать подсчет для кубика 3*3*3 по приведенной выше логике [кстати, у меня там забыто возведение в степень в паре мест], получается
      (8!*(3^8)*12!*(2^12)),
      что будет ровно в 12 раз больше, нежели число на слайде у Эделькампа. Значит либо связных компонент таки 12 (причем 6 из них не отличимы по раскраске от «правильной сборки»), либо я что–то где–то пересчитал, либо мне в дестве очень везло с собиранием кубика.

      Ответить
    5. Peels:
      05/10/2009 в 19:38

      Зацените между прочим, какая у меня штука есть:

      размер 168x140, 47.99 kb

      Ответить
    6. Ga:
      07/10/2009 в 16:26

      скажи мне, есть смысл брать 7х7х7, если 4х4х4 и 5х5х5 уже освоены? Есть ли там над чем поломать голову?
      Интересен ли будет Мегаминкс, не знаешь? Что–то другое?

      Ответить
    7. Peels:
      07/10/2009 в 17:33

      Не знаю, этот 7х7х7 не мой, надо будет скоро отдать, и я его «путать» не решаюсь ибо дико пугает осознание того, что даже если бы одним поворотом я проставлял бы по одному кубику в правильное место, на обратную сборку ушло бы 218 поворотов, а посвятить несколько часов–суток–недель механическому кручению кубика я сейчас не готов. (У меня и на 5х5х5–то всего однажды терпения хватило, а у 4х4х4 я так и не разобрался как уголки менять если они не сойдутся).

      Но как средство для того чтобы окончательно и бесповородно доказать себе что ты таки освоил алгоритм сбора кубика NxNxN, как клевый гэджет друзей попугать или нервно покрутить в руках от нечего делать — он клев. Мегаминкс не пробовал, но тут дело вкуса же. Если тебе такие штуки нравятся — наверняка и этот понравится, даже если окажется что ты его на раз–два–три собирать умеешь 🙂

      Ответить

    Добавить комментарий