纸牌游戏：24

发表于 更新于 分类于 Disqus：

可能是太想排到车号了，最近上下班路上总是盯着过往车辆的号牌。盯着盯着就会下意识地思考：「怎么用上面的数字经过加、减、乘、除得到 24」，比如下面这个车牌：

既可以 "(6 + 3) × 8 ÷ 3"，也可以 "(3 × 3 - 6) × 8"。有时候就这么算着、算着，到达目的地仍觉得意犹未尽。

这个「下意识」的背后是一群理科少年们迷恋的纸牌游戏：24。大概是高二的时候，我与几位同学一起到厦门双十中学参加数学夏令营，其中我还记得名字的有杜远志、吴奋强、林杰、杜明树、陈庆树。夏令营里上的是什么课我已经完全不记得，但我仍然清晰地记得：在临时宿舍里，一群少年拿着几副纸牌，热火朝天地比赛心算 24。

游戏规则很简单：拿一副完整的纸牌，剔除掉大王和小王，将剩下的纸牌平均分给比赛双方。双方各自手持一组纸牌，纸牌需背面朝上。每轮游戏开始，双方同时取出最上面的两张纸牌，反手甩到桌面上，四个数字同时出现在双方眼前。谁先算出 24，就怒拍床板，然后带着唾沫星子说出解法。先拍者先说。说对了，收入囊中；说错了，拱手送人。谁把对方手上的纸牌赢光，谁便胜出。

我的记忆里仍然有许多有意思的画面：比如我拍床板时太用力，疼得嗷嗷叫；又比如我算不过陈庆树，就找哥几个一起「三英战吕布」。我记得最经典的一道题，就是 "3、3、7、7"，当时可是难倒了一众好汉，你想不想也试上一试？ (解法在文末的代码块里)。

今天早上醒来时忽然想到：这不就是个「搜索问题？」对于我这个为了生活努力练习的算法做题家来说算是小菜一碟了。于是就在家里的白板上画起了思路：

最终这 4 个数字一定会和 3 个二元运算符组成一个算式，而且这个算式一定可以用上面这种语法树表示。那么只要从剩余的数字中遍历所有可能的两数排列，再遍历可能的运算符，就可以递归地穷举出所有可能的语法树。因为减法和除法并不具备交换性，这里两数的顺序是需要考虑的，所以遍历的是两数的排列，而不是组合。

编码实现

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
package main

import (
    "fmt"
    "strconv"
)

func MakeTwentyFour(nums []int) (expr string, found bool) {
    // in reality, as long as len(nums) >= 1, this function just works.
    // Just to be conformed with the problem I'm trying to solve here.
    _assertEqual(4, len(nums))

    var fnums []float64
    var exprs []string

    for _, num := range nums {
        fnums = append(fnums, float64(num))
        exprs = append(exprs, strconv.Itoa(num))
    }

    found, expr = solve(fnums, exprs)
    return
}

func solve(nums []float64, exprs []string) (found bool, solution string) {
    _assertEqual(true, len(nums) >= 1)
    _assertEqual(len(nums), len(exprs))

    if len(nums) == 1 {
        return nums[0] == 24, exprs[0]
    }

    // iterate through all possible pairs of numbers from nums.
    for i := 0; i < len(nums); i++ {
        for j := 0; j < len(nums); j++ {
            if i == j {
                continue
            }

            nextExprs := make([]string, 0, len(exprs)-1)
            nextNums := make([]float64, 0, len(nums)-1)
            for k := 0; k < len(nums); k++ {
                if k == i || k == j {
                    continue
                }
                nextExprs = append(nextExprs, exprs[k])
                nextNums = append(nextNums, nums[k])
            }

            for _, op := range []byte{'+', '-', '*', '/'} {
                var num float64
                switch op {
                case '+':
                    num = nums[i] + nums[j]
                case '-':
                    num = nums[i] - nums[j]
                case '*':
                    num = nums[i] * nums[j]
                case '/':
                    num = nums[i] / nums[j]
                }
                nextNums = append(nextNums, num)
                nextExprs = append(nextExprs,
                    fmt.Sprintf("(%s%c%s)", exprs[i], op, exprs[j]))

                if found, solution = solve(nextNums, nextExprs); found {
                    return
                }
                nextNums = nextNums[:len(nextNums)-1]
                nextExprs = nextExprs[:len(nextExprs)-1]
            }
        }
    }
    return false, ""
}

func _assertEqual(expected, actual interface{}) {
    if expected != actual {
        panic("assertion failed")
    }
}

func main() {
    cases := [][]int{
        {1, 1, 1, 1},
        {2, 2, 2, 2},
        {3, 3, 3, 3},
        {4, 4, 4, 4},
        {5, 5, 5, 5},
        {6, 6, 6, 6},
        {3, 3, 7, 7},
        {1, 2, 3, 4},
        {2, 3, 4, 5},
        {3, 4, 5, 6},
        {4, 5, 6, 7},
        {5, 6, 7, 8},
        {6, 7, 8, 9},
        {7, 8, 9, 10},
        {3, 8, 4, 5},
        {3, 3, 7, 9},
        {13, 3, 13, 1},
        {11, 3, 7, 2},
    }

    for _, nums := range cases {
        expr, found := MakeTwentyFour(nums)
        if !found {
            fmt.Printf("%v: not found\n", nums)
        } else {
            fmt.Printf("%v: %s\n", nums, expr)
        }
    }
    // [1 1 1 1]: not found
    // [2 2 2 2]: not found
    // [3 3 3 3]: ((3*(3*3))-3)
    // [4 4 4 4]: ((4+4)+(4*4))
    // [5 5 5 5]: ((5*5)-(5/5))
    // [6 6 6 6]: ((6+6)+(6+6))
    // [3 3 7 7]: (7*(3+(3/7)))
    // [1 2 3 4]: (4*(3+(1+2)))
    // [2 3 4 5]: (4*(5-(2-3)))
    // [3 4 5 6]: (6*(5+(3-4)))
    // [4 5 6 7]: (4*(7+(5-6)))
    // [5 6 7 8]: ((5+7)*(8-6))
    // [6 7 8 9]: ((6*8)/(9-7))
    // [7 8 9 10]: ((8*9)/(10-7))
    // [3 8 4 5]: (4*((3+8)-5))
    // [3 3 7 9]: ((3-7)*(3-9))
    // [13 3 13 1]: ((13-3)+(13+1))
    // [11 3 7 2]: ((11*3)-(7+2))
}

写完这几行代码，就像喝完冰可乐一样令人满足。虽然不是解开了什么世纪难题，但这是对那段青葱岁月与快乐时光的一次回味。

参考