魔金齿的状态穷举和玩法分析

折翼蚂蝗

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

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


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


五个齿轮的编号为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号齿。

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


稍作解释。基本变换图中，共有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都可以。这可以用如下的定理来解释：

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



有了基本变换图，只需填上齿轮编号、合理安排次序，就可以得到60种状态的穷举图：（后记：简化的穷举图见9楼）


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


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



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

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

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

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



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

聚元号

好厉害的图论

魔道窈女

完全看不懂 厉害了

易智强5

有点晕。。。

折翼蚂蝗

潮州小魔王 发表于 2017-10-30 13:57
厉害了，这图是怎么画出来的

用几何画板，笨办法画的

潮州小魔王

厉害了，这图是怎么画出来的

redcarrot

折翼蚂蝗 发表于 2017-10-26 19:03
是的。2度节点的边不能去掉，所以B1—R1连线、B2—R2连线必须去掉，也就是你画的短蓝线。剩下的3度节点有 ...

好的，我去买来看看

折翼蚂蝗

redcarrot 发表于 2017-10-26 15:58
确实没有哈密顿回路
之前忘记了连通的2-正则图就是一个环路这么简单的判定。。。假设哈密顿回路存在，我 ...

是的。2度节点的边不能去掉，所以B1—R1连线、B2—R2连线必须去掉，也就是你画的短蓝线。剩下的3度节点有L1，L2，U1，U2四种，怎么“去边”都不行。所以不存在哈密顿回路。
这款魔金很有意思，不妨买来试试，同为数学人的你一定会有新发现

sfkgi漷

强，支持支持

redcarrot

折翼蚂蝗 发表于 2017-10-23 00:28
占一楼，用于发布 穷举网状图 的修改版，以及回答6楼的问题。
----------------------------------------- ...

确实没有哈密顿回路
之前忘记了连通的2-正则图就是一个环路这么简单的判定。。。假设哈密顿回路存在，我们只要去掉一些度为3的点之间的连接就可以了。
容易看出，这个图里度为3的点是8个一组，分布在五个区域里的，所以“不走的边”只有红蓝两种选择。去掉蓝边会变成2个连通分支，去掉红边会变成5个连通分支，故哈密顿回路不存在。