不可能的棋盘谜题

本文主要介绍关于图论的知识点，对【不可能的棋盘谜题】和【不可能的迷宫】有兴趣的朋友可以看下由【Liiiiiiiiiiiiiiiiiiq】投稿的技术文章，希望该技术和经验能帮到你解决你所遇的【】相关技术问题。

不可能的迷宫

B站原视频链接

https://www.bilibili.com/video/BV1UD4y1U7or

题目概述

环境的设定是：两个人A和B、一个房间、一个8×8的棋盘（棋盘的每个格子上放有一个硬币，有可能正面朝上或者反面）和一把钥匙。

游戏过程如下：首先B离开房间，房间内只有A、随机初始化的棋盘和随机初始化的一把钥匙（棋盘的初始化指硬币的正反，钥匙的初始化指把钥匙藏于某一个方格下面）。然后A根据看见的棋盘和钥匙藏的位置选择一枚硬币进行翻转。最后A离开房间，B进来，B需要根据看见的棋盘推测出钥匙藏的位置（B知道A翻转了一个硬币，但是不知道具体是哪一个）。

游戏的目标是允许A和B商量一个策略，使得根据这个策略，B总是可以找出钥匙的位置。

个人思路简介

在看完视频中关于题目描述的部分后，我认真的思考了这个问题。我发现可以把策略看成一个函数，具体的讲是两个函数F和G。函数F用于A根据看见的棋盘和钥匙的位置选择进行翻转的硬币，即函数的自变量是棋盘（棋盘可以用64位的二进制表示）和钥匙的位置（钥匙的位置用1~64的整数表示），函数的应变量是翻转硬币的位置（翻转硬币的位置用1~64的整数表示）。函数G用于B根据看见的棋盘推测钥匙的位置，即函数的自变量是棋盘，函数的应变量是钥匙的位置。下面介绍下两个函数的形象化表示，因为等下后面要用，为了方便起见以2×2的棋盘为例（下面的讨论都以2×2为例）：

现在的问题是要如何设计函数F和G，或者讲对于每一种棋盘情况（棋盘情况共有

种）要如何去填上图中钥匙位置内的内容。只要设计好了函数F和G，A就可以根据函数F选择翻转的硬币，如下：

同理B可以根据函数G推测钥匙位置，如下：

函数的设计方法可以这样去想：站在B的角度去看，当看见一个棋盘时，他可以猜测A翻转了或第一位、或第二位、或第三位等等。一共4种可能，根据函数F可知，每一种可能都有一个自己的4的全排列，对于第一位翻转得到的棋盘的全排列中的第一位的内容就是钥匙的位置（可能有点绕，等下图示下就明白了），同理对于第二位、第三位和第四位翻转得到的棋盘的全排列中的第二、第三和第四位也可以得到3个钥匙位置，我们只需要保证这4个钥匙答案指向同一个位置即可，这样就确定了钥匙位置，如果不是全部一样，那就是概率问题了，不是必赢了。下面图示下上述想法：

现在的关键问题是如何填充函数F中对应于16个棋盘的16个全排列，使得对于任意B所看见的棋盘，都可以通过上述反推出4个全排列并观察对角线上的数字的方式找出钥匙的位置。直观的填充方法如下（正确性等下讨论）：

初始化全部全排列为空。选择一个未填满的全排列（全排列和棋盘情况一一对应，即选择一个排列等于选择一个棋盘情况）。选择一个这个全排列中的空位，记录空位位置为k，即当前选的全排列应放在“4人组”（4人组指这4个全排列满足上述图中反推过程中产生的4个全排列的性质）中的第k个。找出其余的可以组成“4人组”的3个排列，排好位置。选择一个不冲突的数填到对角线上（可以证明对角线上一定都是空位，不冲突指填的数字在每一个排列中都是唯一的，对于是否保证无冲突的讨论后面再讲，现在默认无冲突）。如果还有未填满的全排列，则跳转到步骤2，否则结束。

根据上面的算法可以设计完函数F，函数G的设计直接根据反推和函数F即可获得，下面是我根据上述算法获得的在2×2情况下设计出的函数F和函数G：

可以看出这样设计是可行的。

关于证明的问题

前面我简单的说了下我的直观思路并应用于2×2的棋盘情况，那么怎么证明对于8×8或者n×n都适用呢？关键需要证明的点有两个，一个是证明一定存在一种全排列的填充方式，可以满足上面的要求，另一个是上面的填充算法一定收敛，也就是说每一次填充都可以找到无冲突的数。由于能力有限，两个问题一个都搞不定╮(╯▽╰)╭。后来我看了下视频后面的部分，他讲了顶点着色的问题，我才发现其实我的方法本质上也是顶点着色，函数G的输入就是顶点，输出的钥匙位置就是顶点颜色，函数F的作用相当于当给定一个顶点和钥匙的位置时，向哪个方向移动（翻转一次硬币相当于一次移动）到下一个颜色正确的顶点。也就是说，可以使用视频中证明有些情况无解的方法来证明第一个点，即不是每一种情况都存在一种合适的全排列填充方式，运气比较好，2×2的情况存在解。对于第二点是否一定可以找到无冲突的数进行填充，我的算法里面的一次选空位＋填对角线相当于为某一个顶点填了一种颜色，换句话说就是我的算法相当于给顶点着色，那么是否可以找到无冲突的数和是否可以找到一个颜色涂在当前顶点上是一样的。当有解时，DFS必定可以在解空间里面找到解，当然可能比较费时间，想要更好的效率可以参考优秀的图着色算法。所以，对于8×8问题的答案，需要优化一下填充算法，或者说顶点着色算法以提高效率，同时答案本身的存储量就已经很大了，算出来可能需要很多计算资源。

本文《不可能的棋盘谜题》版权归Liiiiiiiiiiiiiiiiiiq所有，引用不可能的棋盘谜题需遵循CC 4.0 BY-SA版权协议。