关于魔方的有多少态的问题

mrzs

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

乌木

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

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

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

我的想法对吗？

乌木

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

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

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

xiaotnai

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


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

具体 ...

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

xiaotnai

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

conwood

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

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


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

乌木

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

乌木

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

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

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

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

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

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

七夜

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

sokoban

要计算排除颜色的对称性后的状态数，就需要用一点群论的知识了。涉及到共轭类、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 gc1,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 编辑 ]