魔方吧·中文魔方俱乐部

标题: 二阶魔方状态集已发现哈密顿圈 [打印本页]

作者: 铯_猪哥恐鸣 时间: 2011-12-27 10:17:45 标题: 二阶魔方状态集已发现哈密顿圈

先解释一下什么叫哈密顿圈，对于魔方，它意思就是，找一个很长的公式，沿着这个公式一步一步转动，可以不重复的转到所有二阶的状态。
对于二阶魔方，它的长度为3674160步（对应二阶魔方的总状态数为3674160）。
最终生成的3674160步是用递归的方式定义的。
最后贴上英文原文。

Hamiltonian circuit for the entire 2x2x2 cube group
I have found a Hamiltonian circuit for the entire 2x2x2 cube group (3674160 elements).

I note that my solution was developed independently from the solution for the subgroup posted by cubemir.

For compactness, I use variables to define sub-sequences of moves.
The following conventions are used.
Upper case letters are used for the basic quarter-turn moves of the 2x2x2 puzzle.
· U represents turning the top face a quarter-turn clockwise.
· V represents turning the top face a quarter-turn counterclockwise (conventionally denoted U').
· R represents turning the right face a quarter-turn clockwise.
· S represents turning the right face a quarter-turn counterclockwise (conventionally denoted R')
· F represents turning the front face a quarter-turn clockwise (used in Appendix B).
· G represents turning the front face a quarter-turn counterclockwise clockwise (conventionally denoted F').

Variables denoted with lower case letters represent sequences of multiple moves.
Many of them are defined in terms of other lower case variables.
So recursive expansion is requred to get a plain sequence of individual moves.
If a letter is followed by an apostrophe, then the inverse of the indicated sequence is to be used.
This means that the order of the moves and direction of the moves must be reversed.
A line with a letter and an equal sign starts the definition for a maneuver.
The definition may extend over several lines until there is a line where another definition is started.
The variable z is used to represent the entire Hamiltonian circuit.

b=URURUR
a=bURUR
i=bbUR
c=VRiiVR
n=VRa
d=nn
e=ncUR
f=URcaVR
g=ncabVR
h=nbcaVR
j=ccaVR
k=bbVR
l=ncc
m=nUR
o=VRUR
r=adcURefknbhaodcURfccncabdodcURjabVRdccfcgdccfccVRicaURdnVRdljURURejaocdc
cfcglccadVRddURciVRcjURcecmcURcadVRdgaboURnbeccad
s=nbgaVRdblinVReckdbcanbVRmcURmcidoUR
t=URURnUUaURdVRihkhcecncabdVRdcURfURURhaVRdlfabnbVRdeckcfVRigkURdURcfccaUR
dVRdejhhejaoURdcURURefaVRegkglURcadVRddURciVRchejaoliVRVRigmcidVRnbeUReU
RcadVRdcabVRhURefaVRdhcjURgmefURmciddUUaURdVRicknbefaodcURjabnodlinboURe
URnbcadVRdgciVRcgncgcaURdVRddURURckURjURceURncabdVRccdcURfURURlURVRicaUR
dnVRdmccVRijaVRhcVRijaVRnbefaodURURglfaVReckdcURfabVRmhidnUUaURdeefknbha
odcURfccncabdodcURjabVRdccfcgdccfccVRicaURdnVRdljURURejaocdccfcglccadVRd
dURciVRcjURcecmcURcadVRdgaboURnbeccadVRnbgaVRdblinVReckdbcanbVRmcURmcidd
UUaURdVRihkhcecncabdVRdcURfURURhaVRdlfabnbVRdeckcfVRigkURdURcfccaURdVRde
jhhejaoURdcURURefaVRegkglURcadVRddURciVRchejaoliVRVRigmcidVRnbeUReURcadV
RdcabVRhURefaVRdhcjURgmefURmciddUUaURdVRicknbefaodcURjabnodlinboUReURnbc
adVRdgciVRcgncgcaURdVRddURURckURjURceURncabdVRccdcURfURURlURVRicaURdnVRd
mccVRijaVRhcVRijaVRnbefaodURURglfaVReckdcURfabVRmhidnUUaURdeefknbhaodcUR
fccncabdodcURjabVRdccfcgdccfccVRicaURdnVRdljURURejaocdccfcglccadVRddURci
VRcjURcecmcURcadVRdgaboURnbeccadVRnbgaVRdblinVReckdbcanbVRmcURmciddUUaUR
dVRihkhcecncabdVRdcURfURURhaVRdlfabnbVRdeckcfVRigkURdURcfccaURdVRdejhhej
aoURdcURURefaVRegkglURcadVRddURciVRchejaoliVRVRigmcidVRnbeUReURcadVRdcab
VRhURefaVRdhcjURgmefURmciddUUaURdVRicknbefaodcURjabnodlinboUReURnbcadVRd
gciVRcgncgcaURdVRddURURckURjURceURncabdVRccdcURfURURlURVRicaURdnVRdmc
w=cVRijaVRhcVRijaVRnbefaodURURglfaVReckdcURfabVRmhidnU
u=krVRsURtwF
v=uuuuuuuuaVRrVRsURtwUUG
p=FVw't'SVs'RRRUr'SUSVb'SFRbURVRrVSSSsURtwUG
q=GVw't'SVs'SUr'SUa'SFVVw't'SVs'SUr'SUa'FRrVRsUSSStwUaG
x=krVRsURtcVRijaVRhcVRijaVRnbefaodURURglfaVRnVRUpbURUpbURUpbockdcURfabVRVR
kaboURUpbURUpbURUpURdURURdnUFkrVRsURtVRUpaabVRVRijaVRhcVRicnaUpbdVRnbefa
odURURgnoURUpbURUpbURUpURVRcfaVReckVpaVRUpbURcURURcURUpbnbVRVRkabnbURUpb
URdURURdnUFaVRrVRsURtVRUpaabVRVRijaVRhcVRijaVRnbeURoUpaidodURURglfaVRenb
URUqbURVRknVRUpbURnabURVpURfabVRVRkURUpUpbUpUpcUpURUpUpURVRbUpbVRbURUpVR
UpbURoUpbUUUG
z=vvvvvvuuuuuux

原文链接：http://www.speedsolving.com/foru ... re-2x2x2-cube-group

[ 本帖最后由铯_猪哥恐鸣于 2011-12-27 10:47 编辑 ]

作者: 祭司zhangcy 时间: 2011-12-27 10:20:04

哇，真神奇。一个公式跑遍所有状态。

作者: 野猪哇 时间: 2011-12-27 10:23:35

说实话真的没有看懂.....

作者: 晴默 时间: 2011-12-27 10:23:37

哇，真神奇。没看懂………

作者: shoujiawei 时间: 2011-12-27 10:28:59

丢包了～～！！！！

作者: feifucong 时间: 2011-12-27 10:38:15

略看标题就知道肯定是铯发的帖子~~丢包！！

作者: Light 时间: 2011-12-27 10:50:59

我明白了……就是把这个公式背下来，你就可以不用观察就可以还原所有的二阶魔方了，哈哈

作者: 盲人摸象 时间: 2011-12-27 10:52:40

二阶超级公式啊，强大啊，厉害

作者: sulinlin 时间: 2011-12-27 10:58:00

只有佩服的份
怎么都发丢包，难道流行词汇这么快就改了

作者: 焚寂 时间: 2011-12-27 11:29:43

好虎的说，所有状态，，，话说2阶的所有状态并不多，哈。谁知道7阶的所有状态数，？

作者: 豆钉 时间: 2011-12-27 11:35:10

有两个块相连的情况下，二阶的情况有多少种

作者: 溯叔叔 时间: 2011-12-27 11:41:28

丢包了！！！铯丢包率略高啊~~~

作者: 橘子大王 时间: 2011-12-27 11:55:51

表示没太听懂哈。。。。。

作者: 乾申大那多 时间: 2011-12-27 12:30:24

楼主给力啊！！这么快就给出解释贴了。。。

作者: ttan660 时间: 2011-12-27 12:33:58

所有状态都出现了。。。。。。神奇啊``

作者: 一瓶香蕉水 时间: 2011-12-27 13:00:17

强大.................

作者: 42752277 时间: 2011-12-27 13:07:10

好神奇啊！
300多万步！

作者: Cielo 时间: 2011-12-27 16:38:48

哈哈看来我在另外那帖回复的时候没发现这个~

作者: pengw 时间: 2012-1-21 09:46:41

也就是说，不重复路径可以完成一颗树的搜索，妙啊，妙不可言

作者: 小明的马甲 时间: 2012-1-21 12:31:34 标题: 回复 19# 的帖子

内容状态们构成的不是树，而是一张稀疏图。。。

作者: pengw 时间: 2012-1-21 12:33:27

我上面也没有强调一定是树,你只要解决一楼那些问题,你就行了,能解决吗?如何解决?

事实上,状态之间可以用最短路径相连,并织组到一颗更容易理解的树上,要说是什么哈密尔顿图,你的依据是什么?

[ 本帖最后由 pengw 于 2012-1-21 12:35 编辑 ]

作者: 小明的马甲 时间: 2012-1-21 12:37:38

一楼那些问题？？？

作者: pengw 时间: 2012-1-21 18:26:44

1楼的180算一步还二步？有没有整体转？

作者: pengw 时间: 2012-1-21 18:33:06

一楼看不出来是在证明什么，铯_猪哥恐鸣能不能把一楼的证明过程译成中文写明白一点

作者: 小明的马甲 时间: 2012-1-21 18:35:17

一楼给出了递归定义的最终转动序列。。。证明哈密顿圈存在，只需要给出一个有效的解不，就足够了，无需多言。。。

作者: 小明的马甲 时间: 2012-1-21 18:37:27

解法中没有将180度转作为1步的情况，即所有转动都是90度转作为一步。。。

作者: pengw 时间: 2012-1-21 18:44:39

25楼，你运行出解了吗？你发布了这样一公式吗？有人验证过这样的公式吗？还是在一厢情愿

作者: 小明的马甲 时间: 2012-1-21 18:52:03 标题: 回复 27# 的帖子

据说包括我在内的好多魔友都验证了，它确实不重复的遍历了所有二阶状态。。。另外，这是别人找到的公式，但确实足以证明二阶哈密顿回路存在，这就足够了。。。

作者: pengw 时间: 2012-1-21 19:09:31

你能说出这之间的道理否？

作者: 小明的马甲 时间: 2012-1-21 19:11:50 标题: 回复 29# 的帖子

。。。道理？。。道。。理？！！！。。。你想知道啥？。。。什么是哈密顿圈？。。。

作者: pengw 时间: 2012-1-23 08:50:50

要求你说明的是算法原理，我相信你做事，应该是先弄懂道理才下手的

作者: 小明的马甲 时间: 2012-1-23 12:25:02 标题: 回复 31# 的帖子

我只负责转发，可以么？

作者: 骰迷 时间: 2012-1-24 14:00:08

算法原理不影響結論正確性

作者: pengw 时间: 2012-1-24 17:44:07

是的，我并不强求别人一定说得出道理，也无法证实你是不是真的验证过，总是一切都还是听你在说

作者: 骰迷 时间: 2012-1-25 11:24:03

为什么不自己写程序验证呢?

作者: ZZY7417 时间: 2013-1-16 22:45:42

这写法算是压缩吗…………

作者: い木子汐╰ 时间: 2013-2-25 18:47:56

哇塞！居然有这种超级公示

作者: m16 时间: 2013-5-23 21:28:42

厉害啊。。。。

作者: 樊榕钫 时间: 2013-6-18 19:32:02

高端洋气....没看懂.....

作者: 黑白子 时间: 2013-7-17 14:38:55

就是说，二阶的所有状态可以构成一个圆排列。

作者: 魔方幻 时间: 2013-7-17 14:59:46

说实话真的没有看懂.....但感觉好高级

作者: 黑白子 时间: 2013-7-17 16:21:12

魔方幻发表于 2013-7-17 14:59
说实话真的没有看懂.....但感觉好高级

楼主翻译的资料里说有一个很长的公式可以不重复的经过二阶的所有状态（这个数字是3674160）。既然如此，一定可以把二阶的所有状态按照顺时针或逆时针的次序排列在一个圆上。至于真的有没有这样一个公式，没有人去验证过，楼主也没有翻译这方面的资料。我的理解如果有误，还请楼主解释！

作者: 铯_猪哥恐鸣 时间: 2013-7-18 17:55:17

黑白子发表于 2013-7-17 16:21
楼主翻译的资料里说有一个很长的公式可以不重复的经过二阶的所有状态（这个数字是3674160）。既然如此，一 ...

1楼那个是构造性的证明。。某人还真构造出了这么个大圆环。。

作者: 展翅飞翔 时间: 2013-7-18 18:13:20

2阶超级公式？我收藏

作者: 黑白子 时间: 2013-7-19 11:14:15

铯_猪哥恐鸣发表于 2013-7-18 17:55
1楼那个是构造性的证明。。某人还真构造出了这么个大圆环。。

能否把1楼的那个构造性证明译成中文？

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