24点算法，如何给出所有不同的答案

Question

比如 2，4，6，Q(12) 这4个数，可能的答案有：

2 + 4 + 6 + 12 = 24
4 × 6 ÷ 2 + 12 = 24
12 ÷ 4 × (6 + 2) = 24

但要过滤掉雷同的答案，比如：

(12 + 6) + (4 + 2) = 24 (用交换律、结合律给出的不同答案是雷同的)
12 + 6 ÷ 2 * 4 = 24 (加减法或乘除法顺序颠倒)

还有无用的数怎么组合都是雷同的，比如：4，5，5，6 这四个数，以下两个答案只能算一个：

4 * 6 + 5 - 5 = 24
4 * 6 * 5 / 5 = 24

感觉挺复杂的，一时想不到一个好办法来处理。

补充

搜到一个算24点的页面：http://www.dffyw.com/tool/24.htm ，但是它会把所有的雷同情况都列出来，比如输入 2，4，6，12 这4个数，会有394种答案，其实不同的答案并没多少。

再补充

我自己穷举了下，2，4，6，12应该有以下10种不雷同的解答：

12+(6+(3*2))=24
(6*(3*2))-12=24
3*(12-(6-2))=24
6+(12*(3/2))=24
(2*(12+3))-6=24
12+(3*(6-2))=24
(3*(12-2))-6=24
6+(2*(12-3))=24
(12/2)+(6*3)=24
(12*3)-(6*2)=24

应该没有更多的吧。

再补充

带1和2的情况要特殊考虑，例如：A、J、K、Q

12*((13*1)-11)=24
12*((13/1)-11)=24

用1来做乘除法时，属于雷同的解答。又例如：2、2、3、3

(2+2)*(3+3)=24
2*2*(3+3)=24

2+2和2*2应被视为雷同的步骤。

Answer 1

题主所说的“雷同”，可以理解为“用字母替换数字后得到的代数式等价”。也就是说，当得到一个24点算式后，把它用代数变换导出的所有算式均不视为新发现。比如：

算式	对应代数式	雷同？
4 × 6 ÷ 2 + 12 = 12 + 6 ÷ 2 × 4	$$a\ b / c + d = d + \frac{b}{c} a$$	雷同
4 × 6 + 5 - 5 = 4 × 6 × 5 / 5	$$a\ b + c - c = a\ b\ c / c$$	雷同
12 ÷ 4 × (6 + 2) = 4 × 6 ÷ 2 + 12	$$\frac{a}{b}(c + d) \ne b\ c / d + a$$	不雷同

因此得到算法：

1. 构造所有的数字算式

2. 筛选出计算结果是24的算式

3. 将算式中的数字用符号替换，并对得到的代数式做等价判断，每个等价类选出一个代表

4. 输出代表代数式对应的数字算式

这种穷举构造法的复杂度至少是指数级的，因此不适用于数字较多的情况。

Mathematica 实现

Mathematica 的符号代数功能非常适合处理这类题目。

