如何找到一个公式的所有可能解，例如100*7-8*3+7？（《8成猫倒计时》求解器）

Question

为了好玩，我决定写一个简单的程序来解决《10只猫中有8只做倒数计算》数字谜题，链接来自于Countdown节目的这里，但规则相同。我的程序简单地遍历AxBxCxDxExF的所有可能组合，其中字母代表数字，“x”代表加、减、除和乘法。以下是代码：

private void combineRecursive( int step, int[] numbers, int[] operations, int combination[]){
    if( step%2==0){//even steps are numbers
        for( int i=0; i<numbers.length; i++){
            combination[ step] = numbers[ i];
            if(step==10){//last step, all 6 numbers and 5 operations are placed
                int index = Solution.isSolutionCorrect( combination, targetSolution);
                if( index>=0){
                    solutionQueue.addLast( new Solution( combination, index));
                }
                return;
            }
            combineRecursive( step+1, removeIndex( i, numbers), operations, combination);
        }
    }else{//odd steps are operations
        for( int i=0; i<operations.length; i++){
            combination[ step] = operations[ i];
            combineRecursive( step+1, numbers, operations, combination);
        }
    }
}

这是我用来测试组合是否符合要求的方法。

public static int isSolutionCorrect( int[] combination, int targetSolution){
    double result = combination[0];
    //just a test
    if( Arrays.equals( combination, new int[]{100,'*',7,'-',8,'*',3,'+',7,'+',50})){
        System.out.println( "found");
    }
    for( int i=1; i<combination.length; i++){
        if(i%2!=0){
            switch( (char)combination[i]){
                case '+': result+= combination[++i];break;
                case '-': result-= combination[++i];break;
                case '*': result*= combination[++i];break;
                case '/': result/= combination[++i];break;
            }
        }
        if( targetSolution==result){
            return i;
        }
    }       
    return targetSolution==result?0:-1;
}

在上一集中，我发现了我的代码中存在的一个问题。这是其中一个谜题的解决方案。

(10*7)-(8*(3+7))

我注意到我找到了这个组合"10*7-8*3+7"（两次），但是因为我从左向右进行运算来查找解决方案，实际上我并没有找到所有的答案。我只检查这样的解决方案((((10*7)-8)*3)+7)。所以即使我找到了这个组合，我也没有正确的顺序。

现在的问题是如何测试所有可能的数学顺序，例如(10*7)-(8*(3+7)), (10*7)-((8*3)+7)或10*(7-8)*(3+7)? 我想可以使用操作作为平衡节点的平衡树，但仍然不知道如何通过不移动公式来遍历所有可能的组合。

(10*7)-(8*(3+7))
          -
     /        \
    *         *
  /   \      /  \
700   7     8    +
                / \
              7    3

(10*7)-((8*3)+7)
          -
     /        \
    *         +
  /   \      /  \
700   7     *    7
           / \
          8  3

10*(7-8)*(3+7)

                 *
           /           \
          *
     /        \         10
    -          +
  /   \      /  \
7     8     3    7

我应该如何在代码中实现这个？我不是在寻找解决方案，而是想了解如何改变思路来解决问题。我不知道为什么我会卡在这个问题上。

关于我：我是计算机科学专业的四年级学生，在编程方面并不是新手（至少我愿意这样认为 ;））

- Shawn

---

注意：这不仅仅是“8 out of 10 cats does Countdown”，而是与普通的Countdown相同的游戏。 - Andy Turner

你说得对。我找不到《10只猫中有8只做倒计时》的链接，也不想在帖子中解释这个谜题。所以我只是指向了遵循相同规则的《倒计时》节目。同时，我已经修复了帖子，谢谢。 - Shawn

Answer 1

这个问题可以使用一个专门表示表达式的类来解决，而不是使用一个数组。然后你可以简单地枚举所有可能的树。结合我为类似任务编写的另一个答案以及一个展示如何生成所有二叉树的答案，得到以下结果：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class NumberPuzzleWithCats
{
    public static void main(String[] args)
    {
        List<Integer> numbers = Arrays.asList(10,7,8,3,7);
        solve(numbers);
    }

    private static void solve(List<Integer> numbers)
    {
        List<Node> nodes = new ArrayList<Node>();
        for (int i=0; i<numbers.size(); i++)
        {
            Integer number = numbers.get(i);
            nodes.add(new Node(number));
        }
        System.out.println(nodes);
        List<Node> all = create(nodes);
        System.out.println("Found "+all.size()+" combinations");


        for (Node node : all)
        {
            String s = node.toString();
            System.out.print(s);
            if (s.equals("((10*7)-(8*(3+7)))"))
            {
                System.out.println(" <--- There is is :)");
            }
            else
            {
                System.out.println();
            }
        }
    }

    private static List<Node> create(Node n0, Node n1)
    {
        List<Node> nodes = new ArrayList<Node>();
        nodes.add(new Node(n0, '+', n1));
        nodes.add(new Node(n0, '*', n1));
        nodes.add(new Node(n0, '-', n1));
        nodes.add(new Node(n0, '/', n1));
        nodes.add(new Node(n1, '+', n0));
        nodes.add(new Node(n1, '*', n0));
        nodes.add(new Node(n1, '-', n0));
        nodes.add(new Node(n1, '/', n0));
        return nodes;
    }

    private static List<Node> create(List<Node> nodes)
    {
        if (nodes.size() == 1)
        {
            return nodes;
        }
        if (nodes.size() == 2)
        {
            Node n0 = nodes.get(0);
            Node n1 = nodes.get(1);
            return create(n0, n1);
        }
        List<Node> nextNodes = new ArrayList<Node>();
        for (int i=1; i<nodes.size()-1; i++)
        {
            List<Node> s0 = create(nodes.subList(0, i));
            List<Node> s1 = create(nodes.subList(i, nodes.size()));
            for (Node n0 : s0)
            {
                for (Node n1 : s1)
                {
                    nextNodes.addAll(create(n0, n1));
                }
            }
        }
        return nextNodes;
    }

    static class Node
    {
        int value;
        Node left;
        Character op;
        Node right;

        Node(Node left, Character op, Node right)
        {
            this.left = left;
            this.op = op;
            this.right = right;
        }
        Node(Integer value)
        {
            this.value = value;
        }

        @Override
        public String toString()
        {
            if (op == null)
            {
                return String.valueOf(value);
            }
            return "("+left.toString()+op+right.toString()+")";
        }
    }
}

它将打印出所有的组合，包括你正在寻找的那一个：

[10, 7, 8, 3, 7]
Found 16384 combinations
(10+(7+(8+(3+7))))
(10*(7+(8+(3+7))))
...
((10*7)+(8*(3+7)))
((10*7)*(8*(3+7)))
((10*7)-(8*(3+7))) <--- There is is :)
((10*7)/(8*(3+7)))
((8*(3+7))+(10*7))
...
((7/3)-((8/7)/10))
((7/3)/((8/7)/10))

当然，通过比较字符串表示来检查是否找到了正确的解决方案是“非常实用的”，用这种方式陈述是可以的，但我认为这里真正重要的是生成的实际方法。 （希望这确实是您一直在寻找的内容-我无法查看您链接到的站点…）

- Marco13

---

谢谢，这正是我在寻找的。链接简单地解释了游戏规则。http://www.wikiwand.com/en/Countdown_(game_show)#/Numbers_round - Shawn