魔方可在几步内还原？
Posted by frank on 03月 27th, 2008
Rubik’s Cube的中文名叫魔方，是匈牙利的Rubik教授在1974年发明的智力玩具。去年两位东北大学学生用了一点手上的空闲时间证明任何结构的魔方都能在26步内还原。现在Tomas Rokicki，在斯坦福大学受过训练的数学家更胜一筹，他证明没有一种结构的魔方需要26步才能还原，因此他将还原最少步骤降至25步(论文预印本)。Rokicki的证明完全依靠计算机科学，他使用立方体的对称来研究集合内的转换，这允许他将“立方体空间”分割成20亿个集合，每个集合包含200亿个项。他发现许多集合与其它集合本质上是相同的，因此可以去除。为了完成整个计算，他需要一个8G内存的工作站，1.6GHz频率的Q6600 CPU运行1500小时。这个过程目前还未完成，Rokicki已经着手下一步：24步内还原，这么推测下来，想必23正在向他招手。魔方的极限在何处？已知有些组合能用20步解决，但也还知道没有一种组合是能用21步解决的。20步可能是个界限。