[转帖]魔方与群论

cube_master

摘自：http://www.tianyaclub.com/new/techforum/Content.asp?idWriter=0&Key=0&idItem=180&idArticle=534824

『科学论坛』 [基础科学]魔方与群论

作者：尤里西斯1 提交日期：2005-6-24 23:10:52

　　刚上大学时，曾经花了一个多月把魔方玩会了（能从任意情况变回原来的六面）。当时还没有学群论，所以只是玩。后来学了群论后，再考虑魔方，发觉还是不大理解两者之间的关系。这才体会到群论的不好理解。等再后来，群论学得深入后，才彻底理解了魔方。现在把魔方从群论的角度做一个解释，如果你不能理解的话，就说明你的群论还没有学透！
　　
　　首先解释一些概念．我们称一个群G所含元素的个数叫做它的阶数，我们用|G|表示．
　　
　　n阶置换群S(n)：含n个元素的集合到自身的所有1-1映射按照映射的复合构成的群。该群的阶数（所含元素的个数）为n!．置换群中的元素分两类，一类是偶变换，一类是奇变换．奇偶性按照复合关系有以下性质．奇复合奇＝偶，奇复合偶＝奇，偶复合奇＝奇，奇复合奇＝偶．
　　
　　两个群G和H的直和群G+H：该群元素由形如(g,h)的元素构成，其中g属于G，h属于H．(g,h) (u,v)= (gu,hv)．将(g,h)映为g，和将(g,h)映为h，分别为从群G+H到G，和从群G+H到H的群同态，叫做投影同态．
　　
　　我们把处在魔方顶点位置的8个块叫做顶点块，把处在魔方棱上的除了顶点块之外那12个块叫边块，把其余的处在魔方的面的中心点的6块叫面块．定义了块以后，我们就可以把魔方理解为一个变换群M了．其中M的元素为块集合到自身的1-1映射（即变换），群乘法就是1-1映射的复合（即变换的复合）．
　　
　　我们把魔方的六个面按空间位置分别称为前、后、左、右、上、下层．我们称处在前后两层中间的那层叫X层，称处在左右两层中间的那层叫Y层，称处在上下两层中间的那层叫Z层．我们用层加括号的方法表示对相应的层进行90度旋转其它块不动的变换，旋转的方向如图1，其中坐标轴穿过面块，原点在魔方的中心．作为群，M由以上9个变换生成（可以更少一些）．
　　
　　
　　图1
　　
　　定义C为由变换(X)，(Y)，(Z)生成的M的子群．我们把C生成的M的正规子群记为N(C)．注意，C比N(C)小！N(C)是M的保持8个顶点块不动，只动边块和面块的变换所构成的子群，这样的变换可以只由(前)，(上)，(左)等变换复合而成．由群论知识，|M|=|N(C)||M/N(C)|，其中M/N(C)表示商群．
　　
　　下面我们考虑群M/N(C)的结构．它就是将魔方除了顶点块不变外，将所有的其它块的颜色全部刷成同一种新的颜色后所对应的简化魔方的变换群（其实就是2阶魔方）．而变换（见图2）
　　(前)(前)(前)(下)(前)(下)(下)(下)(右)(右)(右)(下)(下)(右)(右)(右)(下)
　　将处在前层和下层两层共同的边上的两个顶点块互换位置，将其它顶点块不动．这说明M/N(C)可以将任意两个块互换同时保持其它块不动，而这样的变换生成了整个置换群，也就是说M/N(C)与S(8)同构．所以，|M/N(C)|=8！=40320．
　　
　　图2
　　
　　下面考虑N(C)的结构，它只改变边块和面块的位置，而永远不改动顶点块的位置．注意到魔方在变换过程中6个面块是刚体结构，而魔方的变换也总是把边块映到边块，所以N(C)为S(12)+S(f)的一个子群，其中S(12)为将所有边块随意变换位置的12阶置换群，S(f)为六个面块作为由坐标轴连接起来的刚体到自身的旋转变换，该群很容易验证其阶数为24．那么是否有N(C)＝S(12)+S(f)呢？不对．
　　令S(f+)为S(f) 的所有偶变换生成的子群，则|S(f+)|=12．考虑N(C)作为S(12)+S(f)的子群，所有形如(1,x)，x属于S(f)的元素构成的子群U．U就是N(C)中所有保持12个顶点块不动，只动6个面块的变换．U自然也为S(f)的子群．变换
　　(X)(Y)(X)(X)(X)(Y)(Y)(Y)，
　　(Y)(Z)(Y)(Y)(Y)(Z)(Z)(Z)，
　　(Z)(X)(Z)(Z)(Z)(X)(X)(X)，
　　(X)(Y)(Y)(X)(X)(X)(Y)(Y)，
　　(Y)(Z) (Z) (Y)(Y)(Y)(Z)(Z)，
　　(Z)(X) (X) (Z)(Z)(Z)(X)(X)，
　　正好生成了群S(f+)，所以，U包含S(f+)．那么可不可能U比S(f+)大呢？不可能．因为如果U比S(f+)大，则U含S(f)－S(f+)中的元素，也就是说U包含奇变换．而M的9个生成元都是偶变换，也就是说M的所有变换都是偶变换，所以U不可能包含奇变换．所以U=S(f+)．而变换
　　(前)(Y)(Y)(Y)(前)(前)(Y)(Y)(Y)(前)(前)(Y)(Y)(Y)(前)(前)(前)
　　将同处在前层和Z层的两个边块互换位置，将处在Y层的4个面块（不是边块！）沿变换(Y)的逆向旋转了90度，将其它块保持不动．由这个变换再经过简单的复合我们很容易得到N(C)包含所有以下的变换：(x,y)，x为将任意两个边块互换位置，其它边块保持不动的变换，y为将面块沿任一坐标轴旋转90度（方向任意）的变换．这说明N(C)为S(12)+S(f)的如下形式的元素生成的子群，(u,v)，u,v的奇偶性相同．所以2|N(C)|=|S(12)+S(f)|=|S(12)||S(f)|．|N(C)|=2874009600．
　　
　　最后|M|=|N(C)| |M/N(C)|=115880067072000．
　　
　　至于说用最少步变换到任意位置的问题是个不比阶数问题难却还要复杂的问题，而且这个问题的解决和群论关系不太大，所以就没有研究了．

