魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
查看: 944|回复: 23

魔金齿的状态穷举和玩法分析 [复制链接]

Rank: 3Rank: 3

积分
940
帖子
832
精华
3
UID
1321618

收藏爱好者 四年元老

发表于 2017-10-22 21:12:20 |显示全部楼层
本帖最后由 折翼蚂蝗 于 2017-10-27 16:11 编辑

友情提示,本帖讨论 魔金齿 的解法,有剧透,喜欢独立破解的玩家请慎入。欲知解法,请看文末。

最近重温了魔金:O’GEAR齿。这是一款轨道迷宫类型的魔金。自从我刚接触魔金,到收齐全套为止,一直热衷于用巧妙形状卡扣而成的机关类型的魔金,比如Ring环、Dolce美、Donuts连等。现在各种魔金我都玩过了,大部分也会解,觉得迷宫类的探究价值更大,因为路径复杂、变换多、难以穷尽(魔方也有这个特点,所以百玩不厌)。这次重温 魔金齿 ,最初目的就是穷举它的所有状态,以下做一简单介绍。
1.png


魔金齿,有两部分组成。一个正方体的箱体,每面有横竖两个槽,以及一个有向连接的弧形滑道。一个五角形齿轮,其中一个齿上有缺口。初始状态下,齿轮以特定姿势卡在箱体的特定位置上,齿轮可以翻越箱体的棱而转动,目的是利用有缺口的齿,把齿轮从箱体中取出。
五个齿、六个面,每个面上有两种方向,所以这款迷宫类魔金的状态数共有5*6*2=60个。
为了标记各种状态,首先要给箱体和齿轮的编号,如下图。
2.jpg


五个齿轮的编号为0、1、2、3、4。从0开始,是因为分析路径时用到了一点模算数方法,这样标记会带来方便,容后文详述。并且,记4+1=0(这实际上是模5的加法),换言之,0号齿的后继是1号齿,1号齿的后继是2号齿,……,4号齿的后继是0号齿。这体现一种周期性。在箱体上,UR、FL、FD、BD四条棱的形状和其它八条不同,齿轮不能在这四条棱上翻越。为了标明齿轮卡在某一面时的方向,还需要做出如下约定:UF、UB、UR、UL、FR、FL六条棱称为“第1类棱”,其它六条称为“第2类棱”。齿轮卡在箱体中时,将其转到倾斜45度的姿势,如果HANAYAMA标志指向第1类棱,则称此时为第一类方向。否则称为第二类方向。

例一:初始状态,0号齿卡在U面,齿轮倾斜45度时,HANAYAMA标志指向FR棱,是第1类的,所以这种状态记为0U1。分离位,4号齿卡在D面,齿轮倾斜45度时,HANAYAMA标志指向FL棱,是第1类的,所以这种状态记为4D1。

以上的记法稍有繁琐,但这也是标记方向的最简单的方法。
完成记法的约定后,便可以开始寻找路径。首先注意到,无论从何种状态开始,操作一次后,“进入箱体的齿”和“操作之前在箱体中的齿”一定是相邻的。

例二:初始状态为0U1,操作一次后可能的状态有三种:1B1,4L2,4F2。和0号齿相邻的正是1号、4号齿。

所以,在正式穷举之前,不妨先整理一张基本变换图,即不考虑齿轮的实际编号,只考虑操作中齿轮编号的增减。如下图。
3.jpg


稍作解释。基本变换图中,共有12个节点,即箱体的六个面,以及各自的两类方向。箭头方向表示齿轮编号增加的方向。

例三:图中的U1可以顺箭头到达B1,也可以逆箭头到达L2、F2,这表明,任何一个齿,只要处在U1位置,若向B面移动,则齿轮编号加1;若向L、F面移动,则齿轮编号减1。
例二的情况是例三的特例。

至此,看着基本变换图,就可以解开 魔金齿 。因为分离位是4D1,为了解开 魔金齿 ,只需先把任何一个齿转到D面,检查是否为D1方向。如果不是,则操作R、B、L、D,即可变成D1状态。然后检查是否为4D1,如果不是,利用基本变换图可见,只需操作L、B、U、F、R、D。这个操作会保持D1方向,并且使卡在D面的齿轮的编号加2。由于齿轮共有5个,5是素数,所以不断重复这个操作,一定可以出现4D1的状态,从而解开。



插入介绍一点数学内容,不感兴趣的读者可以跳过此段。以上提到的“不断重复这个操作,一定可以……”,实际上是基于一个模算数的简单定理。模算数,别名为钟表上的算数。比如,9点钟加5小时等于2点钟,这就是模12加法,记为9+5=2(mod 12)。模数是素数的加法具有重要意义。比如,一个奇怪的钟表上共有11个小时,则从11时开始,每次向前数2小时,数11次,一定可以遍历所有11个刻度。把每次向前数的2换成3,4,…,10都可以。这可以用如下的定理来解释:
4.jpg