Clear[game24]
game24[input_List, result_: 24] := Block[{add, sub, mul, div},
  With[{
    oprules = {add -> Plus, sub -> Subtract, mul -> Times, 
      div -> Divide},
    specifics = {div[x_, 1] :> x, mul[x_, 1] :> x, mul[1, x_] :> x, 
      add[2, 2] -> mul[2, 2]}},
   Map[RightComposition[
     Hold, ReplaceAll[oprules], ToString[#, InputForm] &,
     StringDelete[{"Hold[", "]"}], 
     StringReplace[{"*" -> "\[Times]", "/" -> "\[Divide]"}]],
    Union[
     Select[result == (# /. oprules) &]@
      Groupings[Permutations@input, {add, sub, mul, div} -> 2],
     SameTest -> (0 === 
         Simplify[
          sub[#1, #2] //. specifics /. 
           Prepend[oprules, k_Integer :> ToString[k]]] &)]]]]

1. 用符号add、sub、mul、div分别对应加减乘除四则运算，构建二叉树代表算式。Groupings函数生成了所有可能的表达式二叉树。

2. Select筛选出计算结果符合要求的。

3. Union负责除去雷同的算式。它的SameTest选项计算两个代数式的差化简后是否为0。注意这里通过把数字转为字符进行“符号化”了，而且对数字1、2进行了特殊处理（specifics）。

4. 最后Map负责把每个算式转成字符串输出。

测试：

Answer 2

花了近一周时间用JavaScript完成了24点去重算法，源码提交到了github上：https://github.com/auntyellow/24 ，可以在线试：http://ns1.xqbase.com:8080/24...

在1到13范围内的四数组合中，不重复解最多的组合是2、4、8、10：

10 + 8 + 4 + 2 = 24
(10 - 4) × 8 ÷ 2 = 24
(10 × 4 + 8) ÷ 2 = 24
((10 + 2) × 8 ÷ 4 = 24
10 × 2 + 8 - 4 = 24
(10 - 2) × 4 - 8 = 24
8 × 4 - 10 + 2 = 24
(8 ÷ 4 + 10) × 2 = 24
(8 × 2 - 10) × 4 = 24
(10 - 8 ÷ 2)) × 4 = 24
10 × 4 - 8 × 2 = 24

只能用分数来解的(16个，这里不给答案了，有兴趣可以自己练练)：

1, 3, 4, 6
1, 4, 5, 6 // 这题居然有两解，都必须用分数的
1, 5, 5, 5
1, 6, 6, 8
1, 8, 12, 12
2, 2, 11, 11
2, 2, 13, 13
2, 3, 5, 12
2, 4, 10, 10
2, 5, 5, 10
2, 7, 7, 10
3, 3, 7, 7
3, 3, 8, 8
4, 4, 7, 7
5, 5, 7, 11
5, 7, 7, 11

其他有难度的，就是中间过程必须有大数的(大于36就很难一下子想到了)，像a × b - a × c = 24这种形式，比如10、12、12、12，其实并没有太大难度，就没有列进去：

1, 7, 13, 13
6, 12, 12, 13
1, 6, 11, 13
6, 11, 12, 12
5, 10, 10, 13
1, 5, 11, 11
5, 10, 10, 11
4, 8, 8, 13
4, 4, 10, 10
4, 8, 8, 11
6, 9, 9, 10
3, 8, 8, 10
3, 5, 7, 13
3, 6, 6, 11
1, 2, 7, 7
5, 8, 9, 13
5, 9, 10, 11
4, 7, 11, 13
4, 9, 11, 11
4, 10, 10, 11
6, 7, 7, 11
3, 5, 8, 13
5, 5, 8, 11
2, 3, 13, 13

还找到一个难的：3、7、9、13，它有两种解法，一种用到了分数，一种有大数。

为了验证这些结论，还是查到了 http://4shu.net 那边，包括 http://4shu.net/theory/ (我的算法跟这里相当接近了)、所有独立解 － 24理论 解决二十四点 http://4shu.net/solutions/all... (解法最多的牌型确实有11个解)， http://4shu.net/solutions/fra... (确实有16个牌型)，看来程序是没太大问题了。

=== 然后说说算法 ===

参考知乎上 https://www.zhihu.com/questio... ，还有本题 @萝卜 的回答，总之就是列出所有不等价表达式，例如((a + b) * c) / d和((b + a) * c ) / d是等价的，需要去重。

虽然是重复在做很多人以前做过的工作，但还是有些自认为别出心裁的思路，因为并没从代数形式上做分析，而是通过试数的办法做的，试的是π、e、ln π和arctan e这四个超越数，对近似值做比较（浮点数运算总是有误差的）来判断两个表达式是否等价。（我把近似度设定在1e-6其实算是碰巧蒙对了，萝卜指出lnπ/(e + π/arctan(e))和π/e - lnπ/arctan(e)只相差7.9e-6，如果把近似度再提高1个数量级，结果可能就不对了。）

5种括号型(((oxo)xo)xo、(ox(oxo))xo、(oxo)x(oxo)、ox((oxo)xo)、ox(ox(oxo))，其中o代表数字，x代表运算符)，4个数一共有24种排列，3个符号一共有64种排列，总共需要“试数”的表达式总共有7680个，在这些表达式中找出了1170种不等价的，也和网上能找到的资料相吻合，例如知乎上 小于0 给我推荐的 http://oeis.org/A140606 。

后来发现，仅仅用这1170个表达式是不够的，还要考虑以下14种牌型：

a, a, b, c // 两个相同的数可以交换，也可以抵消
a, a, b, b
a, a, a, b
a, a, a, a
1, a, b, c // 1可以舍去
1, a, a, b
1, a, a, a
1, 1, a, b
1, 1, a, a
1, 1, 1, a
2, 2, a, b // 2 + 2 = 2 × 2，这个算重复解应该说得过去
2, 2, a, a
1, 2, 2, a
2, a, a, b // 2 × a - a = (a + a) ÷ 2，这个居然被我算成重复解了！

另外还有，a、a'(=a+1)、b、c这种牌型，需要把(a'-a)参与乘除运算的解法排除掉，然后单独算b+c、b*c有没有可能等于24。

所以程序里绝大部分逻辑都是在判断：牌型到底属于上面列出来的15种当中的哪一种，写得相当啰嗦。

另外还有一些小问题，比如：

• 1、1、5、5，只给出了一种解，因为对牌型1、1、a、a组成的表达式来说， (a+1)(a-1)和aa-11是等价的；

• 没有考虑4/2和4-2等价的问题，例如2、4、6、6，(6-(4-2))6和(6-4/2)6被认为是两个不等价的解(凭什么2+2和2*2等价，但4-2和4/2不等价？)

• 当2作为中间步骤时，没考虑2+2和22的等价，还拿2、4、6、6说事，(6-4+2)6和(6-4)26是不等价的解(写到这里我真后悔把2+2和2*2算做等价了)

仔细想想，还真不能轻易认为2+2=2*2、4-2=4/2是等价解法，要是真这么算的话，那么我们可以写出：

(6-4/2)*6 = (6-(4-2))*6 = (6-4+2)*6 = (6-4)*2*6

显然每个等号左右两边都是等价的。但要说最左边的和最右边的是重复的解法，那又说不过去了。

看似很简单的问题，本以为可以花半天时间搞定的，结果编码、测试、验证、优化一系列过程居然花了1周的时间，再次印证了我的盲目乐观 :-(

Answer 3

python3

##趣味24点游戏

import itertools as itrs

EPS = 1e-6 # 极小值 ε epsilon
ops = itrs.product(r'+-*/',repeat=3) 

fmt = [
    '{A}{x}{B}{y}{C}{z}{D}',
    '{A}{x}(({B}{y}{C}){z}{D})',
    '(({A}{x}{B}){y}{C}){z}{D}',
    '({A}{x}{B}){y}({C}{z}{D})',
    '({A}{x}({B}{y}{C}){z}{D}',
    '{A}{x}({B}{y}({C}{z}{D}))'
]

s = input('输入4个数字，以空格分隔，例：5 5 2 4\n>')
nums = set(itrs.permutations(map(str,map(float, s.split()))))

formula = set()
for f,n,op in itrs.product(fmt, nums, ops):
    f = f.format(**dict(itrs.chain(zip('ABCD', n),zip('xyz', op))))
    try:
        if (f not in formula) and (abs(eval(f)-24.) < EPS) : 
            print(f.replace('.0',''),'= 24')
            formula.add(f)
    except :
        continue 


input('-结束-')

输入4个数字，以空格分隔，例：5 5 2 4
>3 3 8 8
8/(3-(8/3)) = 24
-结束-

Answer 4

有想法，没代码

首先，用表达式树的形式生成所有解，类似这样

    *
   / \
  ÷   +
 / \ / \
12 4 6 2

然后，对每一个解作变换。比如+下的6和2可以互换，×子树可以互换，等等，这样生成这个表达式树对应的所有可能的表达式树对应的表达式字符串，存在字典中。如果一个表达式树的表达式字符串已经存在了，那这个数就可以放弃，继续查找下一个。
最后，所有剩下的表达式树挑一个表达式列出来作为不重复解。