魔方吧·中文魔方俱乐部

标题: 魔方到底有多少种变化 [打印本页]

作者: shita 时间: 2013-4-2 09:16:07 标题: 魔方到底有多少种变化

以前不太知道怎么计算魔方的变化数，因为排列组合的时候每次转动都有8个块会动，用理论来说，就是没一个排列都不是独立的事件。
这两天，看了计算机最小步，发现了新东西，目前已经有很多计算机理论表明，一个3阶基本可以在20步左右还原。那么也就是说，一个魔方可以通过20步打乱成图案。这样一来就好考虑了。我们知道算作一步的转动有以下几种，R,L,F,B,U,D,R',L',F',B',D',U',R2,F2,U2,B2,D2,L2,总计18种路径。那么一个20步打乱可能的路径是多少种呢？18的20次方。
大家什么意见呢？

作者: hqd20010111 时间: 2013-4-2 09:17:36

本帖最后由 hqd20010111 于 2013-4-2 09:20 编辑

不仅有位置，还有朝向。。。。。

明明是个男的，还放个女头像，唉

作者: shita 时间: 2013-4-2 09:18:27

忽然发现，数量应该是18乘17的19次方。因为除了第一步打乱可以有18种选择之外，以后没次打乱都只能17种，因为不能重复前一步打乱。

作者: shita 时间: 2013-4-2 09:22:18

哈哈，真的不能细细考虑阿，突然发现，如果第一步是R2,那么第二步和R有关的似乎也不能选了，因为这样一来，R2+R就等于一个R'，也就是说，变化数还要少。18乘15的19次方

作者: shita 时间: 2013-4-2 09:26:54

刚刚按照这个算法算了下，围棋的图案变化有4.69*10^108种，3阶魔为3.99*10^23种，和围棋比，差了N多数量级阿。

作者: shita 时间: 2013-4-2 09:30:54

hqd20010111 发表于 2013-4-2 09:17
不仅有位置，还有朝向。。。。。

爱美之心嘛，放个美女头像大家不也看着养眼么。

作者: shita 时间: 2013-4-2 09:33:06

从另一个角度来讲，如果能从理论上计算出变化总数量，那么也就决定了理论上存在的最小步数了。在这里通过旋转坐标轴以后一样的图案都应当归为一种。

作者: hubo5563 时间: 2013-4-2 09:34:54

本帖最后由 hubo5563 于 2013-4-2 14:44 编辑

shita 发表于 2013-4-2 09:22
哈哈，真的不能细细考虑阿，突然发现，如果第一步是R2,那么第二步和R有关的似乎也不能选了，因为这样一来， ...

不能这么简单考虑，其中还有很多重的。
角块8个位置，8的排列，有8！种位置变化，棱块有12个位置，有12！个变化，每个角块3个方向，有3^8种变化，棱块有2个方向，有2^12种变化。所以总共魔方有12！*2^12*8！*3^8种状态。
但是，转动不能单独交换两个棱块，总数应除以2，也不能单独交换两个角块，所以总数再除以2，不能单独转一个角，所以总数还应除以3，不能单独翻转一个棱块，所以总数还应除以2，但是可以同时交换一对棱块和一对角块，所以总是再乘以2，所以能转出的总数是
12！*8！*2^11*3^7/2=43252003274489856000

作者: shita 时间: 2013-4-2 09:38:56

hubo5563 发表于 2013-4-2 09:34
不能这么简单考虑，其中还有很多重的。
角块8个位置，8的排列，有8！种位置变化，棱块有12个位置，有 ...

我高中的排列组合都忘记得差不多了，按你的计算，比我最后估算的结果还少，你的是4.3*10^20种，那么用我的方法考虑的话，理论最少步要少于20步。大概是18步。

作者: hubo5563 时间: 2013-4-2 09:45:48

shita 发表于 2013-4-2 09:38
我高中的排列组合都忘记得差不多了，按你的计算，比我最后估算的结果还少，你的是4.3*10^20种，那么用我的 ...

最少步确实是20步，已经找到至少需要20步才能复原的状态了。

作者: shita 时间: 2013-4-2 09:47:06

hubo5563 发表于 2013-4-2 09:34
不能这么简单考虑，其中还有很多重的。
角块8个位置，8的排列，有8！种位置变化，棱块有12个位置， ...

