魔方里的数学

zhiqiang九月 26, 2007 自然科学

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

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

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

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

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

关于, , , , , »
  • "完美"的洗牌次数 - 7次 在大家玩牌的时候，每一局之前都需要重新洗牌——一次洗牌指将牌分为左右两垛然后穿插放牌，但多少次洗牌才是正当的呢？就我多次打牌的观察，...
  • 算法百科全书 - Encyclopedia of Algorithms Xie Xie推荐了一本今年出版的一本新书，Encyclopedia of Algorithms，全书1200页，涵盖各类有名问题的算法，概率算法，近似算法，量子算法等。 翻了一下，...
  • 一个算法面试题 & 面试题库 一个面试题，号称是微软的 输入$$a_1, a_2, ..., a_n, b_1, b_2, ..., b_n$$，如何在O(n)的时间，用O(1)的空间，将这个序列顺序改为$$a_1, b_1, ..., a_n, b_n$$。 刚一...
  • 求平方根倒数的算法 下面这个求$$1/\sqrt{x}$$的函数号称比直接调用sqrt库函数快4倍，来自游戏Quake III的源代码。 float InvSqrt (float x){ float xhalf = 0.5f*x; int i = *(int*)&x...
  • 图同构问题属于P？ 更新：证明的关键一步发现错误，作者更新了论文，结论甚至论文标题都改了（废话），新版本On the graph isomorphism problem。 提交论文到arxiv不需要审阅...
  • 编程的核心是数据结构，而不是算法 Rob Pike, 最伟大的 C 语言大师之一 , 在Notes on C Programming(英文原文)中从另一个稍微不同的角度表述了 Unix 的哲学: 你无法断定程序会在什么地方耗费运...
  • 素数筛法的复杂度 Xie Xie给我看了一个链接性能调优--永远超乎想象，里面提到了素数筛法的复杂度，作者用实验发现此筛法是线形的。 所谓素数筛法就是那个求小于n的...
  • Perfect Shuffle的算法 珍爱生命，远离政治。我们继续讨论算法。 2008/04/01补充：此算法有重大缺陷。详情请见留言部分。 一年前，我们讨论过一个算法问题，perfect shuffle，...
  • 理论计算机初步：算法和计算模型 下面是wikipedia上算法的定义： 算法是指完成一个任务所需要的具体步骤和方法。也就是说给定初始状态或输入数据，经过计算机程序的有限次运算...
  • 有序矩阵的中位数算法 给定$$n\times n$$的实数矩阵，每行和每列都是递增的，求这$$n^2$$个数的中位数。 使用类似Tarjan的线性中位数的方法，每次找每列中位数，然后找中位数...
22条留言 -> 跳到留言表格
  • 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.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 2008.12.11 17:49, thxrd said:

          比速度是一派的
          还有一派比步骤少。。。
          地球人记录28步耗时2.半小时

          [Reply]
        • 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]
                  • At 2009.04.01 18:24, CASTEREND said:

                    Oh I could break a cube into pieces and fix it again

                    [Reply]
                    • At 2009.11.16 20:23, yyuu01 said:

                      我觉得魔方应该是24步就能还原吧。
                      一个方块，放在一个有箭头方向的方槽内，一共有6*4=24种放置方法。
                      魔方的每一个旋转轴上能旋转的状态最多有4个。一个旋转轴上只有两个可旋转的层，中间的层不能旋转。
                      所以一次只旋转一个轴的一层，那么只有3*2*4=24种可能结果。

                      [Reply]
                      (Required)
                      (Required, not published)

                        B | I | U | D | 添加链接 | 插入引用 | 插入代码 | 插入表情 | 甲 | + | ?
                      «
                      »
                      guest | 注册 | BBS | 管理 | English | 繁體 | https

                      阅微堂

                      zhiqiang's personal blog
                      Loading...
                      Loading...
                      Loading...