pengw

写一个复原四阶的程序就行了，当然，运行结果是一组复原给定状态的公式

[ 本帖最后由 pengw 于 2010-4-9 20:34 编辑 ]

铯_猪哥恐鸣

最少步我肯定写不出，如果只要一个能解出解答的，不限步数的，不止我会做，很多人都会。。。

pengw

也不要说远了，也不去搞什么上帝之数，你就搞一个四阶全色求解，我想就足以证明你的能力了，你愿意试试吗？

pengw

基于BASIC，那时，我们还没有更好的工具。你不信？要不要再开一个专贴来讨论？搜索一个二阶最远状态，相当于搜索三阶一个单簇，单簇有什么好玩的，什么也证明不了，三阶才是入门起点。

你要是真正弄懂了N阶定律，原则上，N阶求解都能编写出来，你知道为什么吗？

[ 本帖最后由 pengw 于 2010-4-9 16:40 编辑 ]

铯_猪哥恐鸣

求源程序，想知道当时的程序是怎么写的。。。

[ 本帖最后由 铯_猪哥恐鸣 于 2010-4-9 16:33 编辑 ]

pengw

回24楼：

玩魔方不过就三种意义:

1.如何变换到指定状态，方法是遵循状态规则
2.如何实现任意二个状态最短路径变换，方法穷举
3.如何找出最远状态，方法穷举

要说速拧，人都是外行，谁也没有机器快
要说计算机求解，20年前，程序求解三阶全色任意状态转换是我的大学毕业设计课题，那时，你可能还没有出世哦，哈哈哈，不好意思，这是事实哦。

千万不要将计算机算法技术当着魔方变换规则，你在很多时候都将二者搞混了

---------------------

另外，你有一个不好的习惯，喜欢信口开河，说些无根无据的话，做些无证明、无实例、无实证的事，这对玩理论的人来说很致命哦，希望改正。我们真是老，希望找一个杰出的、实实在在的、在推动魔方理论发现方面有杰出贡献的人接班，一直在密切关注你、“刺激”你，但愿找到不凡的证明

[ 本帖最后由 pengw 于 2010-4-9 16:40 编辑 ]

limite034

原帖由 铯_猪哥恐鸣 于 2010-4-9 01:32 发表
这几天莫明上不了论坛，刚上来就发现楼上高明的言论。。。发现楼上一棒子就把当前走在最少步领域前沿的人们的努力给打死了。。。还有其实我个人认为，上面你说得什么高深的东西，不都是基础么。。。线性代数，群论， ...

枚举？能解释“枚举”是什么意思吗？是不是说，举出的例子，无法找到摧毁的它的另一个例子（即：20和21）。
我理解你的话的含义是：如果穷举完成后，发现“枚举”结论是对的。是这个意思吗？

铯_猪哥恐鸣

1。我没有轻视N阶定律的作用，但在算法方面，它只能作为基础，而非核心
2。不是如果仅仅是穷举，是可以证明对于魔方最少步问题只能通过穷举，不然你给出一个不是穷举的算法？
3。玩得快？你是在和我谈速拧还是计算机求解？这两块你可都是外行啊。
4。话说我最近发现用复矩阵来表示魔方变换并以此证明很多原来抽象的结论将方便、直观的多。

pengw

问题是,现在所谓的玩得更快的技术仅仅还只是穷举,但凭这一点就足以说明现在的努力是一个什么含意,再理直气壮的语言实在比不过一个小小的实证要求,可惜,就这一点点最基本的最可怜的实证就是千呼万唤不见芳踪,虽然大道理,大理论,大套路已飞得满天是云,为什么?难到不能实在一点?魔方除了玩得快一点真的就没有更多的道理?哈哈哈

N阶定律真的仅仅只是告诉你魔方只能变成什么样?公式循环周期是如何计算的?什么样的交换可行与不可行难到不是状态理论说了算?状态数算法原理是如何构造的?无论你玩得多快,你的套路难到不受制于状态理论?

如果仅仅是比穷举,那么可以认为,还根本没有玩得快的理论.因而当前关于玩得快的话题实在没有什么值得骄傲的地方和说法.二阶以其极少的状态数,根本不足以成为范例,可以说,怎样做,在二阶上都不为过.更不要说有人承认的骰子魔方.

再说,如果你连魔方能变出什么和不能变出什么都不清楚,你又如何去构造一个完整的状态库?你又凭什么去穷举去搜索?发表高论一定要注意说话的前后逻辑关系,不要因为自已侧重于某一方面就轻视另一方面,要知道,你的侧重点恰恰严重受制于你轻视的问题.

[ 本帖最后由 pengw 于 2010-4-9 07:50 编辑 ]