魔方吧·中文魔方俱乐部

标题: 魔金齿的状态穷举和玩法分析 [打印本页]

作者: 折翼蚂蝗 时间: 2017-10-22 21:12:20 标题: 魔金齿的状态穷举和玩法分析

本帖最后由折翼蚂蝗于 2017-10-27 16:11 编辑

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

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

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

附件: 6.jpg (2017-10-27 16:09:39, 104.67 KB) / 下载次数 236
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjYzMzc2fDAwZGE0N2I3fDE3NDQxMzg0MTB8MHww

附件: 5.jpg (2017-10-22 21:07:10, 129.25 KB) / 下载次数 214
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjYzMzY3fDU1Yjg5ZWRkfDE3NDQxMzg0MTB8MHww

附件: 4.jpg (2017-10-22 21:07:09, 77.45 KB) / 下载次数 221
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjYzMzY2fDZhZDg5NjEwfDE3NDQxMzg0MTB8MHww

附件: 3.jpg (2017-10-22 21:07:07, 23.93 KB) / 下载次数 216
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjYzMzY1fGVhMDI2ZDM2fDE3NDQxMzg0MTB8MHww

附件: 2.jpg (2017-10-22 21:07:07, 29.79 KB) / 下载次数 206
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjYzMzY0fDk3NjEyMmRkfDE3NDQxMzg0MTB8MHww

附件: 1.png (2017-10-22 21:07:06, 142.34 KB) / 下载次数 202
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjYzMzYzfDJlNzE1NGY5fDE3NDQxMzg0MTB8MHww

作者: xiaoli 时间: 2017-10-22 21:53:47

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

作者: otischeng 时间: 2017-10-22 22:01:56

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

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

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

作者: 折翼蚂蝗 时间: 2017-10-22 22:28:22

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

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

作者: 折翼蚂蝗 时间: 2017-10-22 22:30:47

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

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

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

期待您参加马丁加德纳聚会的帖子

作者: redcarrot 时间: 2017-10-22 23:48:01

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

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

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

作者: redcarrot 时间: 2017-10-23 00:08:26

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

作者: 折翼蚂蝗 时间: 2017-10-23 00:26:52

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

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

作者: 折翼蚂蝗 时间: 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？似乎都不行。我也没有正经学过图论，猜测没有哈密顿回路。哈密顿通路也没有。

附件: 无哈密顿回路.jpg (2017-10-24 21:38:31, 25.43 KB) / 下载次数 186
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjYzMzcyfDEyYzc4N2IzfDE3NDQxMzg0MTB8MHww

附件: 改良穷举图.jpg (2017-10-24 21:38:30, 120.1 KB) / 下载次数 198
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjYzMzcxfGZmZGQ4YTZjfDE3NDQxMzg0MTB8MHww

作者: redcarrot 时间: 2017-10-23 09:29:26

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

谢谢推荐！

作者: luckybox 时间: 2017-10-23 14:12:46

蚂蝗厉害了。完全看不懂，上大学就对高数头疼不明觉厉

作者: 管窥子 时间: 2017-10-23 21:18:34

厉害！

作者: 林海gz 时间: 2017-10-23 22:58:56

厉害，WORD 哥

作者: ian_wood 时间: 2017-10-24 18:33:49

迷宫类的魔金相对简单一些，可玩性还是很强的
不过个人还是更喜欢暗盒类的，比如连锭互永转这些，可能和我数学不好有关系吧

作者: 折翼蚂蝗 时间: 2017-10-25 10:52:37

luckybox 发表于 2017-10-23 14:12
蚂蝗厉害了。完全看不懂，上大学就对高数头疼不明觉厉

完全不懂，大概是我写的不够通俗。。其实普通玩玩是不用数学的，我总结的懒人玩法还是挺简单的~

作者: 折翼蚂蝗 时间: 2017-10-25 10:56:19

ian_wood 发表于 2017-10-24 18:33
迷宫类的魔金相对简单一些，可玩性还是很强的
不过个人还是更喜欢暗盒类的，比如连锭互永转这些，可能和我 ...

暗盒类，需要猜测、试探结构上各种可能的机关布置，解开后恍然大悟，但是重复可玩性偏低。迷宫这方面好一点，总结出穷举图，就能以上帝视角看它

作者: redcarrot 时间: 2017-10-26 15:58:04

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

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

无标题.jpg

附件: 无标题.jpg (2017-10-26 15:47:54, 137.11 KB) / 下载次数 131
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjYzMzc1fDE4MWMyNzhhfDE3NDQxMzg0MTB8MHww

作者: sfkgi漷 时间: 2017-10-26 17:56:37

强，支持支持

作者: 折翼蚂蝗 时间: 2017-10-26 19:03:01

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

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

作者: redcarrot 时间: 2017-10-27 09:33:49

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

好的，我去买来看看

作者: 潮州小魔王 时间: 2017-10-30 13:57:06

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

作者: 折翼蚂蝗 时间: 2017-10-30 18:31:41

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

用几何画板，笨办法画的

作者: 易智强5 时间: 2017-11-5 10:44:02

有点晕。。。

作者: 魔道窈女 时间: 2017-11-10 12:15:24

完全看不懂厉害了

作者: 聚元号 时间: 2018-6-22 17:52:45

好厉害的图论

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