魔方吧·中文魔方俱乐部

标题: 证明才干的使命:征寻“计算三阶纯色任意有限转动集对应的状态数“的通用算法 [打印本页]

作者: pengw 时间: 2010-4-23 09:41:18 标题: 证明才干的使命:征寻“计算三阶纯色任意有限转动集对应的状态数“的通用算法

---------------
说明:干点实事胜过滔滔口水,这里发一个征集论文的贴子.
---------------
定义:有限转动集,不包含所有可能的转动方式，转动集由步数（90度/步）大于或等于1的公式组成，集合中元素无使用顺序，每个元素无使用次数限制
---------------
命题:寻找计算任意有限转动集对应的状态数的通用方法，此方法手工操作可行
---------------
命题举例:{UD‘,RL’,FB‘}能转出多少状态，答案是768，那么:{UD,RL,FB‘}和{R，U，F}又是多少？
---------------
这是公认的爆头命题，更是才华无边的新人证明自已的绝好命题，能者勇者们，有谁敢于接招？不限最小步相关人士参与
---------------
要求：
1。明确描述算法原理，为兼顾大家的差异，不得使用任何计算机语言来描述
2。设计算法，限用java语言描述，其它非计算机语言类描述方法不限
3。要有包含计算过程说明的计算实例
4。拒绝无实例空谈
5。拒绝穷举方法，仅限于验证
6。附带设计验证方法和验证实例
7。建议验证操作由乌木和大烟头负责

附：玩理论的人都须要能证明自已实力的论文，对于成功解决此问题的人，将建议坛主升作者为本版版主之一，论文永久置顶

[ 本帖最后由 pengw 于 2010-4-23 10:44 编辑 ]

作者: yq_118 时间: 2010-4-23 09:44:32

原帖由 pengw 于 2010-4-23 09:41 发表命题举例:{UD,RL,FB}能转出多少状态，答案是768，那么:{UD‘,RL,’FB‘}和{R，U，F}又是多少？

{UD,RL,FB}反正不是768.{UD‘,RL,’FB‘}才是768.{R，U，F} 7!*3^6*9!*2^8/2

[ 本帖最后由 yq_118 于 2010-4-23 20:23 编辑 ]

作者: 宇枫幽蓝 时间: 2010-4-23 09:45:53

很好，支持理论研究！谢谢楼主能走向共和！

作者: pengw 时间: 2010-4-23 09:51:25

谢谢，理解

作者: superacid 时间: 2010-4-23 09:54:12

{R U F}就是左后下方的2x2x2固定了，其他都随机
所以是7!*3^6*9!*2^8/2=......

