AVG迷题探索（01）

tabris · 发表于 2007-8-16 22:22

关于本系列贴主题的说明。
8 z# q2 m) X" X& k* @! U; s C 写这个系列的帖子主旨在于深入探讨AVG中某些具有代表性的迷题，讨论研究其中的解题思路以及普遍方法，虽然内容当中肯定会引用特定的迷题做例子并详细解说，但实际上介绍的解题方法却并没有特别针对某一个游戏的某一个迷题而言，算是攻略好像也不太合适。思前想后决定放在“原创评论”这边，姑且算是一种“对某些类型迷题”的评论吧，希望没有违背本版的宗旨。

      与攻略还有论坛的解答帖子不同，我们在这里要深入探讨一种迷题的“一般解法”，请注意：“一般解法”是一种能让你成功破解任何一个这类迷题的办法，但却不一定是最快捷办法（这是一把万能钥匙，但需要耐心，呵呵～只求通关的朋友请飘过吧！）。

      在论坛的破箱人迷题统计中，这个是令大家最头疼的迷题了，就让我们从这个最大难题开始我们的解迷之旅吧～

两个基本变换
      毛主席说“克思主义的道理千头万绪，归根结底就是一句话‘造反有理’！”，所以既然要找出一般解法，则必须通过归纳，把这个千变万化的拼图迷题简化一下。这个拼图迷题的变化确实很简单，只有一种（下图）：

      就是四个方块围绕中间点做顺时针转动（臭鸡蛋纷飞……），先别急，确实，这个变化太简化了，于我们的解题毫无帮助，不过先让我们为这种变换起个名字——“旋转”，然后我们再看看下面这个由几个“旋转”组成的“互换”吧（下图）：

在这个“互换”中涉及最少8个单元格，假设开始的排列如1所示，图中三个点击旋转的按钮姑且就叫做“上、中、下”吧，则步骤如下：
（1－2）：上×1
（2－3）：下×3
（3－4）：中×2
（4－5）：上×3
（5－6）：下×1
      是不是很有规律呢？按钮的顺序为“上下中上下”，点击（转动）的次数为“13231”，看看结果，对比1和6，我们在左列排列不变的基础上，把右列的上下部分互换了。
同样道理，我们也可以使右列保持不变，让左列的上下部分互换，唯一不同的是按钮顺序变为“下上中下上”而已，点击（转动）次数依然为“13231”。
如果我们再把上图旋转90度，那么上下互换的操作同样也就适用于左右互换了，这个“互换”的操作不难吧？确定你要实行互换的行或列，根据下表找到第一个按钮，然后“13231”，搞定！]

需要实现互换的列（行）的位置对应第一个操作按钮的位置
      左                                                             下
      右                                                             上
      上                                                             左
      下                                                             右

好了，基础练习到此结束，下面是正题了。

任意变化
      我们现在掌握了“互换”的秘密，有什么用呢？很重要，事实上，这类拼图迷题的全部变化，都是通过有限次的“互换”再加上1~2次“旋转”实现的。为什么这样说？还是以8个格子为例：

      假设我们现在想重新设置e的位置，能否通过有限次的互换加1~2次旋转实现e的任意移动呢？答案是肯定的。
*  通过一次旋转，e能够到达现在c的位置，这绝对正确；
*  通过一次互换，e能够到达现在a的位置，这一点也毫无疑问；
*  好了，如果e能到达c的位置，它再进行一次互换，就能够到达g；
   （至此，左列全部位置均能到达）
*  e能到达a位置，再进行一次旋转，则能到达b；
*  e在原位进行一次旋转，则到达f；
   （现在剩下d、h位置了）
*  e旋转两次可以到达d位置；
*  e在d位置上再加一次向下的互换，就轻松到达h。
   通过以上步骤，我们让e遍历了全部位置，数一下，所有的过程都不超过有限次的互换和1~2次旋转，而且完全能在8个格子的范围以内实现。一幅任意大小（当然格子数要大于8）的矩形拼图都可以看作是好几个8格子单元的组合。
   因此，理论上，通过有限次的互换和1~2次旋转可以任意变化拼图的排列。这里的“任意”，是指不考虑其他格子的情况，任意安排目标格子的位置。如果考虑其它格子的排列，在有限个格子的范围之内，全部格子的排列则不可能是任意的，例如：

   在这样的8个格子的限制之内，如果规定左列的顺序aceg不变，则右列的顺序只能为bdfh或fhbd，不可能有bfdh等其他的情况出现，姑且把这一条称之为“定理一”。
      不过我们其实不必为这种格子与格子之间排列方式的内在联系操心，因为我们可以这样考虑：现在的这个混乱的拼图其实是游戏制作者在整齐拼图的基础上通过和我们一样的规则变化出来的，因此，一切一切格与格之间内在的联系已经内含在拼图里了，无论拼图如何混乱，这种内在联系不会改变。所以我们只需专注于某一个格子的正确位置，其余的格子自然会按照这种内含关系发生改变。

tabris · 发表于 2007-8-16 22:32

