魔方吧·中文魔方俱乐部

标题: 关于魔方的有多少态的问题 [打印本页]

作者: xiaotnai 时间: 2009-1-5 20:23:56 标题: 关于魔方的有多少态的问题

我记得在哪看过有亿亿态两个亿看着好吓人
最近我在写魔方最少步的计算程序因为我数学不是很好
不敢妄下断言刚才也看到别人说只有几种这个是绝对不可能得紧紧是转5下的态也不只几千态
不过我想问一些高人计算出的亿亿态里是否包括错态呢？？
因为不是说所有的颜色组合都可以摆出来的大部分的组合是错态
我记得好像魔方弄散了在组装有12分之1的机会才能组装正确
剩下的12分11的机会组装出来的都是错态
那是不是说在魔方的亿亿态里有12分11 都是错态呢？

我会常来看贴子的希望高手指教我说过我数学不是很好
所以大家觉得我说的不对尽管批评我说的都是猜测而已
我的QQ295928 有兴趣的加我QQ讨论也行

作者: ben_zheng 时间: 2009-1-5 20:50:23

问题好深奥啊感觉听不懂呵呵先占了沙发等待回答

作者: 录 时间: 2009-1-5 20:59:46

不是的..這4300億億種狀态都是可還原的

作者: 襪子裡的餅乾 时间: 2009-1-5 21:33:03

這道沒仔細研究過...還在提速中...沒時間想這個問題，呵呵...

作者: robester 时间: 2009-1-5 22:08:04

有没有多算不知道（因为也许有重合的），但是没有错态的，已经除掉12了

作者: 乌木 时间: 2009-1-5 22:19:19

楼主可以先算算一个正确的三阶“纯色”魔方，中心块组不动，拆下角块、棱块随机组装的总态数M是多少？（M的计算方法之一是用排列组合知识。）

那么，一个正确的三阶“纯色”魔方，中心块组不动，不许拆下角块、棱块随机组装，只用转动魔方层的方法，所得的相对于参照物中心块组而言的总态数就是M /（3×2×2）。（约四千三百多亿亿个，其中个个都可复原或一个为已复原态，且决无两个一样的态。）

原因：1、1/3－－转魔方法无法单单翻一个角块的色向；2、1/2－－转魔方法无法单单翻一个棱块的色向；3、1/2－－转魔方法无法单单互换两个魔方块的位置。

[ 本帖最后由乌木于 2009-1-5 22:30 编辑 ]

作者: xiaotnai 时间: 2009-1-5 23:53:38

本来想用程序挂一个状态库出来那样直接输入当前态就可以马上找出最少步还原
原来这么多态看来不是太容易

作者: smok 时间: 2009-1-6 09:16:20

三阶的角块为什么不能跟棱块换位？外表看上去完全一样嘛，你们这些高手为什么不好好讨论一下这个问题？

作者: conwood 时间: 2009-1-6 09:53:05

建议你去找找国外的资料，国内这方面资料太少。

你这个方法要是能用，肯定很多人都做出来了。

现在国外最好的算法是有一个中间状态库，库里面的状态在13步之内都能还原，然后算法要对任意状态在最短步数内达到某个中间状态。

多学一些基本的计算机理论吧。

原帖由 xiaotnai 于 2009-1-5 23:53 发表本来想用程序挂一个状态库出来那样直接输入当前态就可以马上找出最少步还原原来这么多态看来不是太容易

作者: conwood 时间: 2009-1-6 09:53:39

角块不能和棱块换位是常识，你拆开看看就知道了。

原帖由 smok 于 2009-1-6 09:16 发表三阶的角块为什么不能跟棱块换位？外表看上去完全一样嘛，你们这些高手为什么不好好讨论一下这个问题？

作者: mrzs 时间: 2009-1-6 10:21:23

·魔方还原程序不简单，建议先查一下有关资料。最好能找到现成的库或者算法，不要自己闭门造车了，没必要。

作者: 乌木 时间: 2009-1-6 11:26:50

原帖由 conwood 于 2009-1-6 09:53 发表
角块不能和棱块换位是常识，你拆开看看就知道了。