{UD',RL',FB'}貌似比较烦，要好好研究一下

[ 本帖最后由 superacid 于 2010-4-23 10:19 编辑 ]

作者: 疯子卡罗特 时间: 2010-4-23 09:55:48

。。。路过。。。。不说话

作者: superacid 时间: 2010-4-23 10:14:36

问一下LZ，不会JAVA怎么办...

作者: pengw 时间: 2010-4-23 10:30:23

java当今最通用的算法语言，懂的人最多

作者: 铯_猪哥恐鸣 时间: 2010-4-23 10:31:33

条件太宽泛了，除了枚举之外准确算法还没想到，倒是想到了一种基于各簇循环长度限制的蒙特卡罗随机算法。
接着想。。

作者: 铯_猪哥恐鸣 时间: 2010-4-23 10:33:07

暴强你就用C描述吧，java和C几乎一样的，能让大家看懂就好

作者: yq_118 时间: 2010-4-23 10:35:47

原帖由 pengw 于 2010-4-23 10:30 发表 java当今最通用的算法语言，懂的人最多

懂JAVA的人大多不懂算法，况且现在JAVA已经不是排名第一了。TIOBE 2010年4月编程排行榜不过话说回来，C和JAVA语法类似。版主也没必要限制那种语言。

作者: pengw 时间: 2010-4-23 10:46:07

很多人不能理解C的指针类，用数组就行了

作者: pengw 时间: 2010-4-23 10:48:36

很多人也不能理解C的类，用C也行，但要一个JAVA附本

作者: yq_118 时间: 2010-4-23 10:49:49

原帖由 pengw 于 2010-4-23 10:46 发表很多人不能理解C的指针类，用数组就行了

连个指针都分不清，还做什么算法，不过可以尽量不用。

作者: pengw 时间: 2010-4-23 10:52:57

指针不是必须，只是方便而已，完全可以用数组替代

作者: pengw 时间: 2010-4-23 10:54:11

命题的上限非常非常容易计算，为什么？不要以为是跟总状态相比

作者: pengw 时间: 2010-4-23 10:55:54

若在研究此命题中发生人身意外，责任自负，特此声明，不是玩笑

[ 本帖最后由 pengw 于 2010-4-23 10:57 编辑 ]

作者: pengw 时间: 2010-4-23 10:59:36

窃以为，可能要用到群论相关的计算，如果群论都算不出结果，那真是不知所云了

作者: superacid 时间: 2010-4-23 11:12:16

个人觉得这题过于宽泛，暂时没有能力解决，等学习了更高深的知识后再回头看看吧

作者: pengw 时间: 2010-4-23 11:13:22

通过对一楼命题的讨论，我认为可以明确以下问题：
1。这是不是讨论魔方问题
2。这是不是研究魔方问题的正确方向
3。如何看待转动受限的魔方
4。这类讨论的意义何在？对应现实问题，如地图，当封堵某些道路后我们还有多少选择？
5。这是一个总是有答案的问题吗？
6。如果甘心当忍者龟（抱定吃最大苦受最大累），理论还有何用？

作者: pengw 时间: 2010-4-23 11:15:53

定义是明确的，答案也是有限的，问题是可操作性如何？总是能操作吗？

作者: pengw 时间: 2010-4-23 11:17:16

这个问题，形象地比喻，就是在城市随意设路障后，要求回答最多还能去多少地方

作者: pengw 时间: 2010-4-23 11:24:45

这样的问题,不妨先拿二阶试手

作者: zykey 时间: 2010-4-23 11:26:59

感谢楼主分享..........................

作者: sokoban 时间: 2010-4-23 11:46:54

这个问题有多项式算法。

用置换群的语言描述这个问题，就是：给定一组生成元，这组生成元所生成的置换群有多少个元素？

具体的算法可参阅Akos Seress 著的《Permutation Group Algorithms》一书的第四章。
（或者其他的介绍置换群算法的书）

一些置换群的软件如 GAP （http://www.gap-system.org/）还实现了这些算法。利用 GAP，不难解决如 {UD,RL,FB‘}能转出多少状态这样一类问题。

[ 本帖最后由 sokoban 于 2010-4-23 11:48 编辑 ]

作者: yq_118 时间: 2010-4-23 11:54:58 标题: 回复 25# 的帖子

魔方还要考虑方向，可以把这个推广到魔方上面。

作者: 铯_猪哥恐鸣 时间: 2010-4-23 11:58:56

感谢楼上的解答，我昨天粗略的看了下群论还没怎么看明白，不愧是高级数学工具啊。。。

作者: sokoban 时间: 2010-4-23 11:59:07 标题: 回复 26# 的帖子

把魔方看成 6 x 9 =54 元置换群，方向问题已经隐含在里面。不需推广，就能够解决了。

作者: yq_118 时间: 2010-4-23 12:08:18

确实，用铯的广义变换的思想，魔方群只是S54的一个子群，
多谢！

作者: sokoban 时间: 2010-4-23 12:13:07

GAP 的主页上有用 GAP 算三阶魔方的相关问题的实例，值得看看：

http://www.gap-system.org/Doc/Examples/rubik.html

作者: superflip 时间: 2010-4-23 12:33:56

GAP当然能算这类问题~

ps：我的本意是不通过计算机，看能否找到某些有意思的技巧来计算 {UD,RL,FB}的大小，类似计算{R,U}时利用捆绑角块对的小技巧。不过既然版主弄出这么个置顶帖，对于推广群论也有一定帮助~

作者: pengw 时间: 2010-4-23 14:15:42

原帖由 sokoban 于 2010-4-23 11:59 发表
把魔方看成 6 x 9 =54 元置换群，方向问题已经隐含在里面。不需推广，就能够解决了。

非常好的主意,能不能在此深入浅出、结合具体实例进行原理性讲解并做普及性推广？顺便带动群论知识讨论，相信这样做对大家都非常有利

[ 本帖最后由 pengw 于 2010-4-23 14:17 编辑 ]

作者: pengw 时间: 2010-4-23 14:22:07

对于N阶魔方，似乎无须群论我们也有办法从整体上把握所有变换，然而，解决有限转动集这类问题，已有的方法已显得无能为力，某一天，理论玩家若都能用群论来描述魔方变换，那将是整体实力的巨大提升

[ 本帖最后由 pengw 于 2010-4-23 14:27 编辑 ]

作者: yq_118 时间: 2010-4-23 14:42:59

先去学习下这个算法，回头来写程序解决。

作者: 铯_猪哥恐鸣 时间: 2010-4-23 14:45:57

支持，但个人认为现在主要语言和精力成比较大的问题。群论博大精深，想在短期入门根本不可能。并且大部分相关知识都是用英文描写的，虽说搞理论的绝不会在乎读外文书籍，但是对于魔方吧上的交流大家都用一片片的英文术语总觉得欠妥。

作者: pengw 时间: 2010-4-23 14:47:39

网上有中文版基本知识

作者: 铯_猪哥恐鸣 时间: 2010-4-23 14:54:30

对了，刚想起来，其实N阶定律中也引用了很多群里的术语，如奇变换（对应于群论中的奇置换），共轭等等

作者: pengw 时间: 2010-4-23 17:22:37

偶太簇本质上就是一个偶排列，奇态簇本质上就是一个奇排列，奇偶性可以用逆序数来度量，也可以用偶元环的个数来度量，同一时间，有多少个奇排列和多少个偶排列是确定，N阶定律中扰动关系的本质就是描述不同簇的奇偶排列搭配关系，其中簇的偶元环数量的奇偶性对应于簇的奇偶性，总体上讲，所有簇的奇偶性搭配一但确定，余下的全是三置换或称为偶数步公式的活，包括色向变换。

因此N阶魔方变换实质就二样：

1。确定簇的奇偶搭配，二三阶有二种，四五阶有四种，任何一个状态只含一种
2。用偶数步（90度/步）变换解决所有余下的问题

这样的解释已经非常本质了，难以置信的是N阶魔方的变换规则仅仅只有这些，不过在总结N阶定律时，却历经坎坷，最本质的往很简单，却隐藏得很深，总结时，并没有意识到脚已经伸到群论中去了

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

为什么利用N阶定律可以预言总状态数却难以计算有集转动集的状态数？也许这是下一个将提出来讨论的问题，从中大家会看到一些很本质的思维。另外一个启示就是，虽然可能没有学过群论，但通过自已的总结和归纳，也会不自觉地使用群论规则

[ 本帖最后由 pengw 于 2010-4-23 17:51 编辑 ]

作者: pengw 时间: 2010-4-23 18:00:21

记得铯在前面一个有限转动集跟贴中已提到棱簇分析裂为三个簇，看似荒谬，其实这正是限制转动方式后带来的后果，即原来同一个簇的块变得互相不能置换，我认为限制转动方式后的变换已非原来魔方的变换，此时的魔方已不是原来定义的魔方。

作者: yq_118 时间: 2010-4-23 18:04:39

这个好像要用schreier sims algorithm

作者: cube_master 时间: 2010-4-23 20:02:15

进来关注一下。

作者: 宇枫幽蓝 时间: 2010-4-23 20:03:42 标题: 回复 41# 的帖子

老大出现了！我们列队欢迎！

作者: 200100 时间: 2010-4-23 20:06:19

关注完就跑了。。。。老大躲着谁呢？？？

作者: aubell 时间: 2010-4-23 20:14:40

真的很难吗？我来算一个试试。黑人手下无难题（初学者不懂害怕的意思

），希望别错了。
就<R,U,F>吧。
很明显，RUF不会打乱BLD位置的角块以及与它相邻的3个棱。
而且，只要LBD位置的角和三个棱处于完好位置，用RUF就能还原其它所有。
假如不限制任何操作，这个角块在整个魔方中的位置有24种方式，
三个棱分别是24,22,20放置种方式。
24*24*22*20=253400

但现在，这三块被固定成放置一种方式了。
所以，总状态数除以 253400就是所求。
170659735142400

请大师指正

作者: 乌木 时间: 2010-4-23 21:03:12 标题: 回复 44# 的帖子

我有点问题还未想通：
你说“只要LBD位置的角和三个棱处于完好位置，用RUF就能还原其它所有。”
那么，这些被“RUF”复原的“所有”态之中，如果有的态当初是从复原态出发，打乱时不仅做过“RUF”，还做过别的表层转动，但是结果却又是“LBD位置的角和三个棱处于完好位置”，那么，是否仍然是“用RUF就能还原”的呢？
如果这种态不能单单“用RUF就能还原”，那么，就不能用总态数除以253400 。对吗？
我对这类问题老是会出错，望指点。

也就是问，“LBD位置的角和三个棱处于完好位置”的态，获得它们时的打乱过程，不一定限于“RUF”三个层的动作，这里只是探讨复原它们的过程有“RUF”的限制。对吗？

[ 本帖最后由乌木于 2010-4-23 21:09 编辑 ]

作者: yq_118 时间: 2010-4-23 21:06:33 标题: 回复 45# 的帖子

可以证明，只要DBL的2*2*2完成了，就可以只用R,U,F还原，当然魔方没装错。

作者: 乌木 时间: 2010-4-23 21:34:30

此外，是否可以不用总态数除以253400的算法，直接计算其余7个角块和9个棱块在“BLD角块以及与它相邻的3个棱”以外的位置上的变化数：
7！×3^6×9！×2^8 / 2 ＝1.7065973×10^14

[ 本帖最后由 pengw 于 2010-4-23 21:56 编辑 ]

作者: WitEden 时间: 2010-4-23 21:41:40

虽然我是学数学的，但是没有时间研究这些！现在都静不下心来！

作者: pengw 时间: 2010-4-23 21:57:02

原帖由乌木于 2010-4-23 21:34 发表
此外，是否可以不用总态数除以253400的算法，直接计算其余7个角块和9个棱块在“BLD角块以及与它相邻的3个棱”以外的位置上的变化数：
7！×3^6×9！×2^8 / 2 ＝1.7065973×10^14

这是通用算法的一个子集,这个计算的意义在于给出受影响区状态数的上限,这种计算完全是基于状态变换规则的直接运算,然而事实,上于转动限制,你上面计算出来的很多状态是无法转出来的,举例:

{U,F},无论如何转不出二棱和二角置换，其它块不变。虽然这些块都位于受影响区域，但就是转不出来，然而，不限制转动就可以转出来，即同一受影响区域，限制与不限制，其结论可能并不完全相同。

[ 本帖最后由 pengw 于 2010-4-23 21:59 编辑 ]

作者: pengw 时间: 2010-4-23 22:01:19

就目前所见，都是一单了一单的个案分析，找出一个通用方法是一楼的目标，有一点很清楚，限动状态数小于或等于非限动状态数

[ 本帖最后由 pengw 于 2010-4-23 22:05 编辑 ]

作者: 铯_猪哥恐鸣 时间: 2010-4-23 22:08:58

前面s版已经给出国外的一个通用算法了，就看吧里谁有空如理解和实现了。

作者: yq_118 时间: 2010-4-23 22:19:26

找了篇英文的论文，正在研究。

附件: essay.pdf (2010-4-23 22:19:26, 347.55 KB) / 下载次数 35
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=OTQyODR8NjZjYjkzZDB8MTcyODEzMzc0MnwwfDA%3D

作者: pengw 时间: 2010-4-23 22:45:34

楼上愿意将那篇关于交换群算法的文章翻译成中文否?没想到这么快就有重大发现,大家赶快学群论吧,至少要撑握交换群理论

[ 本帖最后由 pengw 于 2010-4-23 22:52 编辑 ]

作者: superacid 时间: 2010-4-24 13:14:07

正在努力学习，不过看英语没有中文舒服...

作者: aubell 时间: 2010-4-24 13:48:39 标题: 回复 25# 的帖子

你成功安装了gap吗？我下载了，安装起来好像很麻烦，还没弄好呢。
准备切换到Linux下再试。

作者: yq_118 时间: 2010-4-24 14:42:57 标题: 回复 55# 的帖子

可以用啊，解压到C盘，运行 C:\gap4r4\bin\gap.bat就可以，要是在其它位置就要改下bat了。

作者: pengw 时间: 2010-4-24 18:46:55

貌似构造转动子集对应的生成元子集,交给GAP计算就行了,从群论的角度看,有点异乎寻常的简单,看来这个问题早已经有人解决.现在的问题变成了看谁把别人的方法通俗易懂地介绍给大家.

通过构造魔方生成元的方式计算出来的总状态数和通过变换规则计算出来的总状态数竟完全一样,这的确是太有趣,看来这里的确是存在解决问题的二个不同的思路,即群论的思路和非群论的思路(N阶定律),虽然生成元方式在计算任何转动子集对应的状态都很容易,但就魔方变换规则的推导和描述及N魔方变换本质的描述来看,我认为N阶定律更为简单,完全不涉及高深的群论知识,但群论知识解决所有异构魔方问题都很容易,另外一个有趣的现象是,GAP的讨论中,似乎回避了中心块变换

[ 本帖最后由 pengw 于 2010-4-24 19:00 编辑 ]

作者: 乌木 时间: 2010-4-24 23:03:02

原帖由 pengw 于 2010-4-23 21:57 发表
这是通用算法的一个子集,这个计算的意义在于给出受影响区状态数的上限,这种计算完全是基于状态变换规则的直接运算,然而事实,上于转动限制,你上面计算出来的很多状态是无法转出来的,举例:

{U,F},无论如何转不出二棱和二角置换，其它块不变。虽然这些块都位于受影响区域，但就是转不出来，然而，不限制转动就可以转出来，即同一受影响区域，限制与不限制，其结论可能并不完全相同。

这是你在49楼回答我47楼的。
那么，也就是说，我的答案“1.7065973×10^14 ”（我这答案和44楼aubell的另一算法的答案一样）是不对的，太大了。可见，aubell的答案也不会对，是吧？

是不是因为{R,U,F}中包含{U,F}，所以才造成1.7065973×10^14 不对？那么，尽管“{U,F}无论如何转不出二棱和二角置换，其它块不变”，{U,F}转不出的态就让它转不出好了，这与{R,U,F}的态数有1.7065973×10^14 又有何干？aubell的例子是求{R,U,F} ，怎么会受“{U,F}转不出二棱和二角置换”的影响呢？{U,F}转不出的，不等于{R,U,F}也转不出吧？

按照类似的说法，{R,U,F}的答案中不仅要排除“{U,F}无论如何转不出二棱和二角置换，其它块不变”，还要排除{R}等等的转不出态吧？那么，究竟{R,U,F}的含义是什么呢？又怎么理解46楼yq_118说的“可以证明，只要DBL的2*2*2完成了，就可以只用R,U,F还原，当然魔方没装错”呢？是否yq_118此说也错了？

这问题对我来说，感到蛮搅的，想了两天，还是没有弄懂pengw的答复，继续请教。

[ 本帖最后由乌木于 2010-4-24 23:15 编辑 ]

作者: yq_118 时间: 2010-4-24 23:12:24 标题: 回复 58# 的帖子

你的结论是对的。可以转出两棱两角换以及两棱翻。

那么，究竟{R,U,F}的含义是什么呢？
意思就是仅用R,U,F三种转动就可以还原的所有状态。

[ 本帖最后由 yq_118 于 2010-4-24 23:17 编辑 ]

作者: pengw 时间: 2010-4-24 23:24:42

回58楼:
你是用基于变换规则的直接计算:7！×3^6×9！×2^8 / 2 ＝1.7065973×10^14,从算式就看得出来是直接计算,直接计算并不总是适合转动子集状态计算,{U,F}是拿来举例，我的意思是说{U，F}转不出A（2）M（2），虽然在其影响的区域A（2）M（2）是合法的，举例跟{U，F，L}无关。

再举例：{UD‘，LR’，FB‘}，影响所有块，但转出的状态仅仅是64*12

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

转动子集状态计算与直接计算在概念上是相当不同，因此千万要注意这个问题

[ 本帖最后由 pengw 于 2010-4-24 23:30 编辑 ]

作者: 乌木 时间: 2010-4-24 23:26:53

｛R,U,F｝可以转出二棱和二角置换的一个实例：
[java3=250,250]
[param=scrptLanguage]SupersetENG[/param]
[param=scrpt]F' R' U' R F' R' U F' U' F' U F R F2 [/param]
[/java3]

意思理解错了，看60楼

[ 本帖最后由 pengw 于 2010-4-24 23:36 编辑 ]

作者: pengw 时间: 2010-4-24 23:33:38

最终的解决方法还是要在魔方交换群上构造对应于于转动子集的生成元，将生成元代入GAP计算，这是通用的一般性方法

作者: yq_118 时间: 2010-4-24 23:34:28

R U' R2 U F R U F2 U' F R2 F2 R2 F2 两棱翻的公式。
U2 F2 R2 F2 U' F' U F' R2 F U' F U' 三角换公式。
U2 R U R' U' R' U R U2 R U2 R' U R' U2 R 两角翻公式。
还有三棱换公式等，用这些公式就可以还原DBL的2*2*2完成后的魔方。

作者: 乌木 时间: 2010-4-24 23:35:25 标题: 回复 60# 的帖子

那么，我和aubell的关于｛R,U,F｝的答案1.7065973×10^14 还是没问题的，对吗？只是要注意不能错误推及到别的比｛R,U,F｝还要小的｛……｝，对吧？

作者: pengw 时间: 2010-4-24 23:45:49

回64楼：
确认仅凭{U，F，L}，每个簇任意三个块可以进行独立三元置换（或只看本簇，任意二个块可以独立置换），棱角任意二个块可以独立改变色向，满足这二个条件就可以直接计算，对任意转动子集这是一个晋适条件。我没有试过{U，F，L}是否满足条件，只是强调二种计算的差别

[ 本帖最后由 pengw 于 2010-4-24 23:55 编辑 ]

作者: 乌木 时间: 2010-4-24 23:54:34 标题: 回复 65# 的帖子

噢，对，条件不具备的话，直接计算的结果就会有水分。

作者: pengw 时间: 2010-4-24 23:59:27

所以要强调一下。要“推”“翻”别人的直接计算，找到任意一个不具备的条件就足够了

作者: Cielo 时间: 2010-4-25 00:46:17

原帖由 sokoban 于 2010-4-23 11:46 发表
这个问题有多项式算法。

用置换群的语言描述这个问题，就是：给定一组生成元，这组生成元所生成的置换群有多少个元素？

具体的算法可参阅Akos Seress 著的《Permutation Group Algorithms》一书的第四章。
（ ...

太感谢了！

以前在speedsolving上看到GAP不知道在什么地方找……

作者: pengw 时间: 2010-4-25 07:37:08

回65楼:

再举例：{UD‘，LR’，FB‘}，这组转动根本不会扰动任何状态,由此就可以判定直接计算是错误的.因此判断错误还要加上一条:是不是每个转动元素都改变扰动关系.

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

作者: 乌木 时间: 2010-4-25 09:26:20

本版块的N×N×N魔方在计算某些条件下的状态数时，除了上面说的由于转层受限所致的转不出的状态别误计入，还有，角块和棱块不能交换，这是不会弄错的。中棱块和非中棱块也不能交换，不同簇的非中棱块也不能交换，不同簇的心块也不能交换，这些也是要当心的。簇间扰动关系更要正确考虑。
顺便联想到问题的另一方面，在计算别的类型的魔方状态数时，要注意它（们）的“角块”和“棱块”性质有可能和N×N×N魔方的角块、棱块性质很不同，比如，其“角块”和“棱块”是可以交换的，计算时不能遗漏了这种变化的状态。比如SQ－1。

[ 本帖最后由乌木于 2010-4-25 09:32 编辑 ]

作者: pengw 时间: 2010-4-25 09:53:13

回70楼:

N阶定律及其一系列推论成立的一个重要前提就是，可以用已有的公式证明，每个簇可以自由置换，每一个有色向簇的任意二个块可以置换无关地独立变换色向，扰动关系总是可以由转层决定。如果得不出这些结论，则只能求群论回答问题了，幸运的是，正方体色子阵魔方的这些问题都很好确定，才使得描述要比群论简单很多的N阶定律得出世。就广义的魔方描述而言，还是由群论描述更具晋适性，虽然这种描述可能大多数人都看不懂。

虽然群论可以随意计算状态数，但是不清楚群论是如何求取扰动关系的数量，如何表达变换性质，而这些都是最实用的须要，对于更高阶的魔方，构造生成元的工作之巨，计算量之大，很多问题都变得难以确定，而用N阶定律则要简单很多。目前所有的群论描述中，都排除了中心块，或许中心块不满足群对元素的定义要求。

就目前面言，群论能告诉我的要比我们已经知道少很多，我曾看过一篇“群论在魔方中的应用”硕士论文，我的感觉是，作者更多是借助魔方来表达群论，而不告诉大家群论是如何解决魔方问题，且明显可以感觉到作者对魔方并不十分熟悉，讨论也限于三阶纯色。

[ 本帖最后由 pengw 于 2010-4-25 10:09 编辑 ]

作者: sing2 时间: 2010-4-25 11:11:24

高一的路过...不懂....

作者: yq_118 时间: 2010-4-25 12:14:25 标题: 回复 71# 的帖子

对与三阶全色魔方，仍然可以用群论。只要给每个中心加上四个编码，每转90°就让这四个编码轮换一次。

作者: pengw 时间: 2010-4-25 16:28:40

回73楼:
真是不谋而合,经典!楼上,如果专门给你开个魔方群相关的贴子,专门供你操作,讲解魔方群知识,你意下如何?理论区目前缺乏群论相关的知识贴

[ 本帖最后由 pengw 于 2010-4-25 19:04 编辑 ]

作者: yq_118 时间: 2010-4-25 19:15:04

版主愿意的话可以做个索引贴，大家可以把相关的内容整理出来或者翻译一些国外的资料。

我也愿意为论坛建设做些贡献，不过才疏学浅，对群论只是入门，最近在看那个算法才感觉个人能力的有限，以及以前对魔方认识的不足。

作者: pengw 时间: 2010-4-25 19:17:41

没关系,大家都是在战争学习战争的魔友,没有谁是专业的

作者: pengw 时间: 2010-4-25 19:59:17

还真看不出构造{UD',LR',FB'}的生成元与构造{U，D，L，R，F，B}的生成元有何差异，yq_118能解释一下否？

作者: limite034 时间: 2010-4-25 20:02:45

原帖由 pengw 于 2010-4-25 16:28 发表
回73楼:
真是不谋而合,经典!楼上,如果专门给你开个魔方群相关的贴子,专门供你操作,讲解魔方群知识,你意下如何?理论区目前缺乏群论相关的知识贴

欢迎欢迎，热烈欢迎

作者: yq_118 时间: 2010-4-25 21:24:19

gap的网站上的演示，｛U,D,R,L,F,B｝

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

cube := Group(( 1, 3, 8, 6)( 2, 5, 7, 4)( 9,33,25,17)(10,34,26,18)(11,35,27,19),
( 9,11,16,14)(10,13,15,12)( 1,17,41,40)( 4,20,44,37)( 6,22,46,35),
(17,19,24,22)(18,21,23,20)( 6,25,43,16)( 7,28,42,13)( 8,30,41,11),
(25,27,32,30)(26,29,31,28)( 3,38,43,19)( 5,36,45,21)( 8,33,48,24),
(33,35,40,38)(34,37,39,36)( 3, 9,46,32)( 2,12,47,29)( 1,14,48,27),
(41,43,48,46)(42,45,47,44)(14,22,30,38)(15,23,31,39)(16,24,32,40) );

------------------------------------
改一下就变成｛UD,RL,FB｝了
------------------------------------

cube := Group(( 1, 3, 8, 6)( 2, 5, 7, 4)( 9,33,25,17)(10,34,26,18)(11,35,27,19)(41,43,48,46)(42,45,47,44)(14,22,30,38)(15,23,31,39)(16,24,32,40)，
( 9,11,16,14)(10,13,15,12)( 1,17,41,40)( 4,20,44,37)( 6,22,46,35)(25,27,32,30)(26,29,31,28)( 3,38,43,19)( 5,36,45,21)( 8,33,48,24)，(17,19,24,22)(18,21,23,20)( 6,25,43,16)( 7,28,42,13)( 8,30,41,11)(33,35,40,38)(34,37,39,36)( 3, 9,46,32)( 2,12,47,29)( 1,14,48,27), );

------------------------------------------
至于｛UD',RL',FB'｝需要把相应的轮换倒过来写。

[ 本帖最后由 yq_118 于 2010-4-25 21:25 编辑 ]

作者: pengw 时间: 2010-4-25 23:07:05

回79楼：
GAP的举例中是5组/转层，转层的不同排列会影响状态数的计算否？你的答复只是调整了转层的排列，验证过否？我做了一个更短的测试，似乎与顺序无关关

gap> cube1 :=Group((1,2,3,4),(3,4,5,6));
Group([ (1,2,3,4), (3,4,5,6) ])
gap> cube2 :=Group((3,4,5,6),(1,2,3,4));
Group([ (3,4,5,6), (1,2,3,4) ])
gap> Size(cube1)
> ;
120
gap> Size(cube2);
120
gap>

[ 本帖最后由 pengw 于 2010-4-25 23:13 编辑 ]

作者: yq_118 时间: 2010-4-25 23:23:29

这个....
注意括号之间的逗号，我是把U和D的论换一共10个合成一个了...
这样就只有三个生成元了。

作者: pengw 时间: 2010-4-25 23:37:57

看下面，你谈的格式好象有问题

gap> cube :=Group((1,2,3,4)(3,4,5,6));
Permutation: cycles must be disjoint and duplicate-free
gap>

作者: yq_118 时间: 2010-4-25 23:43:29

这个不是格式问题，
Permutation: cycles must be disjoint and duplicate-free
意思是轮换不能相交和重复。
(1,2,3,4)(3,4,5,6)里面重复了，应该化简为(1,2,4)(3,5,6).

作者: pengw 时间: 2010-4-25 23:50:03

如此的话,{UF,UR}将无法计算？

作者: yq_118 时间: 2010-4-25 23:53:16

可以，不过要先化简，人工的话比较麻烦。

作者: pengw 时间: 2010-4-25 23:59:36

你的意思是，把UF执行一次，读出所有置换，再用到Group中，同理处理UR？如果处理一个公式，这不就成了计算的公式循环周期？

[ 本帖最后由 pengw 于 2010-4-26 00:05 编辑 ]

作者: yq_118 时间: 2010-4-26 00:05:53

用盲拧的方法读编码还是比较快。
如果处理一个，确实是公式的循环周期。

作者: pengw 时间: 2010-4-26 00:10:12

我明白了，再次建议你开一个魔方群或GAP相关的专题贴，结合魔方来讲解群论知识，我想支持的人会很多

作者: pengw 时间: 2010-4-26 00:13:02

跟公式循环周期计算相通，给我很大启示，不仅转层可以做生成元，直接读出的置换也可以做生成元，太妙了。尤其是不区分色向和块的置换处理方式，更是妙不可言。看来，GAP已经为本贴主题划上一个园满句号，同时又为大家打开了一个了解群论的窗口。

从上面的有限讨论中即可知道，GAP是魔方分析与研究难得的利器

[ 本帖最后由 pengw 于 2010-4-26 00:28 编辑 ]

作者: wangjiyuan 时间: 2010-4-26 06:00:03

要解决这个问题是需要时间的漫漫等待新斑竹？

作者: pengw 时间: 2010-4-26 07:14:28

感谢GAP软件解决了楼主的命题，不清楚GAP软件接受做版主的建议否，玩笑

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

作者: pengw 时间: 2010-4-26 07:45:10

感谢sokoban推荐GAP，同时感谢yq_118对GAP使用的一些细节补充，通过对GAP的使用获得的一个重要启示，即大家要重视群论知识的学习和应用。

群论是否可以解决所有魔方问题，比如，推导或预言三阶全色最大公式循环周期？目前尚不知道答案，有谁愿意分析一下否。

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

作者: 铯_猪哥恐鸣 时间: 2010-4-26 09:06:17

回楼上，我认为应该是可以的。求最大循环周期元素在群论里是有直接语言描述的。相信连有限元生成群大小都能求，求最大循环应该不是什么难事。

作者: pengw 时间: 2010-4-26 11:31:06

愿意举一个例子否

作者: aubell 时间: 2010-4-26 22:05:21 标题: 回复 56# 的帖子

多谢。搞掂！
万分感谢。

作者: aubell 时间: 2010-4-26 22:28:00

可惜不懂群论，只是看看热闹。
不知道用gap能否直接解魔方？
想必如果懂群论，也许用几行代码就有一个解魔方的程序诞生了。

作者: pengw 时间: 2010-4-27 06:48:20

原则上群论可以解魔方,但不适合手工解,解魔方的程序并不复杂,解上帝之数就要看你的计算机资源有多强大

作者: ANTY 时间: 2010-4-29 13:22:36

我是被“证明”吸引进来的~~

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