24点/倒计时/数字游戏解算器，但没有答案的括号(24 Game/Countdown/Number

我一直在浏览互联网整天现有的解决方案来进行数字和运算符列表的创建方程式指定的目标数。

我碰到了很多的24点求解，求解倒计时和一致好评，但它们都围绕打造允许的答案括号的概念。

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

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个运营商和目标值（每个基本操作+ 1随机算的2）（0到1000之间的随机数）的列表。我需要一个算法来检查我的目标值是否是可解（和可选的，如果不是，如何接近我们可以得到实际值）。每个数字和运算符只能使用一次，这意味着将有最多10个号码，你可以用它来获得目标值。

我发现了一个蛮力算法可以很容易地调整到做我想做的（如何设计一个算法，计算出倒计时式的数学数字拼图），以及该作品，但我希望能找到一些东西，产生更复杂的“解决方案”像此页上： 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” 的结果。要做到这一点的代码是绝对可怕，但如果你有兴趣这一切都在JavaScript的在https://github.com/jes/cntdn/blob/master/js/cntdn.js -要点是发现后其被存储在阵列的形式（与信息有关的每个数字是如何制造）溶液一堆后处理的发生。大致：

转换从DFS生成到一个（基于嵌套阵列简陋，）表达式树中的“解决方案列表” - 这是应对多参数的情况下（即，“5 + 3 + 2”不是2次加法运算，它的只是一个补充，它3个参数）
表达式树转换的步骤的阵列，包括让他们呈现更一致的排序参数
的步骤的数组转换成一个字符串表示以显示给用户，包括一个解释如何远离目标数的结果是，如果它不等于

道歉的该长度。希望有的却是使用的。

詹姆士

编辑：如果你有兴趣在一般倒计时求解器，你可能想看看我的信解算器，因为它是比数字远一个更优雅。这是顶部的两个功能在https://github.com/jes/cntdn/blob/master/js/cntdn.js -使用呼叫solve_letters（）的一串字母和一个函数来获取呼吁每一个匹配的单词。该解算器的工作方式是遍历表示所述字典（由所产生的线索https://github.com/jes/cntdn/blob/master/js/mk-js-dict ），并调用在每一个端节点的回调。

Answer 2:

我用的是递归在java做的阵列组合。其主要思想是在运用DFS拿到阵列组合和操作组合。

我用一个布尔数组来存储所述被访问位置，可避免相同的元素被再次使用。临时的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;
        }
    }
}

文章来源: 24 Game/Countdown/Number Game solver, but without parentheses in the answer