主题：【原创】用计算机求解一个儿时的游戏 -- Highway

昨天在河里瞎逛的时候，看看面壁网友的一个回帖

看了这个问题，使我马上联想起小时候常玩的一个游戏。大概在二三年级的时候（注意不是大二大三大时候），常和小朋友们在一起用扑克牌玩一种心算游戏。一般是4个人玩（2个人也成），一开始每个人分一摞扑克牌。然后每轮一人出一张牌放在中间。这时候大家开始心算。谁第一个找到算法，这四张扑克牌就归谁。到最后谁手里的扑克牌最多，谁就是赢家。

那时候我们只会四则运算。所以规则很简单，就是四张扑克牌都要用到，但是每张牌只能用一次。不管是加减乘除怎么组合，能得到24就算赢。

这个游戏是谁发明的我不知道，为什么选择24也从来没有问起。事实上这个游戏设计有问题，很多情况下大家想不出答案，只能把自己出的扑克牌收回，重新再来。

那时候我们玩得时候，有大一些的孩子在旁边看我们玩（比如说谁的哥哥姐姐什么的）。有时候我们小孩子们想不出来，大孩子们可能会用一些“高级”的算法来解决问题，比如说用乘方，或是开根号什么的。

问题是当我们大家都想不出来答案的时候，可能我们是对的，这4张扑克牌无解。也可能我们是错的，我们还没有穷尽所有的组合。现在计算机这么牛，能帮着解决一下这个问题嘛？我想这可能就是面壁朋友要问得那个问题。

Highway不才，是吃计算机饭的。看到这个帖子后有些技痒。于是乎坐在那里开始发呆（所谓的思考）。想了好一阵子，基本路线大概有个眉目了以后，开始动手。手边正好有Java的IDE，于是决定用Java来写写看。

写了一阵子，又测试了几个case，一个小游戏算是基本成形了。当然这个游戏只是Proof of concept类的演示，连个图形界面也没有(寒碜啊)。

游戏是这样玩的：你在Dos Console上给出4个数字（1到13，代表A到K），然后一敲回车，计算机就开始寻

找答案。找到的话，就在屏幕上给出答案（很多时候有多种解），找不到的话，就实话实说“Sorry, I can’t find one!”.

我现在的这个小游戏很粗糙，很多地方都不是很合理，比如说计算机给出的多种答案其实是一回事。因为有些括号是多余的，A+B-C+D和B+A+D-C也只是交换了一些顺序而已。我现在的算法不具备甄别这些的能力。

我的游戏算法大概是这样的：

1） 任意给四个1-13之间的数字

2） 求出所有的排列来。4个数字的组合上限是24，如果数字有重复，排列自然就会减少，这样可以减少一些计算。

3） 把加减乘除运算符加进去，列出所有可能的计算表达式（优先级也要考虑）

4） 对每个表达式进行求解，如果是24,那么这个表达式就是一个答案。

从计算机程序的角度来讲，我现在这个程序不太合格，有几个地方是hard-coded（优先级算法上有些投机取巧）。对加减法和乘法的交换率视而不见（及A+B = B+A, A*B=B*A），造成很多重复的计算。如果有人出钱让我把这小游戏写成一个产品的话，那么正儿八经程序应该是这样的。

1） 允许扑克牌张数为1-N, 求解的答案可以是24，也可以是任何整数。用户可以自己制定游戏规则。

2） 算法可以是简单的加减乘除，也可以是更广义上的所有binary运算，比如说取余数，乘方，或者是计算机上常用的shift（<< >> >>>）等等。用户可以自由选择定制。

3） 加上美观的界面。如果用户解除了一个有难度的题目后，一定要有养眼的MM（切切）弹出。如果一个非常简单的题目也做不出来的话，可以适当的嘲笑羞辱一下（嘿嘿）

如果把这些情况都想到了，那么穷尽法可能性能上就会有些问题，比如说是玩8张牌，允许复杂算法的大游戏，那么组合很可能就会上亿。如果是玩20张牌的超大游戏，你计算机 可能3天也算不出来）。那么这时候算法就要优化，要有些智能，及早排除那些“压根就没谱”的表达式。据说当初深蓝大战国际象棋大师的时候，就有些“投机”。当卡斯帕罗夫走出一步棋的时候，深蓝会利用“常识”首先排除一些荒唐的走法，同时利用卡斯帕罗夫历史上胜负的记录优先选择一些方案。当然即使是这抄近道儿，要估算出十几步以后的情况，出现的组合数量还是触目惊心的，计算机之大非深蓝这种超级计算机才可能完成。

好了，就说到这里吧！