AVG迷题探索（02）

tabris · 发表于 2007-8-21 13:55

      破箱人中的这个迷题颇为有趣，如果我们换个角度来思考，把进入迷题时各灯泡的状态看作一幅图画，而把电源接通后各灯泡的状态也看作一幅图画的话，那么这道迷题也可以当作是一幅“拼图”类型迷题吧～不过这个“拼图”却不是靠“移动”各部分来“拼”成的，而是依靠“旋转”各部分来“拼”成的。
      如果各行列的旋转按钮不像现在一般有个指针的话，即使我们能够看到这个拼图的最终状态，我们有把握把它拼好么？恐怕不是每个人都有肯定的回答。
这个迷题的变化真的如此复杂吗？事实上这却是一个最最简单的拼图迷题，为什么？请看下面的分析。
      这类迷题和其他拼图迷题的产生方法是一样的，都是在整齐拼图的基础上，由迷题作者通过使用和游戏者一样的操作方式随意变动而产生的。那么先让我们看看迷题作者对这幅拼图的变动产生了什么效果。

      迷题作者通过点击每一行或列上的旋钮来旋转该行或列的全部方格，因此我们可以用上表来表示全部方格的变化情况。假设全部方格的初始状态为0（即没有经过旋转），然后方格每被旋转一次，它的状态数值就增加1，最后表上的数字就能很清楚的显示出迷题作者对拼图做过什么手脚了。

      例如作者对A列做了两次旋转，对5行做了一次旋转，表格的表示就如上图所示，可以看到行列相交的方格A5因参与了两次调整，故已经旋转3次了。
      于是，作者就开始对这个表格（也就是迷题本身）做随意的调整了：

      呵呵～现在简直就是一团糟嘛，作者的任务就完成了，游戏上市，摆在我们面前的就是这“一团糟”的东西，怎么办？
      看着上面这些毫无规律的数字当然头痛，但应该记住，上面的数值只表示每个格子经过了几次旋转，但并不代表格子的状态。实际上因为是正方型的格子，所以格子的状态只有4种而已。因此我们可以先通过一些转换，把表示旋转次数的数字变为表示状态的数字，方法是把上图数字对4取模（即与4相除取其余数），于是得出：

      现在的画面好看很多了，每个数字1、2、3、0分别代表该方格处于的不同状态，很显然，我们需要做的就是让全部数字归0，这样就能把拼图复原成初始状态了。所谓“归0”，就是继续旋转数字为“1、2、3”的格子，使其累加转动次数变成4（记住：状态4＝状态0）。

  这里介绍一种极其简便的“归0”方法：选定任一行或任一列为目标，先把它全部归零，然后再调节其他的列或行，这样每行/列的旋转次数都不需要超过3次就可以解决问题了。还是以上图为例，假设我们选择先调整E列：

      我们通过点击按钮1两次，使行1的全部方格转动两次，E1的状态即由2转为0（4）了。同理我们通过按动按钮2～8，把E列的全部方格“归0”，

      看到了，结果很神奇对不对？尽管我们只把注意力放在E列上，可是当把E列全部“归0”后，其他列上的方格居然也自动排列得整整齐齐了。
      剩下的工作就是通过A～H几个按钮，把不为0的列转过来就好了。

      上面的方法可不是碰巧的呀，如果有朋友表示怀疑，说我们是碰运气，那请继续看下面的证明。

（附上一个excel小程序，各位可用来测试本文内容）

tabris · 发表于 2007-8-21 14:00

证明：

      假设作者在打乱拼图时，对每一列的转动次数为x1～x8，每一行的转动次数为y1～y8，那么每个方格转动的次数可以在上图这样表示出来。和前面的步骤一样，我们对全部方格的转动次数对4取模：

      还是和刚才一样，我们随便选一列，譬如x5列为第一目标进行“归0”。以x5y1格为例，该格子现在的状态是(x5+y1) mod 4，那我们要调整y1多少次呢？设调整次数为Δ1，则：
                                             （（x5+y1）mod 4 +Δ1）mod 4 = 0

      因为:
                                                            （x5+y1）mod 4 < 4

      所以上面方程可转化为：
                                                      （x5+y1）mod 4 +Δ1 = 4

      所以调节次数Δ1等于：
                                                      Δ1 = 4 -（x5+y1）mod 4

      按照方程结果，旋转y1行Δ1次，则y1行全部方格的状态变为（全部列出太长了，截选一个方格来说明）：
x1y1方格：
                                             （x1+y1） mod 4 + 4 -（x5+y1）mod 4

      为了表示出方格状态，上式必须再对4取模：
                                    （（x1+y1） mod 4 + 4 -（x5+y1）mod 4）mod 4

      简化一下：
                                                      （x1+y1 - x5 - y1） mod 4

      于是x1y1的状态为：
                                                         （x1 - x5） mod 4

      同理我们可以得到调整后y1行全部方块的状态如下：

同样的方法，我们可以算出y2～y8行的旋转次数Δ2～Δ8，并使整个矩阵的状态变为：

      可以清楚看到，现在同一列上的方格都处在同一状态之下，这和我们实例中的结果是一致的。证毕！

好了，这条迷题的分析只能到这里为止，实际上我们分析的只是这一类迷题中格子的旋转规律，通过这种规律总结出一般的方法，使用此方法可以迅速把迷题调节到解决状态，但前提是我们事先知道“解决状态”的图案。

所以，很遗憾，虽然我们找到旋转规律，却仍无法解决破箱人这道迷题，因为刚刚面对时我们跟本不知道“解决状态”是什么样子的。呵呵～我们架起了桥梁，可不知道对岸在哪。这个问题小弟实在还没解决，请高手来指教了！

soring123 · 发表于 2007-8-21 14:33

我顶 tabris你也忒牛了吧

soring123 · 发表于 2007-8-21 14:34

学了两年的高等数学都看不懂我要仔细研究下

闪光 · 发表于 2007-8-21 14:45

我的高等数学

简直没学过

tabris · 发表于 2007-8-21 15:13

向soring救助，我贴子里附的excel小程序不能锁定，请你下了看看怎样修改才行。谢谢啦～

vexer · 发表于 2007-8-21 15:14

我草[s:15] ～tabris你是搞得越来越虚幻了～
感慨完了再慢慢看～～～

tabris · 发表于 2007-8-21 15:19

其实可以不看后面的证明的，那个东西我都觉得很烦，把附件下载了点点就完全能够明白什么意思了哦 [s:1]

soring123 · 发表于 2007-8-21 15:37

晕完全不会用excel 看得出tabris已经是高手了

tabris · 发表于 2007-8-21 15:41

没办法呀～工作需要，每天必用EXCEL，是个宝

技巧 AVG迷题探索（02）

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

楼主热贴

社区热点

本帖子中包含更多资源