您的位置首页百科问答

存在可以遍历三阶魔方所有情况的公式吗?

存在可以遍历三阶魔方所有情况的公式吗?

的有关信息介绍如下:

存在可以遍历三阶魔方所有情况的公式吗?

这个问题有两种不同的理解方式,区别在于“出现过的状态”是否包括公式转到一半时“路过”的状态。如果包括,则这样的公式存在,并且可以构造;否则,这样的公式不存在。

举个例子说明“包括”与“不包括”的区别。例如对于公式“RU”,从还原态出发转动105遍之后魔方将再次回到还原态,如果“出现过的状态”包括转完R但还没有转U时“路过”的状态,则该公式在循环过程中一共出现了了210个不同状态;否则该公式在循环过程中一共出现了105个不同状态。

对于第一种情况,即公式转动每一步所路过的状态都计入出现的状态。此时,原来的问题可以转变成如下弱化版的问题:是否存在一个转动序列,使得从还原态出发执行该转动序列后魔方回到了还原态,并且魔方每一个可能的状态都在转动中出现过。

事实上这样的序列很容易构造,一个直观的方式如下。首先把所有状态按照任意顺序排成一个圈:还原态 -> 状态1 -> 状态2 -> ... -> 状态N-1 -> 还原态,其中N为魔方总状态数,约为4.3*10^19。然后对于上述圈中每一个状态转化,我们都试着找一个合适的公式来完成,即总共得到N个公式。最后把这N个公式串起来得到一个特别长的公式,这个公式即满足题目需求。那剩下的问题就是对于每一步,如何找一个公式使得魔方可以从状态i转变为状态i+1。这总是很容易的,最简单的方法就是分别找到这两个状态的还原公式Si和Sj,然后Si Sj^-1就是满足条件的公式(先转Si把状态i变为还原态,再转Sj的逆序把还原态变为状态j)。

另一个更有意思的问题在于,这个公式的长度能否刚好为N?即在转动的时候,没有任何一步的浪费,每一步都刚好转到一个从未出现过的状态,转完N步恰好遍历完三阶魔方的所有状态。答案是存在的,并且在几年前有一个叫Bruce的人(WCAID:2006NORS01)构造出来了:A Hamiltonian circuit for Rubik's Cube。他的构造只用到了5个面,且每一步转动都是90度,有兴趣的可以点开上述链接围观一下。

对于第二种情况,即不考虑公式未转完时路过的状态,则不存在这样的公式。这是因为,对于魔方转动群,任何一个公式的最长循环长度为1260(即魔方群元素的阶最大为1260)。换句话说,任何一个公式从还原态出发转回到还原态的过程,其需要的重复次数不会超过1260,即如果不考虑公式未转完时路过的状态,任何一个公式在循环过程中至多只会出现1260个不同状态。而魔方的总状态数远大于1260,剩下那些状态都没有出现,因此这样的公式是不存在的。