没错，实物魔方由于结构关系，角块、棱块、中心块三者无法互换位置；但是在虚拟魔方（比如Puzzler中的魔方）中谈不上内部结构，但是由于它的运动完全符合实物魔方，故同样如此。那么，是不是应该说魔方的运动方式起决定作用，实物魔方仅仅是在机械结构上满足了魔方运动规律？

当然，实物魔方出现在先，虚拟魔方出现在后，但这是另一回事吧？在此问题上，还是魔方的运动方式，即每一转所发生的有关块的循环变化方式，决定了魔方的态变规律。

我的想法对吗？

作者: 乌木 时间: 2009-1-6 11:42:39

原帖由 xiaotnai 于 2009-1-5 23:53 发表
本来想用程序挂一个状态库出来那样直接输入当前态就可以马上找出最少步还原
原来这么多态看来不是太容易

两个态之间的路线不是唯一的，即使在当时的数据库条件下找到一条“最短路线”，也不一定是理论上该两态之间的最短路线。是否最短路线，要加以证明的吧？除非所用的方法能保证获得的是理论上的最短路线。

具体的不懂的，这里只是问问。

作者: xiaotnai 时间: 2009-1-6 18:11:25

原帖由乌木于 2009-1-6 11:42 发表

两个态之间的路线不是唯一的，即使在当时的数据库条件下找到一条“最短路线”，也不一定是理论上该两态之间的最短路线。是否最短路线，要加以证明的吧？除非所用的方法能保证获得的是理论上的最短路线。

具体 ...

如果我挂出库当然是能保证找出最短路线
请问能给我您的联系方式吗？我想想请教问题
论坛消息告诉我QQ好吗
我的QQ295928

作者: xiaotnai 时间: 2009-1-6 18:14:51

现在我又在想另一个问题就是同态不同色的问题
比如转一步 R 和 L 还有 F 等（M不算）一下转动其实转出来的都是同态只是颜色不同而已。不知道我有没有表达明白如果能在已算出的态中去掉这些同态不同色应该能减少很大一部分态

作者: conwood 时间: 2009-1-6 20:49:56

乌木说的有道理，很启发
不过我觉得什么决定的并不是很重要了

原帖由乌木于 2009-1-6 11:26 发表

没错，实物魔方由于结构关系，角块、棱块、中心块三者无法互换位置；但是在虚拟魔方（比如Puzzler中的魔方）中谈不上内部结构，但是由于它的运动完全符合实物魔方，故同样如此。那么，是不是应该说魔方的运动方式 ...

作者: 乌木 时间: 2009-1-6 21:10:16 标题: 回复 14# 的帖子

我没有QQ。其实论坛内理论高手不少，我向他们学了一点点皮毛，稍加深入就搞不懂的了。

作者: 乌木 时间: 2009-1-6 21:15:50

原帖由 xiaotnai 于 2009-1-6 18:14 发表
现在我又在想另一个问题就是同态不同色的问题
比如转一步 R 和 L 还有 F 等（M不算）一下转动其实转出来的都是同态只是颜色不同而已。不知道我有没有表达明白如果能在已算出的态中去掉这些同态不同色应该 ...

好像这样的一些态叫“同构”（对吧？请内行指正），好像那“上帝之数”一帖中提到这事的，是可以简化计算的。

同构的态显然在计算总态数时要统统计入；而若干个“同态”在统计总态数时只能保留一个，其余的不得重复记数。对吧？

同态例子：从任何同一种初态出发，分别作“U，D'”和“D'，U”，得到两个态；还有比如分别做“U2,D”和“D,U2”,得到两个态，等等，分别都只能算一个态。

大概可以不用这种“态树”生长方式的办法来记录一个个态，改用更巧妙的方法？以免随之而来的“消同态”这种劳民伤财的巨量计算的吧。（我不清楚。）

[ 本帖最后由乌木于 2009-1-6 21:36 编辑 ]

作者: 七夜 时间: 2009-1-6 23:20:10

谁说有多少,谁一个一个摆出来

作者: sokoban 时间: 2009-1-7 00:03:46 标题: 回复 15# 的帖子

要计算排除颜色的对称性后的状态数，就需要用一点群论的知识了。涉及到共轭类、burnside 引理等等。

考虑到颜色对称性之后，状态数只有：901,083,404,981,813,616, 也是很大的一个数字。
不考虑对称性的数字为 43,252,003,274,489,856,000

