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

折翼蚂蝗

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

最近重温了魔金：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。



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

xiaoli

请收下我的膝盖吧 大师 一头雾水的拜读着。。。发觉我白玩了这款魔金 或说我根本就真正玩过

otischeng

首先, 列成表這一點很厲害. 值得一讚!

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

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

折翼蚂蝗

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

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

折翼蚂蝗

otischeng 发表于 2017-10-22 22:01
首先, 列成表這一點很厲害. 值得一讚!

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

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

redcarrot

分析的很漂亮！
一开始看到那个网状图的时候还以为是正则的（每个点的度相等，是叫这个吧，没怎么学过图论），以为有可能是有群结构，后来发现有的点度是2有的点度是3……不过可以通过去掉一些边（形如1L2-2R1，3B1-4R1的边）或者添上一些边变成正则的，不知道是不是可以在Puzzle本身上找到解释？

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

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

redcarrot

求推荐几个入门的魔金……或者是不是有前辈写过心得？

折翼蚂蝗

redcarrot 发表于 2017-10-23 00:08
求推荐几个入门的魔金……或者是不是有前辈写过心得？

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

折翼蚂蝗

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

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

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


现在回答六楼的问题。有的节点度数是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。

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

redcarrot

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

谢谢推荐！