[趣味数学·益智游戏]魔方

鲁比克教授当年以帮助学生理解3D几何中的空间转动为动机而构想的教学道具却无心插柳地成为有史以来最畅销的机械益智玩具。

  一个外围26个子块的内部铰接构造能使其任意一面都可以随意旋转(任意方向可转90度或半圈)的3×3×3六面体。六个面颜色互异,这个玩具的目标是在经过任意次随机扭转后复原六面单色的状态。这个在20世纪七十年代由匈牙利人艾尔诺•鲁比克发明的机械益智玩具在随后的八十年代期间卖出了数百万个。

  鲁比克魔方的变换总数达

\( \huge \frac{8! * 12! * 3^8 * 2^{12}}{2 * 3 * 2} = 43252003274489856000 \)

(特纳&戈尔德,1985,Schönert)。霍伊使用波利亚-伯恩赛德引理证明了存在针对魔方整体对称性共轭不变的 901083404981813616 种不同变换。

  鲁比克魔方的转动操作内蕴的有限群称为鲁比克群,鲁比克群的凯莱图称为鲁比克图,复原任意颜色组合的魔方所需要的最少转动次数等于鲁比克图的直径(即最长测地线),有时被称为上帝之数。尽管存在从任意颜色组合复原魔方的算法,它们不一定是最优的(即最少的转动次数),计算上帝之数异常困难,早在1995年就已经知道上帝之数的下界(在最坏的情形)是20。直到2010年托马斯•罗基奇等人证明任意颜色组合的魔方都能够在20步内复原[1],从而确立上帝之数为20

另见:

上帝之数,鲁比克钟,鲁比克图,鲁比克群

参考:

  • G.赫尔姆斯,鲁比克魔方
  • D.霍伊,魔方的问题空间/解空间的实际测度
  • 道格拉斯•理查•霍夫斯塔特[2],魔方迷玩转魔方,魔方大师破解魔方,《科学美国人》第244期Metamagical Themas专栏, 20-39页, 1981年3月
  • 道格拉斯•理查•霍夫斯塔特,不可思议的元主题:心灵与模式的追问,第14章,位于纽约的BasicBooks出版社, 1985
  • 赫伯特•科先巴,最优解
  • M.E.拉森,魔方的报复:群论解决方案,美国数学月刊第92期,381-390,1985
  • M.朗里奇,魔方的领域
  • D.L.W.米勒,用最快的搜索算法和简要表解决鲁比克方块
  • J.帕尔默,魔方路线,新科学家第199期,40-43,2008
  • 托马斯•罗基奇,25步足以复原魔方,2008年3月24日
  • 托马斯•罗基奇,22步足以复原魔方,2008年8月12日
  • 托马斯•罗基奇 & 赫伯特•科先巴 & 莫利•戴维森 & 约翰•德斯里奇,上帝之数是20
  • Jaap Scherphuis,Jaap的荟萃益智玩具的专题网页:3×3×3鲁比克方块
  • M.Schoenert,魔方爱好者: 按日期索引
  • M.Schönert,用GAP计算群论方法分析魔方
  • D.Singmaster,鲁比克魔方札记,位于新泽西州Hillside的Enslow出版公司,1981
  • 唐•泰勒,精通鲁比克方块,位于纽约的HRW(Holt, Rinehart, and Winston)教育图书出版公司,1981
  • 唐•泰勒 & 莲妮•赖兰兹,魔方游戏:92个玩法和解法,位于纽约的HRW(Holt, Rinehart, and Winston)教育图书出版公司,1981
  • E.C.特纳 & K.F.戈尔德,鲁比克群,美国数学月刊第92期,617-629,1985

[1] 与四色定理一样,证明上帝之数等于20使用的方法也是求助于现代计算机威力的蛮力法,因此这并不是一个符合美学标准的证明

[2] 侯世达(中文名),曾获得普利策奖的《哥德尔、埃舍尔、巴赫:集异璧之大成》一书的作者


原文:Rubik’s Cube