正常的钟表上,共有12个刻度,12不是素数,所以不具有这种性质。比如,从12时开始,每次向前数3小时,则历经的刻度为:3,6,9,12,并不能遍历所有刻度。在 魔金齿 中,齿轮数共有5个,是素数,所以当转到D1状态时,只需在基本变换图中,取一个包含D1的环路,只要沿着这个环路的编号增量不为0,那么反复走这条环路,最多走四圈,一定可以到达分离位4D1。
魔金五 上也有相似的机制。可见设计师还是手下留情了的,如果把齿轮数变成6,不是素数,那么这种方法就行不通了。



有了基本变换图,只需填上齿轮编号、合理安排次序,就可以得到60种状态的穷举图:(后记:简化的穷举图见9楼)
5.jpg


60个节点,想把穷举图摆的简明扼要,很难。我试验了很多方法,这个比较清晰。看着穷举图,就可以在任意两个状态之间自由转换。说实话,画完穷举图后,我有种失落感,因为并没有实现预想的清晰明了。60个节点,纷繁复杂的连线,恐怕也没有更清晰的图示了。其实,如果节点过多,就不适合穷举了。这是因为,依靠穷举图解魔金时,要满足两点才能带来方便,一是节点容易找到(比如归类放置节点),二是路径简明、少交叉。当节点过多时,这两点不能兼顾,所以穷举就失去了意义。没有人穷举魔方,大概也是这个原因。
为此,我又做了 魔金齿 的最短路径图,如下图:
6.jpg


注意,这张图并不包含所有路径,只是画出了从任何一种状态到分离位4D1的最短路径。当然,路径最短的走法也不是唯一的。从图中可见,从初始状态0U1解开至少需要10步。从最短路的意义上说,初始状态并不是最深状态。



现在总结,魔金齿 的三种玩法。

懒人玩法:公式一:R、B、L、D。公式二:L、B、U、F、R、D。
先把任何一个齿转到D面,检查是否为D1方向。如果不是,则操作公式一,即可变成D1状态。然后检查是否为4D1,如果不是,只需反复操作公式二,最多操作四次,必会出现4D1的状态,从而解开。

普通玩法:看穷举网状图,移动到分离位4D1。

高手玩法:看最短路径树状图,移动到分离位4D1。



以上就是我对 魔金齿 的分析,谢谢观看。

已有 3 人评分经验 收起 理由
cube_master + 20 厉害了!
kexin_xiao + 20 赞一个!
otischeng + 20 很给力!

总评分: 经验 + 60   查看全部评分

Rank: 2

积分
216
帖子
579
精华
0
UID
1247069
性别
保密

六年元老

发表于 2017-10-22 21:53:47 |显示全部楼层
请收下我的膝盖吧 大师 一头雾水的拜读着。。。发觉我白玩了这款魔金 或说我根本就真正玩过

使用道具 举报

Rank: 7Rank: 7Rank: 7

积分
9372
帖子
2873
精华
15
UID
101905
性别
兴趣爱好
收藏

收藏爱好者 八年元老

发表于 2017-10-22 22:01:56 |显示全部楼层
首先, 列成表這一點很厲害. 值得一讚!

公式還算能看懂, 但還是稍為複雜了一些. 如果不是特別感興趣的看客, 多半會為之郤步. 如果能更簡明一點就更好了.

身為數學盲, 理論方面就不評論了.

使用道具 举报

Rank: 3Rank: 3

积分
940
帖子
832
精华
3
UID
1321618

收藏爱好者 四年元老

发表于 2017-10-22 22:28:22 |显示全部楼层
xiaoli 发表于 2017-10-22 21:53
请收下我的膝盖吧 大师 一头雾水的拜读着。。。发觉我白玩了这款魔金 或说我根本就真正玩过

过奖了。。模算数那里用到一点数学,还有就是对齿轮方向的定义有点复杂。搞清这两点,穷举什么的只是反复试试,没有很高的技术性。

使用道具 举报

Rank: 3Rank: 3

积分
940
帖子
832
精华
3
UID
1321618

收藏爱好者 四年元老

发表于 2017-10-22 22:30:47 |显示全部楼层
otischeng 发表于 2017-10-22 22:01
首先, 列成表這一點很厲害. 值得一讚!

公式還算能看懂, 但還是稍為複雜了一些. 如果不是特別感興趣的看客 ...

谢O仔表扬!一般玩家只要注意一下我对齿轮方向的定义就行了,别的都很简单。数学的部分是个人有感而发,也是为了窥见设计意图的一斑。最后总结的 懒人玩法还是挺容易看懂的
期待您参加马丁加德纳聚会的帖子

使用道具 举报

Rank: 4

积分
1059
帖子
1546
精华
2
UID
1244890
性别
居住地
杭州市
WCA ID
2014XULI01
兴趣爱好
破解
DIY

