*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

вторник, 10 августа 2010 г.

Решение кубика Рубика максимум на 20 шагов

Вроде как поставлена новая планка в алгоритме Бога для кубика Рубика. 35 машинолет были потрачены, чтобы доказать, что для решения любой позиции кубика надо не более 20 движений.

http://www.cube20.org/

Update: У нас тут есть свои блумберговские кубики, на грани которых кроме цвета нанесена корпоративная атрибутика. Подобное "улучшение" сильно осложняет сборку, так как необходимо правильно сориентировать остов до начала сборки слоев. Причем данная ориентация может съехать при неосторожной попытке сборки начального слоя.

7 комментариев:

  1. А где алгоритм же? Я тоже могу показать два примера решения за 20 ходов и сказать: "Я сделал это!" :)

    ОтветитьУдалить
  2. Ну там предлагается поверить им на слово. Все-таки авторитетные люди. ;-)

    Может там для самого алгоритма нужна там громадная база данных по комбинациям, которую они рассчитали.

    ОтветитьУдалить
  3. Ага, в базе все комбинации, а алгоритм такой:
    1. Найти комбинацию в базе
    2. ???
    3. ПРОФИТ!

    А базу составляли студенты за зачет по матану =)

    ОтветитьУдалить
  4. Этот комментарий был удален автором.

    ОтветитьУдалить
  5. Надо организовать что-то вроде SETI@HOME с gpu-калькуляцией - база довольно быстро соберется :)

    посчитать граф, где ребро - одно из действий, вершина - состояние кубика. Потом по графу кратчайший путь находить

    ОтветитьУдалить
  6. Этот комментарий был удален автором.

    ОтветитьУдалить
  7. ой, там вершин 43 252 003 274 489 856 000 будет тогда :)

    ОтветитьУдалить