其实对我来说，计算中最头疼的是，角块动了，棱块必定有动的，所以单独计算角块和棱块，然后相乘是否正确？因为这两者之间必须都是相互独立的才能相乘。

作者: hubo5563 时间: 2013-4-2 09:51:25

本帖最后由 hubo5563 于 2013-4-2 09:54 编辑

shita 发表于 2013-4-2 09:47
其实对我来说，计算中最头疼的是，角块动了，棱块必定有动的，所以单独计算角块和棱块，然后相乘是否正确 ...

你考虑的是一转，的确角块动了，棱块也跟着动，但是，总能找到棱块不动，角块三循环的公式吧。也能找到角块不动，棱块的三循环公式，所以，角块和棱块可以看做是独立运动的。

作者: shita 时间: 2013-4-2 10:04:38

嗯，的确如此，刚才也在考虑，通过路径计算获得的最小步，即小于20步的可以在某些情况出现。由于要以最小步进行，当角块和棱块联动的时候，可能需要在路径的方式上增加步数来达到这个联动。

作者: 洛阳狼王 时间: 2013-4-2 10:12:16

多少种变化，算了才知道！

作者: LOVEGARFIELD 时间: 2013-4-2 10:32:24

shita 发表于 2013-4-2 09:38
我高中的排列组合都忘记得差不多了，按你的计算，比我最后估算的结果还少，你的是4.3*10^20种，那么用我的 ...

是4.3*10^19。上帝之数是20已有证明。

作者: jiangtianzhao 时间: 2013-4-2 10:38:05

shita 发表于 2013-4-2 09:47
其实对我来说，计算中最头疼的是，角块动了，棱块必定有动的，所以单独计算角块和棱块，然后相乘是否正确 ...

你那样用逆推的方法来算的话会出现很多相同的结果，就像很多同功能的公式一样，所以会大出几个数量级。所以不能简单的去按照打乱来计算，必须通过严格的每块的位置和朝向来计算。

作者: 奇趣屋toys 时间: 2013-4-2 10:45:59

楼上的说的透彻，学习了。

作者: 天方魔 时间: 2013-4-2 11:49:23

楼上说的来说简直是天书，完全听不懂，咱的数学一直很差，所以从没有关心过这问题，只是直到不可能碰到一次以前做过的打乱，就算碰到过也忘了！

作者: 呆木 时间: 2013-4-2 12:42:20

楼主是教授级别的哈

作者: mylxc60 时间: 2013-4-2 12:44:17

从转动步数算是有问题的，因为同一个状态可以通过不同转法得到。例如同样的三棱换就有不同步数的做法，所以这样算会出现重复状态，算法是错的。

作者: 花无缺0228 时间: 2013-4-2 16:03:51

shita 发表于 2013-4-2 09:26
刚刚按照这个算法算了下，围棋的图案变化有4.69*10^108种，3阶魔为3.99*10^23种，和围棋比，差了N多数量级阿 ...

一直就觉得围棋比魔方难。

作者: 花无缺0228 时间: 2013-4-2 16:03:51

shita 发表于 2013-4-2 09:26
刚刚按照这个算法算了下，围棋的图案变化有4.69*10^108种，3阶魔为3.99*10^23种，和围棋比，差了N多数量级阿 ...

一直就觉得围棋比魔方难。

作者: shita 时间: 2013-4-2 16:53:57

花无缺0228 发表于 2013-4-2 16:03
一直就觉得围棋比魔方难。

你也下围棋？

作者: shita 时间: 2013-4-2 16:56:30

我的围棋又荒废了一年半，目前在TOM网上基本能到1段。这一荒废，又回到10级的水平了。

作者: Ray_Lam 时间: 2013-4-2 17:58:50

我记得是四千亿吧。。

作者: 花无缺0228 时间: 2013-4-2 19:14:22

shita 发表于 2013-4-2 16:53
你也下围棋？

业余。初中时学过俩月围棋，偶尔和别人下着消磨时间，也不往专业方面发展。

作者: shita 时间: 2013-4-3 08:06:01

花无缺0228 发表于 2013-4-2 19:14
业余。初中时学过俩月围棋，偶尔和别人下着消磨时间，也不往专业方面发展。

我也是初中的时候学的，看书自己学。

欢迎光临魔方吧·中文魔方俱乐部 (http://www.mf8-china.com/)