魔方打乱公式

魔方打乱公式

最近玩魔方比较多，发现打乱魔方也是一个很有技术含量的活。魔方的还原是打乱的逆过程，在标准的魔方比赛里，打乱是很有讲究的，三阶魔方通常打乱17-20下。咦？为什么不是50？100呢？是不是打乱步数越多是不是越难还原？回答这些问题，首先要知道，在魔方比赛里，打乱魔方是由打乱员负责的，电脑会随机生成一组打乱序列，我们称之为打乱公式,打乱员就要按照这个打乱公式把模仿打乱，因此，步骤太多会增加打乱员的负担。那多少步合适呢？这就要引出一个上帝之数(The God Number)的概念,目前的水平将上帝之数定为17，即我们能在17步以内将魔方打乱到任意形态，同理，理论上任何三阶魔方在17步之内都是可以被还原的。那会不会更小呢？这还需要进一步的考证。

还有一个事情，就是打乱公式如果是20步，那么打乱后所需的最少还原步数会是20吗？答案肯定是<=20，因为打乱公式一般情况下会有优化的可能。比如打乱公式第一次让魔方前面逆时针转90度，第二步是前面顺时针转90度。那么很明显这两步会相互抵消。也就是要避免回文公式，因此，一个完美的打乱公式的步数应该是打乱后的魔方还原所需的最少步数，即我们只能按照打乱公式的逆序才能以最小的步骤还原回去。

魔方的表示

魔方的转动用语言怎么简单地表达呢？

David Singmaster发明了Singmaster符号来解决这一问题。这里以三阶魔方为例，三魔共有6各面，因此我们用R、L、U、D、F、B、分别来表示右、左、上、下、前、后六个方向，方向确定后还需要确定旋转方式，若是顺时针旋转，则直接写上符号，逆时针旋转则在后面增加符号'，旋转180度在后面增加符号2。如F表示前面顺时针旋转90度，U’表示上面逆时针旋转90度，R2表示右侧旋转180度（注：180就无需分顺逆方向）。

打乱公式编程实现

这里我采用了非常非常原始的方法写了一个二阶、三阶、金字塔魔方的打乱公式生成工具类，代码很简单，肯定不会生成完美的打乱公式，但也对简单地情况做了过滤，我后面会放到gist上。权当抛砖引玉。

调用起来比较简单，比如生成50个20步的三阶打乱公式：

for(int i =0; i<50;i++)
		System.out.println(getThreeCubeDisruting(20));

效果: