Любой алгоритм, связанный с кубиком Рубика
У меня вчера была интересная идея. Представьте, что у вас есть кубик Рубика с одинаковыми цветами на каждом лице. Теперь, если я закручиваю его один раз и знаю, как его крутить, я всегда могу вернуть куб к его оригиналу, выполнив этот шаг в обратном порядке. Если я поверну дважды, я всегда смогу восстановить куб с минимально обращенными двумя шагами. Поэтому я думаю, что если бы я случайно скрутил n шагов, всегда может быть n шагов, чтобы повернуть куб к оригиналу.
Тем не менее, я думаю, что когда n становится больше, минимальные шаги для выполнения реверсирования могут быть меньше, чем n, потому что будет некоторая определенная последовательность шагов, которая может использовать меньше шагов для достижения того же эффекта при использовании большего количества шагов.
Например, если n=100, он может иметь тот же шаблон, когда n=30, поэтому он эквивалентен n=30. Тогда, возможно, я мог бы использовать операцию m шагов, чтобы уменьшить n до 20, но m меньше 10.
Так что я думаю, что независимо от того, насколько велика n, он всегда будет сходиться к
маленькое число, которое означает, что независимо от того, как кубик Рубика изначально, я всегда мог восстановить его к его оригиналу менее чем за k шагов, где k - сходимость n.
У меня вопрос, если существует алгоритм, который можно использовать, чтобы найти сходимость п? Я думаю, что некоторые вещи в теории графов или теории групп были бы полезны.
1 ответ
Есть алгоритм, и есть известное решение. Ответ 20.
См. http://www.cube20.org/ для истории проблемы и исходного кода для того, как ответ был продемонстрирован.