具体计算过程可以参考下面：

Date: Fri, 04 Nov 94 11:46:50 -0500 (EST)
From: Dan Hoey <hoey@aic.nrl.navy.mil >
Subject: The real size of cube space

In January of this year, Jerry Bryan and I wrote of counting the
number of M-conjugacy classes of Rubik's cube. In the sense that (for
instance) there is really only one position 1 QT from start, even
though that QT may be applied in twelve different ways, this task
amounts to counting the true number of positions of the cube. The
earlier discussion centered on calculations involving computer
analysis of large numbers of positions. However, a look in Paul B.
Yale's book _Geometry and Symmetry_ gave me a clue: the Polya-Burnside
theorem is a tool that allows us to perform this calculation by hand.

The Polya-Burnside theorem describes a relation between a finite group
J and a _representation_ of the group. For our purposes, a represen-
tation is a homomorphism of J into a permutation group, R: J -> S[X].
Here, S[X] refers to the group of all permutations of a set X; the
image of J, called R(J), need not be the whole of S[X], but R(J) will
be a subgroup of S[X]. The _orbits_ of R(J) are the equivalence
classes of X under the relation x~y, said to be true if there is some
permutation p in R(J) for which p(x)=y. The _fixed points_ of a
permutation p in R(J) are the elements x of X for which p(x)=x. The
Polya-Burnside theorem states that the average number of fixed points
of permutations in R(J) is equal to the number of orbits of R(J).
That is,
|R(J)| |Orbits(R(J))| = Sum[p in R(J)] |FixedPoints(p)|.
The average may also be taken over J:
|J| |Orbits(R(J))| = Sum[j in J] |FixedPoints(R(j))|,
a nontrivial distinction, since R may not be one-to-one (though it is
for our application). The Polya-Burnside theorem is not very
inaccessible nor hard to prove, but I will not prove it here.

For our purpose, we take the group J to be M, the 48-element group of
symmetries of the cube. X will be the set of all cube positions,
which we usually call Gx (for GE, GC, or G, depending on whether we
consider edges, corners, or both; we are considering the positions
relative to fixed face centers in all three cases). And the repre-
sentation R is the operation of M-conjugation: (R(m))(g) = m' g m.
Verifying that R is a homomorphism is an exercise in associativity
that Jim Saxe and I carried out in the Symmetry and Local Maxima
paper, in the archives [cube-mail-1, 14 December 1980].

R has been so chosen because we wish to calculate the number of
M-conjugacy classes of Gx, |Gx\Conj(M)|, which is be the number of
orbits of R(M). To apply the Polya-Burnside theorem for this, we need
to calculate, for each element of m of M, the number of fixed points
of R(m). That is the number of elements g of Gx for which m' g m = g.
Multiplying by m, this becomes g m = m g: the fixed points we wish to
count are just those elements g of Gx that commute with m.

There are several tools to make the counting easier. First, I'll note
that just as there are M-conjugacy classes of Gx, there are
M-conjugacy classes of M itself. The number of fixed points of R(m)
is the same for any m in a given conjugacy class. So to calculate the
total number of fixed points over R(M), we need only calculate the
number of g in Gx commuting with each of the ten classes of cube
symmetry and multiply by the size of the class.

The fundamental principle we use in finding whether g commutes with m
can be found by examining the cycles of m. Suppose m permutes a cycle
(c1,c2,...,ck), so that c2=m(c1), c3=m(c2),...,ck=m(c[k-1]),c1=m(ck).
For g to commute with m, we have g(c2)=m(g(c1)), g(c3)=m(g(c2)), ...,
g(ck)=m(g(c[k-1]), and g(c1)=m(g(ck)). So (g(c1),g(c2),...,g(ck)) is
also a cycle of m. Thus g must map each k-cycle of m to another
k-cycle of m, and in the same order. Conversely, if g acts thus on
cycles, then g will commute with m, and so g is a fixed point of R(m).

Suppose that m has j different k-cycles of cubies. There are j! k^j
possibilities for g's action on the cubies in those k-cycles: j!
permutations of cycles, and for each g

c1,c2,...,ck)->(d1,d2,...,dk),
k choices for g(c1) among {d1,...,dk}. It turns out to be a fairly
easy exercise to show that half of those possibilities are even
permutations and half odd, though the partition by parity is
surprisingly different depending on whether k is even or odd. This
will allow us to combine the results for GE and GC simply by
multiplying together and dividing by two.

Now consider orientation of cubies. This is similar to the case of
permutation, in that the orientation that g imposes on a cubie is a
constant for all cubies in a cycle. I will first discuss the edge
orientation, which is fairly straightforward, and continue to corner
orientation, which has some surprising features.

For edge orientation, if all the cycles have even length, then g's
orientation parity is zero over each cycle, and so zero over the
entire cube. So we can choose the orientation of imposed by c1->g(c1)
for each cycle (c1,...,ck) in 2^j ways. If there are odd-length
cycles, then half of the orientations will have nonzero orientation
parity, and only 2^(j-1) possible orientations can be achieved.

For corners, we might expect there to be 3^(j-1) orientations, except
3^j for cycles of length a multiple of three, and this is often so.
But there are two important exceptions. First, if m is a reflection
(i.e., not a proper rotation in C) then alternate cubies in each cycle
must be given the opposite orientation by g. If the cycle has even
length, this conserves orientation, so there will be 3^j possibili-
ties. If the cycle has odd length, this implies that the orientation
of each cubie must be its own opposite (i.e., zero twist). Thus,
there there is only one possible orientation of the 1-cycles in the
diagonal reflections. The second exception, an even bigger surprise,
occurs when m is either the 120-degree rotation or the 60-degree in-
verted rotation. It turns out that the orientation constraint forbids
any permutation that exchanges the two 1-cycles in these positions.
(This constraint on permutations would throw off the equality between
even and odd permutations, except that these classes of m have other
corner cycles that restore the balance.) The impossibility of m
commuting with an exchange of the two corners can be verified by
examining the possible orientations, but I haven't got any good way of
characterizing when it would be be a problem in general. In fact, I
did not notice it until I investigated discrepancies with the
exhaustive computer analysis.

Using the above analysis, we may carry out the calculation as in the
three tables below. The first two tables count the number of fixed
points of R(m) for an element m of each class, multiply by the class
size, and divide by |J|=48 to get the number of orbits as in the
Polya-Burnside theorem. The third table calculates the number of
fixed points by combining the results of the first two tables, divided
by the class size (which was multiplied in both for edges and for
corners), and divided by 2 (because only half the combined positions
have matching permutation parity).

Counting M-conjugacy classes of the edges of Rubik's cube.

M class          Cycles                   Total F.P.    Numeric
  (class size)    of m    Perms Oris    in class    Total/48
==============  ===========  ======  ====== ==========  ===========
Identity (1)  12 1-cycles  12!    2^12/2 12! 2^11 20437401600

Axis Rot/2 (3) 6 2-cycles  6! 2^6  2^6    6! 3 2^12       184320

Rot/3    (8) 4 3-cycles  4! 3^4  2^4/2 4! 3^4 2^6       2592

Diag Rot/2 (6) 5 2-cycles  5! 2^5  2^5
               2 1-cycles  2    2^2/2 5! 3 2^13       61440

Rot/4    (6) 3 4-cycles  3! 4^3  2^3    3! 3 2^10          384

Inv Rot/4  (6) 3 4-cycles  3! 4^3  2^3    3! 3 2^10          384

Diag Ref (6) 5 2-cycles  5! 2^5  2^5
               2 1-cycles  2    2^2/2 5! 3 2^13       61440

Inv Rot/6  (8) 2 6-cycles  2! 6^2  2^2    2! 3^2 2^7          48

Axis Ref (3) 4 2-cycles  4! 2^4  2^4
               4 1-cycles  4!    2^4/2 4! 3^2 2^14    73728

Inversion  (1) 6 2-cycles  6! 2^6  2^6    6! 2^12          61440
                                                      -----------
                                    | GE\Conj(M) | =  20437847376

Counting M-conjugacy classes of the corners of Rubik's cube.

M class          Cycles                Total F.P. Numeric
  (class size)    of m    Perms Oris in class    Total/48
===============  ==========  ======  =====  =========== =======
Identity (1) 8 1-cycles  8!    3^8/3  8! 3^7       1837080

Axis Rot/2 (3) 4 2-cycles  4! 2^4  3^4/3  4! 3^4 2^4       648

Rot/3    (8) 2 3-cycles  2! 3^2  3^2
               2 1-cycles  1    3^2/3  3^5 2^4          81

Diag Rot/2 (6) 4 2-cycles  4! 2^4  3^4/3  4! 3^4 2^5    1296

Rot/4    (6) 2 4-cycles  2! 4^2  3^2/3  3^2 2^6          12

Inv Rot/4  (6) 2 4-cycles  2! 4^2  3^2 3^3 2^6          36

Diag Ref (6) 2 2-cycles  2! 2^2  3^2
               4 1-cycles  4!    1    4! 3^3 2^4       216

Inv Rot/6  (8) 1 6-cycle 6    3
               1 2-cycle 1    3    3^3 2^4          9

Axis Ref (3) 4 2-cycles  4! 2^4  3^4 4! 3^5 2^4    1944

Inversion  (1) 4 2-cycles  4! 2^4  3^4 4! 3^4 2^4       648
                                                      -------
                                    | GC\Conj(M) | =  1841970

Counting M-conjugacy classes of the entire Rubik's cube

M class          Edge       Corner    Corner times edge
  (class size)    F.P.       F.P.          / (96*class size)
===============  ==========    ========= =======================
Identity (1) 12! 2^11    8! 3^7    901,083,401,551,872,000

Axis Rot/2 (3) 6! 3 2^12    4! 3^4 2^4             955,514,880

Rot/3    (8) 4! 3^4 2^6 3^5 2^4                   629,856

Diag Rot/2 (6) 5! 3 2^13    4! 3^4 2^5             318,504,960

Rot/4    (6) 3! 3 2^10    3^2 2^6                      18,432

Inv Rot/4  (6) 3! 3 2^10    3^3 2^6                      55,296

Diag Ref (6) 5! 3 2^13    4! 3^3 2^4             53,084,160

Inv Rot/6  (8) 2! 3^2 2^7 3^3 2^4                      1,296

Axis Ref (3) 4! 3^2 2^14 4! 3^5 2^4          1,146,617,856

Inversion  (1) 6! 2^12    4! 3^4 2^4             955,514,880
                                          -----------------------
                           | G\Conj(M) | = 901,083,404,981,813,616

These results have been corroborated and expanded by use of
combinatorial computer programs, to be described in a later message.

Dan Hoey
Hoey@AIC.NRL.Navy.Mil

[ 本帖最后由 sokoban 于 2009-1-7 00:06 编辑 ]

作者: haohejiao 时间: 2009-1-7 01:10:29

很深奥的问题今天先学点明天继续

作者: ggglgq 时间: 2009-1-7 09:19:01

　　
　　
　　
　　
　　
　　
　　　　
　　楼主是个有心人呀！

楼主的问题请大家参考： 正六面体二阶魔方- 48　“同态”
　　
　　http://bbs.mf8-china.com/data/attachment/forum/dvbbs/2006-5/20065719274976097.rar
　　
相关论述请参考：

二阶魔方的最远状态

　　http://bbs.mf8-china.com/viewthread.php?tid=1850&extra=page%3D1&page=10
　　
　　当然，正六面体二阶魔方-48 “同态” 很容易推广为楼主的一般性问题。　　
　　
　　
　　正如 20 楼 sokoban 所说，对于正六面体三阶魔方，

“考虑到颜色对称性之后，状态数只有：901,083,404,981,813,616 ，也是

很大的一个数字。不考虑对称性的数字为：43,252,003,274,489,856,000  。”


即便进行 48 “同态”后，甚至再加上“逆同态”的处理，对于  正六面体三阶

魔方来说，也是“杯水车薪”呀，路漫漫 ......
　　
　　
　　
　　

作者: xiaotnai 时间: 2009-1-8 00:05:40

呵呵谢谢大家帮忙解答我也是想到什么问什么可能有些比较弱智的问题
大家也不要见怪我数学是在不是很好才把问题拿出来的
因为写算法之前必须要做一些统计我才能从众多方法里选出一个最佳的方法

再次谢谢所有回帖的人以后有新的想法我还会来在问的

作者: Atato 时间: 2009-1-9 14:14:35

原帖由 smok 于 2009-1-6 09:16 发表
三阶的角块为什么不能跟棱块换位？外表看上去完全一样嘛，你们这些高手为什么不好好讨论一下这个问题？

SMOK的问题都是很哲学化的问题啊.哈哈
我觉得很简洁的答案是:旋转轴在各个面的中心.

作者: pengw 时间: 2009-1-10 10:58:06

要说清楚楼主的问题，请先弄清楚魔方状态的定义或者说，你是相对于一个什么定义来讨论问题。像ggglgq这样删贴大师最独到的地方就是不须要概念或胡乱定义，所以他说五角星也是魔方，任何人跟他争论的结果将是自已疯掉，他没有逻辑思维，所以相似变换就被说成了解决上帝之数的最小步理论。

[ 本帖最后由 pengw 于 2009-1-10 11:01 编辑 ]

作者: 黑白子 时间: 2013-9-4 12:25:09

sokoban 发表于 2009-1-7 00:03
要计算排除颜色的对称性后的状态数，就需要用一点群论的知识了。涉及到共轭类、burnside 引理等等。

考虑 ...

能翻译成中文吗？

作者: 黑白子 时间: 2013-9-4 12:26:20

ggglgq 发表于 2009-1-7 09:19
　　
　　
　　

48同态能推广到高阶魔方吗？还是仅限于2、3阶魔方？

作者: ggglgq 时间: 2013-9-5 12:59:51

　　
　　

当然能推广到高阶魔方。
　　
　　
　　
　　
　　
　　

作者: 黑白子 时间: 2013-9-5 16:18:57

ggglgq 发表于 2013-9-5 12:59
　　
　　

举个4阶的例子吧？

作者: 黑白子 时间: 2013-9-5 16:21:22

ggglgq 发表于 2013-9-5 12:59
　　
　　

这个帖子的20楼有三阶48同态后的数字和计算方法，刘老师能否翻译成中文？

作者: ggglgq 时间: 2013-9-5 20:13:48

　　
　　


我想，没有必要找四阶的了，找个正六面体二阶魔方的足可以说明问题了，（相关软件：

http://bbs.mf8-china.com/data/at ... 065719274976097.rar  ）

比如这个 48 自同构： URFR'U'（这个是状态，并非公式，只是用 URFR'U' 表示而已）有 48 个不同

的状态，统称“　48 自同构”，即可以用 URFR'U' 表示 48 个不同状态的自同构。



48 自同构 URFR'U' 有 48 个不同的状态，对于正六面体二阶魔方适用，对于大于二阶的正六面体魔方均适用。



顺便说一下，我的英语很烂。对于诸如正六面体三阶魔方上帝之数的英文资料也仅仅是能凑合着看，对于

里面的术语也不知道怎么翻译为好。有需要这方面资料的，请另找高人。  比如：

http://www.math.rwth-aachen.de/~ ... _of_cube_space.html
　　
　　
　　
　　
　　
　　
　　
　　
　　

附件: 48.PNG (2013-9-5 20:13:07, 39.93 KB) / 下载次数 75
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjIyMzA1fDRjNmUxZDhlfDE3MzI2MjA3MTl8MHww

作者: 黑白子 时间: 2013-9-6 22:41:39

本帖最后由黑白子于 2013-9-7 12:38 编辑

ggglgq 发表于 2013-9-5 20:13
　　
　　

48同态除了下面的外层对应关系，在4阶以上高阶魔方中是否还要增加内层的对称对应关系？
F<-->F'
B<-->B'
U<-->U'
D<-->D'
L<-->R'
R<-->L'

作者: ggglgq 时间: 2013-9-7 07:17:49

　　
　　
　　
　　

当然要加。

另外，好像 32 楼的 R<-->L 是笔误。
　　
　　
　　
　　
　　
　　

作者: 黑白子 时间: 2013-9-7 12:49:16

ggglgq 发表于 2013-9-7 07:17
　　
　　
　　

谢谢ggglgg老师！另外，32楼已改正错误。坦率地说，不是笔误，而是粗心！写完帖子后没有认真检查，这种态度是对读者不负责任，要不得的，以后一定要改正的！至此，我们之间的误解已全部解开！

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