六年元老

发表于 2017-10-22 23:48:01 |显示全部楼层
分析的很漂亮!
一开始看到那个网状图的时候还以为是正则的(每个点的度相等,是叫这个吧,没怎么学过图论),以为有可能是有群结构,后来发现有的点度是2有的点度是3……不过可以通过去掉一些边(形如1L2-2R1,3B1-4R1的边)或者添上一些边变成正则的,不知道是不是可以在Puzzle本身上找到解释?

你数过这个网状图的最短回路不?以及这个图应该有Hamilton回路吧?

一直没敢入魔金坑,这个看起来好像很有意思,光看分析还是不能完全看懂,有点想入一个玩玩。

使用道具 举报

Rank: 4

积分
1059
帖子
1546
精华
2
UID
1244890
性别
居住地
杭州市
WCA ID
2014XULI01
兴趣爱好
破解
DIY

六年元老

发表于 2017-10-23 00:08:26 |显示全部楼层
求推荐几个入门的魔金……或者是不是有前辈写过心得?

使用道具 举报

Rank: 3Rank: 3

积分
940
帖子
832
精华
3
UID
1321618

收藏爱好者 四年元老

发表于 2017-10-23 00:26:52 来自手机 |显示全部楼层
redcarrot 发表于 2017-10-23 00:08
求推荐几个入门的魔金……或者是不是有前辈写过心得?

推荐魔金,主要考虑这三个方面:难度适中,外观美观,经得起折腾。推荐这几款:环美乐辰锁对星蟹球,这些是机关巧妙,破解后恍然大悟型的。还有齿宙迷继磁箱,这些时迷宫型的,研究价值高。有的魔金有人写过心得与分析,比较少。
感兴趣可以加群38655250,群里有魔金、环扣的各路大师。

使用道具 举报

Rank: 3Rank: 3

积分
940
帖子
832
精华
3
UID
1321618

收藏爱好者 四年元老

发表于 2017-10-23 00:28:18 来自手机 |显示全部楼层
本帖最后由 折翼蚂蝗 于 2017-10-24 21:39 编辑

占一楼,用于发布 穷举网状图 的修改版,以及回答6楼的问题。
-------------------------------------------------不知道怎么艾特6楼。

更新,正文中的穷举图还可以进一步化简,这是QQ好友昆西的发现。把原图划分为五个部分,重新排列,可以消去原有的10条长线,得到同构且更简单的形式:
改良穷举图.jpg

对照最短路径树状图,找到三个离分离位最远的节点,从穷举图上看,确实很远。


现在回答六楼的问题。有的节点度数是2,有的是3,这是这款魔金本身形状决定的。如正文中所说,在箱体上,UR、FL、FD、BD四条棱的形状和其它八条不同,它们是“尖棱”,齿轮不能从这些棱上翻越(如果手上有实物,很容易发现)。可见,当齿轮处在F面时,只能向R、U面移动;当齿轮处在D面时,只能向R、L面移动。所以,穷举图中关于F、D的节点的度数都是2。如果把FD棱改成非“尖棱”,即在F、D面之间建立通路,则变成每点度数为3的正则图(具体的说,F1到D1齿轮编号加1,F2到D2齿轮编号减1)。
“去掉一些边,变成正则的”这是办不到的。这等价于把一些非尖棱变成尖棱,使每一面上有两条尖棱。观察魔金实物,可见这是不可能的。其实这也好理解:如果穷举图中每个点度数都是2,那么穷举图要么是单链式,要么是单环式,没有支路,相应的魔金解法过于简单。

最短回路应该有5个节点,从改良穷举图中容易看出。

关于哈密顿回路,常见的判定定理我都试过了,无法判断存在或不存在。通过观察几何图形,我认为是不存在的,如下图,这是改良穷举图的上5分之1。
无哈密顿回路.jpg

注意节点0D1和0F1,它们的度数是2,又它们各有一条边通向4R1,所以红色部分必须在哈密顿回路中。同理,绿色部分也在。考虑4U2的后继点是谁?3B2还是0L1?似乎都不行。我也没有正经学过图论,猜测没有哈密顿回路。哈密顿通路也没有。

使用道具 举报

Rank: 4

积分
1059
帖子
1546
精华
2
UID
1244890
性别
居住地
杭州市
WCA ID
2014XULI01
兴趣爱好
破解
DIY

六年元老

发表于 2017-10-23 09:29:26 |显示全部楼层
折翼蚂蝗 发表于 2017-10-23 00:26
推荐魔金,主要考虑这三个方面:难度适中,外观美观,经得起折腾。推荐这几款:环美乐辰锁对星蟹球,这些是 ...

谢谢推荐!

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

上海香港网

Archiver|手机版|魔方吧·中文魔方俱乐部

GMT+8, 2017-11-25 00:32

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部