主题：【原创】用计算机求解一个儿时的游戏 -- 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天也算不出来）。那么这时候算法就要优化，要有些智能，及早排除那些“压根就没谱”的表达式。据说当初深蓝大战国际象棋大师的时候，就有些“投机”。当卡斯帕罗夫走出一步棋的时候，深蓝会利用“常识”首先排除一些荒唐的走法，同时利用卡斯帕罗夫历史上胜负的记录优先选择一些方案。当然即使是这抄近道儿，要估算出十几步以后的情况，出现的组合数量还是触目惊心的，计算机之大非深蓝这种超级计算机才可能完成。

好了，就说到这里吧！

不过好几年前玩的手机里就有这个java游戏：24点，当自己无解是手机会给出正解。

毕竟只能是四则运算，那种小数，开方什么的高级货不算的。24是个偶数而且可以被3整除，同样的数字有12，36等，我猜3张牌算12，5张牌算36不错。就4张牌而言，算出24也许是4张牌的排列组合中最多的。一点愚见。

一般说来算24只用四则运算，不过即使这样也有很多很tricky的解，比如你的第一个case：7，7，4，4实际是有解的。我先不说答案，有兴趣消磨时间的同学可以想想。

另外解的同构性判断是个很复杂的问题，在组合搜索中，这种判断往往比寻找解的算法还要难。比较简单的处理办法可能是找到一个解就返回，不去追求多个解。

搜索树的修剪也是门大学问，如何优先发展有希望的分支，正是AI中的A*算法的核心问题。

花！

似乎Highway的算法原则上没问题，我猜可能是4/7这种除不尽的时候截断保留小数了，所以后来再X7的时候就和24差一点点。

都花！

恭喜：意外获得【西西河通宝】一枚

谢谢：作者意外获得【西西河通宝】一枚

鲜花已经成功送出

PS. Highway叫Jinsong，hehe

fix了一下，给出了两个答案（7，7，4，4四张牌）

Please input 4 numbers here, like "7, 8, 11, 9"
4, 4, 7, 7
The solution is: (4 - (4 / 7)) * 7
The solution is: 7 * (4 - (4 / 7))

仔细一看，其实是一种算法。我现在基于String表达式的算法甄别不出来。简单的fix就是把这些表达式标准化一下,这样形似的算法就会“合并”起来。

刚才把取余数算法加了进来，答案有多了一些，变成了

The solution is: (4 * 7) - (4 % 7)
The solution is: ((4 % 7) * 7) - 4
The solution is: 7 * (4 - (4 / 7))
The solution is: (7 * 4) - (4 % 7)
The solution is: (4 - (4 / 7)) * 7
The solution is: (7 * (4 % 7)) - 4

如果把乘方加进来，好多问题变得更有趣了。

不是出在那里。是计算组合的情况我遗漏一些。

BTW，眼力不错。不过那是Vista login的user name，未必是我的名字，再说我用的也许是别人的计算机呢。你这个算法有“问题”。哈哈

The solution is: 6 / (1 - (3 / 4))

牛掰不?

如果只是四则运算，答案是

The solution is: (5 - (1 / 5)) * 5

The solution is: 5 * (5 - (1 / 5))

如果可以用取余数，那么多一个答案

The solution is: (5 * 5) - (1 % 5)

如果还可以用乘方，那么又多一个

The solution is: (5 * 5) - (1 ^ 5)

can you give me your code in C here?