魔方里的数学

zhiqiangSeptember 26, 2007 科学

今天香港中文大学的Prof. Cai给我们上graph algorithm。第一节课上教我们玩魔方，先给每人发了一个。我喜欢这样的教学方法。

魔方的解法，在网上已经有无数了，基本上的思路都是几个定式，玩的时候记住这些定式即可。课上Cai给我们演示了一个他自创的定式，很可惜，我目前为止只学会弄出一面来。

OK，这篇文章的主要目的是讲魔方里的数学，对魔方的群结构研究网上也已经有很多，这里不谈了。魔方总共有(8! × 3⁸⁻¹) × (12! × 2¹²⁻¹)/2 = 43252003274489856000=4.3× 10¹⁹个不同的状态。每个状态看作图上的一个点，则解魔方问题可以视作求一个超大图上的路径问题。这个图是如此之大，使得看上去求最短路这么简单的问题都变得非常困难，事实上，用计算机也不可能直接算。

虽然这个图是如此之大，而且边很少（每个顶点只引出12条边），但这个图的直径却非常小。可以证明，任何一种魔方的状态，都可以在26步之内复原。（见Optimal solutions for Rubik's Cube)

这样的图与以前提到过的洗牌模型里面的图非常相似，结构简单，定点巨多，但混合速度却特别快（从一点会以非常快的速度达到其它点），做算法的很喜欢这种图。

查看更多关于Rubik's Cube, 图论, 洗牌, 算法, 解法, 魔方的内容。

19条留言 -> 跳到留言表格

At 2007.09.27 09:52, 热心读者 said:

。（见Optimal solutions for Rubik's Cube)
链接的url错了。

[Reply]
At 2007.09.27 16:15, deerlamp said:

Optimal solutions for Rubik's Cube的那个wiki en在国内被禁了，能否把网页内容发给我？

[Reply]
- At 2007.09.27 19:58, zhiqiang said:
  
  用这个链接可以阅读wikipedia wikipedia browser
  
  [Reply]
At 2007.09.28 15:35, 小一 said:

我想知道怎么在26步之内复原

[Reply]
- At 2007.09.29 15:50, PSKing said:
  
  应该只是理论上这样吧，
  要找出这样一个解来可不容易阿！
  
  [Reply]
- At 2007.09.29 18:24, zhiqiang said:
  
  There exists a position that needs 20 face turns (superflip). There exists an algorithm that can always solve in 26 face turns. There exists a position that needs 26 quarter turns, and there is an algorithm that can always solve in 35 quarter turns.
  
  这样的算法即使有，也不可能用。而且26步的证明用了计算机。7TB的RAM extension，用这些就没什么意思了。
  
  [Reply]
  - At 2007.09.30 10:07, 小一 said:
    
    呵呵,我说嘛,这不是人能做到的....
    
    [Reply]
    - At 2007.10.01 09:11, szuxjq said:
      
      但是确实有高手能在十几秒内复原的
      
      [Reply]
      - At 2007.10.02 16:07, 小一 said:
        
        这个我看过......太恐怖了....
        
        [Reply]
        
        At 2007.10.03 09:57, szuxjq said:
        
        魔方众多状态的相似度很高，应该有法子可以快速处理。。。
        
        At 2007.10.06 09:41, 小一 said:
        
        -_-!! 我是不行了.....
At 2007.09.28 23:31, szuxjq said:

我只会做一层，觉得在往前一步就要参考别人的经验了。

[Reply]
At 2007.09.28 23:57, dribblejj said:

你们的生活太有趣了，现在看你这儿的数学问题成了我业余学习数学的方式....

[Reply]
- At 2007.10.04 21:41, ikbear said:
  
  我也有同感啊。
  
  [Reply]
At 2007.09.30 19:43, Bryan Chan said:

So what is your major? Mathematics?
Your class seems so much interesting compare to mine ;)

[Reply]
- At 2007.10.02 12:57, zhiqiang said:
  
  this is a lecture of advanced graph algorithm in theoretical computer Science
  
  [Reply]
At 2007.12.02 20:58, bafisys said:

可不可以教教我魔方的状态是怎么算出来的？？？？

[Reply]
- At 2007.12.02 21:17, zhiqiang said:
  
  魔方有多少种可以达到的状态？答案是 43252003274489856000 约 4000 亿亿。
  
  算法： 8 个角方块排列在 8 个位置， 12 个棱方块排列在 12 个位置，共有 8! × 12 ！种。又每个棱方块有 2 个朝向，每个角方块有 3 个朝向，共 3^8 × 2^12 种。因此魔方的状态数是 8! × 12 ！× 3^8 × 2^12 ＝ 519024039293878272000 种，51902亿亿以上。
  
  但在 20 个方块中， 18 个位置确定，另外 2 个位置也就确定了。因此要去掉因子 2 ！。在 8 个角方块中， 7 个朝向确定，第 8 个朝向也就确定了；在 12 个棱方块中， 11 个朝向确定，第 12 个朝向也就确定了。这样要再去掉 3 × 2 因子，实际是上面数的 1/12 ，即总数 8! × 12 ！× 3^7 × 2^11/2=43252003274489856000 。
  
  从另一个角度考虑上面的除数 12 。如果我们确定了 6 种颜色，每种颜色涂在魔方的1 个表面上的9个小方块上。然后然后我们拆开魔方，再打乱了重新拼装起来，那么并不是所得到的每个魔方都能还原为初始状态。具体说，有519024039293878272000 种拼法，可以分为 12 类，每类 43252003274489856000 种。同类里任何两个状态可以相互转换，而不同类间不能转换。
  
  至于最后两段是为什么,要使用群论了,见http://qzc.home.zjgz.net/mofang4.htm
  
  [Reply]
At 2008.02.28 20:45, 现代古人 said:

真是佩服这些搞研究的人！
但往往太过于专业了，或研究的过于细致了，研究者的视野就缩小了，研究者或科学家基本都如此。反正我们大多数人没有如此的兴趣，要生活啊！一头扎进去了，其余的学习生活怎么办？
还是向科学家们致敬！他们太伟大了。人类的进步有赖于此。
对于几十秒钟就回复魔方的人，也只让我等普通人佩服的五体投地。
但我们相信都有规律，这些规律能不能传下来咧！

[Reply]

« Windows Live Writer支持WordPress 2.3的tag的方法（不用插件）

货币战争（附PDF和TXT版下载） »

魔方里的数学

查看更多关于Rubik's Cube, 图论, 洗牌, 算法, 解法, 魔方的内容。

19条留言 -> 跳到留言表格

阅微堂