24游戏/倒计时/数字游戏解算器，但答案中没有括号

Question

我已经在互联网上浏览了一整天，寻找一种现有的解决方案，可以从指定目标数字的数字和运算符的列表中创建一个等式。

我遇到了很多24游戏解算器，倒计时解算器等等，但它们都是围绕着允许在答案中使用括号的概念构建的。

例如，对于使用数字1 2 3 4 5 6的目标42，解决方案可以是：

6 * 5 = 30
4 * 3 = 12
30 + 12 = 42

注意算法如何记住子方程的结果，并在以后重用它来形成解(在本例中为30和12)，本质上是使用括号来形成解(6 * 5) + (4 * 3) = 42。

而我想要一个不使用括号的解决方案，它是从左到右求解的，例如6 - 1 + 5 * 4 + 2 = 42，如果我写出来，它将是：

6 - 1 = 5
5 + 5 = 10
10 * 4 = 40
40 + 2 = 42

我有一个大约55个数字(从2到12的随机数)、9个运算符(每个基本运算符的2个+1个随机运算符)和一个目标值(0到1000之间的随机数)的列表。我需要一个算法来检查我的目标值是否可解(如果不是，我们可以选择离实际值有多近)。每个数字和运算符只能使用一次，这意味着您最多可以使用10个数字来获取目标值。

我发现了一种暴力算法，它可以很容易地调整来做我想做的事情(How to design an algorithm to calculate countdown style maths number puzzle)，而且它是有效的，但我希望找到一种可以生成更复杂的“解决方案”的东西，就像在这个页面上一样：http://incoherency.co.uk/countdown/

Answer 1

我写了你在文章末尾提到的求解器，我提前道歉，代码可读性不是很好。

在本质上，这类问题的任何解算器的代码都是简单的深度优先搜索，这意味着您已经在工作了。

请注意，如果您使用“不使用括号的解决方案，这是从左到右解决”，那么就有一些输入集是不可解的。例如，11,11,11,11,11,11，目标为144。解是((11/11)+11)*((11/11)+11)。我的求解器通过将括号分成不同的行，使人们更容易理解这一点，但它仍然有效地使用了括号，而不是从左到右求值。

“使用括号”的方法是将操作应用于输入，并将结果放回输入包中，而不是将操作应用于输入之一和累加器。例如，如果您的输入包是1,2,3, 4，5,6，并且您决定将3和4相乘，则包将变成1,2,12,5,6。这样，当您递归时，该步骤可以使用上一步的结果。为输出做好准备只是将操作的历史记录连同每个数字一起存储在包中的情况。

我想你所指的更“复杂”的解决方案就是我的javascript求解器中使用的简单性启发式。求解器的工作方式是对整个搜索空间进行深度优先搜索，然后选择“最佳”的解决方案，而不是只使用最少的步骤。

如果一个解决方案更接近目标(请注意，求解器中的任何状态都是候选解决方案，只是大多数状态比以前的最佳候选解决方案离目标更远)，或者如果它与目标的距离相等，并且具有较低的启发式分数，则该解决方案被认为比以前的解决方案“更好”(即将其替换为“答案”解决方案)。

启发式得分是“中间值”(即"=“符号右侧的值)的总和，去掉了尾随的0。例如，如果中间值是1、4、10、150，则启发式得分为1+4+1+15: 10和150只计算1和15，因为它们以零结束。这样做是因为人类发现更容易处理可被10整除的数字，因此解决方案看起来“更简单”。

另一个可以被认为是“复杂”的部分是一些行连接在一起的方式。这只是将"5 +3= 8“和"8 +2= 10”的结果合并为"5 +3+2= 10“。这样做的代码绝对是可怕的，但如果你感兴趣的话，它都在https://github.com/jes/cntdn/blob/master/js/cntdn.js的Javascript中-要点是在找到以数组形式存储的解决方案(以及每个数字是如何构成的信息)后，会发生一系列的后处理。大致如下：

• 将从DFS生成的“解决方案列表”转换为(基本的、基于嵌套数组的)表达式树-这是为了处理多参数情况(即"5 +3+ 2“不是2个加法操作，它只是一个具有3次加法(3 arguments)
• convert )表达式树到步骤数组的添加，包括对参数进行排序以便它们被更一致地呈现
• 将步骤数组转换为字符串表示以显示给用户，包括对结果与目标数的距离的解释，如果不等于

很抱歉说得太长了。希望其中一些是有用的。

詹姆斯

编辑:如果你对倒计时解算器感兴趣，你可能想看看我的字母解算器，因为它比数字解算器优雅得多。这是https://github.com/jes/cntdn/blob/master/js/cntdn.js中最重要的两个函数--对字母字符串调用solve_letters()，以及为每个匹配的单词调用一个函数。此解算器的工作方式是遍历表示字典的trie (由https://github.com/jes/cntdn/blob/master/js/mk-js-dict生成)，并在每个端节点调用回调。

Answer 2

我使用java中的递归来进行数组组合。其主要思想是使用DFS来获得数组组合和操作组合。

我使用布尔数组来存储访问的位置，这样可以避免重复使用相同的元素。temp StringBuilder用来存储当前的方程式，如果对应的结果等于目标，我会将方程式放入结果中。选择下一个数组元素时，不要忘记将临时数组和已访问数组恢复到原始状态。

此算法会产生一些重复的答案，因此需要在以后进行优化。

public static void main(String[] args) {
    List<StringBuilder> res = new ArrayList<StringBuilder>();
    int[] arr = {1,2,3,4,5,6};
    int target = 42;
    for(int i = 0; i < arr.length; i ++){
        boolean[] visited = new boolean[arr.length];
        visited[i] = true;
        StringBuilder sb = new StringBuilder();
        sb.append(arr[i]);
        findMatch(res, sb, arr, visited, arr[i], "+-*/", target);
    }

    for(StringBuilder sb : res){
        System.out.println(sb.toString());
    }
}

public static void findMatch(List<StringBuilder> res, StringBuilder temp, int[] nums, boolean[] visited, int current, String operations, int target){
    if(current == target){
        res.add(new StringBuilder(temp));
    }

    for(int i = 0; i < nums.length; i ++){
        if(visited[i]) continue;
        for(char c : operations.toCharArray()){
            visited[i] = true;
            temp.append(c).append(nums[i]);
            if(c == '+'){
                findMatch(res, temp, nums, visited, current + nums[i], operations, target);
            }else if(c == '-'){
                findMatch(res, temp, nums, visited, current - nums[i], operations, target);
            }else if(c == '*'){
                findMatch(res, temp, nums, visited, current * nums[i], operations, target);
            }else if(c == '/'){
                findMatch(res, temp, nums, visited, current / nums[i], operations, target);
            }
            temp.delete(temp.length() - 2, temp.length());
            visited[i] = false;
        }
    }
}