实战
      OK，现在用破箱人的最难迷题来检验和演示一下我们的“万能钥匙”。

      1、拼图的初始状态如上，我们的顺序是从左上角开始，于是第一目标就是把红色方块移到左上角第一格；

      2、先来一次“旋转”，红色方块位置如上，然后在黄色方框范围来一次“互换”，结果

      3、红色方块和它右边的方块一起被移到如上位置。（我们移动目标方块时，必定有一块不相干的方块和它一起移动，这点不必理会，记住，我们唯一的目标就是红色的目标方块！）然后和上一步一样：黄色方框里做“互换”，

      4、还是黄色方框里做“互换”，

      5、第一步大功告成！锁定下一个红色方块，现在要把它移到绿色方块下方了（很显然，只需一次“旋转”两次“互换”就足以达成目的）。很简单的重复步骤，这里不细说，就这样从上往下，从左到右一直排下来（注意，请不要排最下方的一行），结果如下：

      6、如果在排列中途遇到好像上面这种“目标格子”被挤在角落出不来的情况，也很容易解决，来一次“互换”把它换到右边的自由空间就可以了。最终我们能够得到以下结果：

      7、在右边只剩两列，下边只剩一行的基础上，我们再来对付最下面一列（在其他此类拼图也一样，无论是5×5还是8×8还是其他面积的）。操作也很简单，把需要塞进正确位置的方块挪到右边两列的最底层，然后通过互换把它塞往左边即可！这里要注意一点：互换时，目标方块的移动其实是跳跃前进一个格子的，所以我们要选好目标方块进行互换的初始位置。如上图，目标方块的目标位置是左下角，往右跳回两次，所以互换初始位置应该在右下角。于是

      8、一次“互换”后

      9、两次“互换”后，成功！在最后一行只剩2列没有完成的时候，我们需要改变一下策略了。如上图，假设现在再往左边（坐标5，2处）塞一个方块，那剩下的那个方块就没法塞进去了（因为剩下的方块要互换到坐标5，3处，必然会带着一个不相关的方块进入坐标5，2），因此最后这一步必须两个目标方块联动才行。

      10、其中一个目标方块已经准备到位，剩下的一个通过一次竖向的“互换”前往初始位置。

      11、准备就绪，发射！！

      12、剩下右边两列了，我们可以任意选择从上往下排还是从下往上排，假设我们选的后者，操作也没什么难度，完全和刚才准备那两块初始位置的步骤相同，先就绪一个，另一个通过互换到达。

      13、现在剩下没有拼好的只有8个方块了，其他方块不需要做任何变动，只要在这8个方块内部作调整就可以完成拼图。怎样调整呢？记得上面提到的“定律一”吗？按照该定律，只要把左边4个方块排好，右边4个方块就只存在两种可能，一种可能就是正确顺序，那么我们就解开迷题；另一种可能是上下位置相反了，那我们做一次互换也同样能够解开迷题。所以我们把精力集中在左边一列就可以大功告成。具体步骤我们等一下再讨论，现在停下来看看一个问题。

tabris · 发表于 2007-8-16 22:42

一个佯谬
      上面13步说的很轻松：只要×××一切就妥当了。这个×××即“排好左边列的顺序”确实是小事一桩，但问题是：真的就一切妥当了吗？呵呵，不一定，请看下图：

      这幅图是不是接上一章第13步，而是在上一章12步时选择从上往下排时所遇到的，我们发现在最后的8个格子范围内，无论依靠旋转还是互换，都没办法把蓝色方块排好。
为什么会这样呢？看看我们总结出来的两种基本变换，无论是旋转还是互换，每一种基本变换最终必然会涉及4个方块位置的改变，因此好像上图这种“需要改变两个方块位置”的情况，基本变换是毫无办法的！
      等等，但迷题作者也是通过基本变换生产出迷题的呀，那这种基本变换无法产生的情况作者是怎样调出来的呢？难道还有别的神奇办法？
      诸位放心，没有的！没有别的神奇办法！基本变换无法应付的情况也不可能出现！不过上图确实也是真的，不是用photoshop做的手脚。问题的关键在于这个迷题存在6个特殊的方块——空白方块！！
      迷题作者在制作迷题的时候，每一个空白方块必然有它自己的位置，然后作者通过基本变换把全部方块弄乱了，现在我们通过基本变换把方块复原。于是就存在了这样的情况：也许某一个甚至某几个空白方块并没有被放回到它原来所应该在的位置，我们在画面上无法得知这种错误的存在，但这种隐藏的错误就被带到迷题的最后显现出来。好像上面那幅图，有两个有花纹的方块位置不对，即是说，整个画面中肯定还有至少两个空白方块的位置错了。
      现在明白为何实战篇写到13步就中断，而插入这一章的原因了。因为对于普通的此类迷题来说，到13步确实已经大功告成，出现这一章的原因仅仅是因为破箱人中这条迷题的特殊性。
如何解决？
      有“空白方块”是对我们解密不利的因素，我们就把它转化为有利因素。既然程序没有硬性规定空白方块必须回到原位，那么在最后一步的8个方块中，包含空白方块越多，我们的自由度就越大。如果从12步开始是从下往上排到达13步则空白方块有3个，因此在12步看似能够任意选择，但鉴于破箱人这条迷题的特殊性，为了避免后面麻烦，我们还是应该选择从下往上排的顺序较佳。

