用Python解“智力游戏”

大家好，欢迎来到Crossin的编程教室！我是Crossin。

之前国庆假期在家闲来无事，找了一本“思维训练手册”（其实就是一些智力题、推理题，甚至“脑筋急转弯”），跟家人一起玩智力游戏。这些题是不是真的可以训练人的思维我不知道，但是看了几题我忍不住要吐槽：这真的不是从“青少年信息学奥林匹克”题库里找出来的题吗？！

里面有不少题，让人做是有的烧(wu)脑(liao)，但如果改成编程题，那倒有点意思了。

于是，原本拿着纸笔做题的场景，就立马被我改成了拿出电脑敲代码的画风。

我从里面挑了3题，你们感受一下。

如果你像我一样喜(xian)欢(de)挑(wu)战(liao)，也可以来试试，不管用不用编程。

答案在文末，另外也附了我的代码解法，欢迎取用。

1.

（答案见文末）

思路提示：

用程序解这类“智力题”有个屡试不爽的方法，就是“枚举法”，或者叫做“暴力解法”。就是对于存在有限种可能选择的情况下，让程序把每一种情况都试一遍，找出符合条件的解。

这题就可以暴力去解。

当然，暴力最好也要有头脑的暴力。比如这里，5个3位数，从中去掉9个数，听上去有点烦。但反过来想，其实不就是从里面挑6个数字嘛！

100、10、1、300、……、90、9，这15个数里面取6个，使得它们的和是1111，这我已经不能再提示了吧！

对了，再说一句：Python里有个取排列/组合的库，叫做：itertools。谁用谁知道

2.

为了方便讨论，我给这些圆圈加上编号：

（答案见文末）

思路提示：

这题，比上一题复杂，因为它的不是一个规则的“形状”。但它的可能性依然是有限，且不是很多。

9个数放进9个格子里，最多也就是9!=362880种情况，这对于计算机来说是个小case。关键在于你如何判断某种情况是符合要求的。

如果你看过“数据结构”有关的书，应该会想到这个结构就是一个“图”。我们可以将每个格子定义为一个类，也就是一个节点，每个节点有一个值，还有一个列表，记录它相连其他节点。

判断一个节点是否符合要求，就把它相连节点的值加起来，看看是否与它自己的值所对应的和相等。如果每个节点都符合，那就是我们要的答案。

不过呢，这题还有另一种思路，就是用“递归”去解：

1. 判断 n 个值和 n 个格子是否有解

2. 将一个“不违反条件”的值放入一个格子，然后判断剩下 n-1 个值和 n-1 个格子是否有解，以此类推

3. 如果格子全部放完，即得到答案

4. 如果剩下的值里找不到“不违反条件”的值，则退回上一步，选择下一个值继续

不过就这题来说，递归的条件设定有点复杂，我就不展开细说了，代码里我也给了递归的版本。

特别说明：枚举版本最后遍历了59674种情况，在我的电脑上花了0.18秒“撞”到了答案；而递归版本判断了5320种情况，花了0.015秒。

3.

（答案见文末）

思路提示：

这题就不再适合暴力去解了，因为52个值分到4个盒子里，一共是有4的52次方，也就是20282409603651670423947251286016种情况……

但是仔细想一下，这题也不必暴力。我们只需要把52个值从小到大依次往盒子里放就行。只是放的时候需要判断一下，哪个盒子是“不”能放的，即其中盒子里已有两个数的和等于这个值。如果存在，那么就去下一个盒子，此处不留爷，自有留爷处！（处处不留爷，那一定是题目出错了！）

OK，先就来这3题试试看吧！

讲真，这种题虽然没啥实际意义，但若真要你用代码写出来，也不是那么容易的，很考验你对程序逻辑和数据结构的理解。所以，很多IT公司在招聘开发岗位时也会出一些类似的题，既是考察你分析问题的能力，也能看出你写代码的水平。讲不定哪天你就在面试时碰到我发过的题目呢。（事实上，这种事已经发生过几次了，甚至还有面试官就直接拿我的题目去面人的）

欢迎在留言区分享你的解答！如果大家对此类题目感兴趣，之后我再多弄一些来。

本文题目来源自《思维高手:全世界聪明人都在做的200个思维游戏》

相关代码：

crossin/snippet

智力题

答案：

1.

111

x3x

x7x

9xx

(此题共有5个解，参见代码输出)

2.

按图上圆圈标记顺序：

2, 5, 8, 9, 3, 4, 6, 7, 1

3.

[1, 2, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52],

[3, 5, 6, 12, 14, 21, 23, 30, 32, 39, 41, 48, 50],

[8, 9, 11, 15, 18, 35, 36, 38, 42],

[17, 20, 24, 26, 27, 29, 33, 45]

(此题也不是唯一解，比如把48放进盒子4也是可以的)

----

获取更多教程和案例，

欢迎搜索及关注：Crossin的编程教室

这里还有更多精彩。一起学，走得远！