纸牌游戏：24

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

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

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

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

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

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

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

编码实现

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))
}

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

纸牌游戏：24

参考