继续解迷
      然后我们回到第13步，现在拥有3个空白方块了。继续我们的工作吧～（后面可是重点哦）

      14、继续从下往上排左边列的方块，开始两个非常容易，随便调也可以得出

      15、一次旋转

      16、一次互换，到位！下一目标只需旋转两次即可。

      17、现在8块挪移最后的关键了，如何把最后左列最后两块安排到位？而且我们注意到破箱人这道迷题烦人的特殊性又来了，究竟A、B、C哪一个才应放在左列最上方？虽然表面上看来哪一个都无所谓，但实际上通过上一章的实践我们知道，放错的话最后很可能就无法完成拼图了。我们只能采取的碰运气的办法，如果一块不行再选另一块吧。
好，假设我们已经选定了先用哪一块放在左列，然后应该怎样调节呢？这里还是必须采取两块联动的办法，注意到目标方块有花纹的那块（给它起个绰号叫“花纹”），如果“花纹”能够处于坐标（1，4），选定的例如A方块能处于坐标（1，5），那么通过简单旋转上面四块方块，就能使两块目标方块同时到位了。基于这一想法，接下来的步骤就很简单了

      18、先让“花纹”处在坐标（1，4），然后通过互换把选定的另一空白方块移到坐标（1，5）即可，既然现在B能直接互换，我们就先尝试用B来排左列吧

      19、一次互换把B移上来，大家看到了，很好运气对吗？居然我们尝试的第一个空白方块B就是那块应放在左列的！！剩下的事情大家都会做了吧？

tabris · 发表于 2007-8-16 22:48

错误时的情形：

      当然我们不会每次都那么好运气，也许下一次游戏就没有已B为首选选，于是上图的情况就可能出现了。表面上左列是对的，但我们的定理一却不适用，呵呵～因为困扰人的佯谬再次出现了！
      这时我们最好先标记一下那块错误的格子，记住它的特征，继续移动时就别把它放到左边了，已第一幅图为例，我们继续做调整：
      假如我们选择用A做尝试，那么现在只需旋转一下，把“花纹”转到坐标（1，4），然后把A互换上来就可以了，很明显，我们就将受阻在第二幅图的情形之下。

      假如我们选择用B做尝试，那么先把B互换下去，和上面一样旋转“花纹”到坐标（1，4）

      再次把B互换上来，

      再稍微旋转一下，结果……

      定律一开始发挥作用，迷题彻底破解！！

      总结一下，其实此类迷题的关键还是在最后8个方块的腾挪问题上，其他方块相信即使没有这篇小文总结的“旋转”“互换”，绝大部分人都能轻易完成。通过总结的定律一，把最后8个方块的问题简化为4个方块的问题，简化了一步。在本文最后一章的讨论中，我们看到，其实4个方块问题中的2块也是完全没有发生变化的，于是最终问题就简化为“左列上端2个方块的问题”，这对于形成破解迷题的思路无疑是有一定帮助的。对于如何解决这“2个方块”的问题，请仔细研究一下第17、18的分析，应该能够明了的。

AVG迷题探索第一篇到此结束，谢谢大家支持啦～

soring123 · 发表于 2007-8-16 23:02

这帖子精彩啊腾挪问题一直为很多人所捆饶

XYZ · 发表于 2007-8-16 23:09

明天再加100金币！

soring别急，你的全完工了也给你加啊，不吵，有糖！

帖子真的精彩，希望能再接再厉，争取成为avg的系列工具书，以后大家解谜的时候也有据可查了！

PS：avg玩到这份上，可以出书了哈哈

柠檬2099 · 发表于 2007-8-16 23:11

这个精彩阿
我玩这种游戏一向是凭着感觉和运气瞎掰的

这下有指导思想了

vexer · 发表于 2007-8-16 23:56

tabris你理论基础太强了～能把游戏中的谜题分析得这么透彻还真是难得

本来还琢磨着写个数学知识在谜题中的应用浅谈的。算了不班门弄斧了，还是你继续写吧！

田横 · 发表于 2007-8-17 00:10

看来我的直觉不错，做这类谜题从来没想到数学上，呵呵!

XYZ · 发表于 2007-8-17 08:13

引用第7楼vexer于2007-08-16 23:56发表的 :% H$ c- R% q0 i& Y" d& S
tabris你理论基础太强了～能把游戏中的谜题分析得这么透彻还真是难得6 h# b: I9 ?. ?1 s( l$ k" f6 W

! z+ \, w0 T) C% R4 r" i7 V+ O本来还琢磨着写个数学知识在谜题中的应用浅谈的。算了不班门弄斧了，还是你继续写吧！

别啊，vexer 该写就写，一向欢迎百家争鸣嘛，每个人的角度和想法肯定不同，都是很有价值的！

技巧 AVG迷题探索（01）

[技巧] AVG迷题探索（01）

楼主热贴

社区热点

本帖子中包含更多资源