关于转动式拼图的通用解法

humphry.l

; E3 ^7 ~8 \& q- F

对于AVG里滑动式拼图大家一定不陌生，对各种 3×2 单元做一把循环，很容易就完成，对这类解法不熟悉的可以看这里：http://xy2.netease.com/viewthread.php?tid=1690301（以前论坛上有一偏文章也专门讲述了滑动式拼图的解法，可惜我找不到。另外有哪位坛友能帮助改善下表格混排，论坛的排版似乎不支持表格与文字共用一行）

不过对于转动式的拼图谜题暂时还没有被大家讨论到，它的一般模式是这样的，比如 3×3 形式：

1	4	9
6	7	8
2	3	5

或者是这样 2×4 形式：

1	2	5	8
7	6	4	3

对于 3×3 形式的，谜题要求转换成（记这个形式叫做标准型 M0）：

1	2	3
4	5	6
7	8	9

对于 2×4 形式的：谜题要求转换成（记这个形式叫做标准型 N0）：

1	2	3	4
5	6	7	8

不同于带空格的滑动式拼图，转动式没有空格，而是在每个 2×2 方格的中间放置了一个小转盘，点击一下就会使得该 2×2 区域产生顺时针或者逆时针转动。我最早遇到的类似谜题还是 2006 年发行的 Safecracker，也就是《破箱人》，里面有一个转动式拼图最终是要拼出美元符号 “$”。这个题看起来很吓人，不过由于里面恰好有两块完全一样而且是紧贴着的空白方块，所以一般玩家很容易过关，当时我也没有注意到正是这个因素导致这个谜题的难度大大下降。不过在后续的其他游戏里我遇到的谜题总是非常讨厌，一般拼到最后总是某两个数字的顺序恰恰相反，除了暴力式无脑转动就是直接看攻略了事。

昨天晚上思考了下，把这类谜题的通用解法记录在帖子里以供大家参考。我们先来观察几个基本情况：

• 对于 N×N (N>2) 形式的正方形拼图来说，最终都可以化解成 3×3 形式。理由很简单，你总是可以通过很容易的操作把最外围的边都按照要求拼好，然后只剩下一个内层的 3×3，就像这样：
  

N	…	…	…	…
…	…	…	…	…
…	…	1	4	7
…	…	2	5	8
…	…	3	6	9

• 而其内层的 3×3 在变换为标准型 M0 之前也总是很容易被转换成这样，差别在于 8 和 9 的位置颠倒，把这个记成 M1：
  , A. C! L- \# l* H; q1 f

1	2	3
4	5	6
7	9	8

• 同样地，对于 2×N (N>3) 形式的长方形拼图来说，最终都可以化解成 2×4 形式。理由很简单，你总是可以通过很容易的操作把最外围的边都按照要求拼好，然后只剩下一个内层的 2×4，就像这样：
  7 }7 i, U7 @5 v9 r" O

N	…	1	3	5	7
…	…	2	4	6	8

• 而其内层的 2×4 在变换为标准型 N0 之前也总是很容易被转换成这样，差别在于 4 和 8 的位置颠倒，把这个记成 N1：
  

1	2	3	8
5	6	7	4

• 再考虑转动方向的问题。以顺时针方向为例，对于某个固定转盘的连续不间断操作都不应该超过三次，因为到了第四次相当于不转，而顺时针转动的次数 T 相当于用 4 - T 次逆时针转动的次数。这样我们就建立起了转动方向之间的内在联系，为简化模型，我们可以假设每个转盘都是顺时针方向的。
  

所以问题也就转换成了较简单的 M1 -> M0 以及 N1 -> N0，而且每次都是顺时针方向操作。进一步观察可知，M 和 N 的结构也是非常类似，如果我们固定住 M1 中的 “7”（即不操作左下的转盘），那么剩余的方块也是 8 块，转盘数是三个，和 N1 -> N0 的操作类似。具体的思路见下一楼。

myq495

支持一下，这是我的弱项。

humphry.l

0 s+ {; E: L5 h3 @

根据上面的结论，我们先来研究 N1 -> N0 的操作（我们对于 N1 -> N0 的目的就是交换 4 和 8）。为方便起见，我们把转盘从左往右，依次记为 L、M、R。我们希望能够找到某种LMR的排列构成的操作，这样的操作不要复杂，而且只改变某些元素的位置（必须包含拟交换的元素），被改变位置的元素有一定规律性，针对这样的规律找到公倍数，于是只要重复几次，就可以完成 N1 -> N0 的变换。经过观察我们找到了这样一个操作 Op：

R, M, R, R, L, L, L, R, M, R, L。这个操作使得 N1 变成了下面这样 N2：

1	6	3	4
2	5	7	8

可以观察下 N2 和 N1 相比有什么不同：首先，这个操作过程中位置没有变化的是1、3、7，变化的有 4 和 8 交换位置以及由 2、6、5 构成的小三角形完成了一次逆时针转动。事实上只要再完成两次 Op 操作就可以将 N2 变化成 N0（这是因为对于 4 和 8 互换需要 2K+1 次 Op 操作，而对于小三角形转回成原样需要 3L 次 Op 操作，所以取一个最小公倍数 3）。具体每次操作后的表格状态我就不画了，有兴趣的坛友可以自己写个小程序验证下（至于我是怎么找到操作 Op 的，其实也是拿计算机先暴力猜了一遍再提取出规律的，我猜可能和群论有关，和魔方类似，可惜我的数学早就还给老师了，如果坛友里有研究数学的不妨从理论上研究下）。

至于 M1 -> M0，把左上、右上、右下分别记为 L、M、R 的话，也有类似的循环操作 Op，重复次数也是 3 次（大家可以自行验证下）：

R, L, R, R, L, L, R, M, M, R, L, M, L, L, L, M, L

这篇文章也是抛砖引玉，希望大家集思广益，看看还能不能找找更简便或者说长度更短的循环操作。

ice7summer

学习一下，这种类型的都是跳过

恶魔出没

好厉害呀！！！！经常会遇到这种拼到最后两个位置颠倒的情况！！！都没有这么深入地考虑过……虽然还是看不太懂…………

humphry.l

恶魔出没 发表于 2015-10-19 09:06
好厉害呀！！！！经常会遇到这种拼到最后两个位置颠倒的情况！！！都没有这么深入地考虑过……虽然还是看不 ...

哪里写得不太明白，我好改进下