Using the numbers 1, 3, 4 and 6, create an algebraic expression that equals 24. All four numbers must be used and each number may only be used once. Those four numbers are the only numbers permitted in the expression. The expression is restricted to using addition, subtraction, multiplication and division. A particular mathematical operator maybe applied more than once. The expression may contain parentheses to define the order of operations.
Here are some valid expressions that do not equal 24:
((6 * 4) - 3) - 1 (3 + 4) * (1 + 6) 4 * (1 + (6 / 3))
Here are some invalid expressions:
((6 * 4) + (-3)) + 1 34 * (1 + 6) 3.4 * (1 + 6) 4 * (1 + (6 ^ 3)) 6 * (3 + 1) 1 + 4 + (6 * 4)
The first expression used the negation unary operator. The symbol for negation is the same symbol used in subtraction, but it’s an entirely different mathematical function. The second expression attempted to form 34 by putting the numbers 3 and 4 adjacent to each other. The third expression attempted to form 3.4 by introducing a decimal point between 3 and 4. Numbers can only be combined using the four operators stated in the problem. The fourth expression used 63. Exponents are not permitted even though it is possible to express them without an explicit operator like ^. The fifth expression does not include 4. The sixth expression includes 4 twice.
1, 3, 4 and 6 are base-10, real numbers. The expression must evaluate to 24 in base-10. During evaluation, each sub-expression evaluates to a real number. There is no implicit conversion to integers via the floor, ceiling or round functions at any stage during evaluation.
A simple solution exists. The answer equals exactly 24 and it doesn’t apply some sort of trick or loophole that breaks the rules explained above. But, I bet you can’t find it.
As far as I can determine, the only way to find the solution is via a brute force search. Is it feasible to do that by hand? How large is the problem space? How many expressions exists with the constraints specified in the problem?
The number of possible expressions can be determined by multiplying together the following 3 values:
The number of permutations of 1, 3, 4 and 6 is 4! = 24. That follows from the fact that we have four choices for the first number in the expression. Once that number is in place, we can select among one of the three remaining numbers for the second number in the expression. And so on: 4 * 3 * 2 * 1 = 24.
Next, we need to compute the number of operator permutations where these permutations may contain repeats. But, how many operators are in the expression? Does it vary? Any expression containing parentheses can be expressed in Reverse Polish notation (RPN, a.k.a. Postfix notation) using no parentheses. An RPN expression is easy to evaluate using a stack. The expression is evaluated from left-to-right. When a number is encountered, it is pushed onto the stack and the stack size increases by 1. When one of the binary operators above is encountered, 2 values are popped from the stack, the operator is applied and the result is pushed back onto the stack. In that case, the stack size decreases by 1. The final result is left on the stack. Since the expression contains 4 numbers and after evaluation the stack size is 1, the expression must always contain exactly 3 operators, each of which reduces the stack size by 1.
We have four choices for each of the three operators in the expression. 4*4*4 = 43 = 64.
Finally, how many expression forms are there? Meaning, how many RPN expressions exists containing 4 numbers and 3 binary operators? Let N denote a number and B a binary operator. Consider this RPN expression:
N N N N
We need to insert 3 B’s. Let’s number the insertion points:
1 N 2 N 3 N 4 N 5
A binary operator consumes the top 2 values on the stack. Hence, we can’t put a B at point 1 or 2 because it needs to follow at least 2 N’s. If we insert a B at point 3, we can’t put a second B there because the first reduced the stack size to 1. As described above, the stack size at any point is the number of N’s minus the number of B’s. Analyzing the remaining possibilities yields these 5 expressions:
N N B N B N B N N B N N B B N N N B B N B N N N B N B B N N N N B B B
The infix version of those expressions is:
((N B N) B N) B N (N B N) B (N B N) (N B (N B N)) B N N B ((N B N) B N) N B (N B (N B N))
If we plug in the permutations of the four numbers and the permutations (with repeats) of the operators, we get 24 * 64 * 5 = 7680 expressions. That’s way too many to do by hand. Instead, I used a simple C# program.
First, I manually listed out the permutations of the 4 numbers:
1: private double[,] permutations = {
2: { 1, 3, 4, 6, },
3: { 1, 3, 6, 4, },
4: { 1, 4, 3, 6, },
5: { 1, 4, 6, 3, },
6: { 1, 6, 3, 4, },
7: { 1, 6, 4, 3, },
8: { 3, 1, 4, 6, },
9: { 3, 1, 6, 4, },
10: { 3, 4, 1, 6, },
11: { 3, 4, 6, 1, },
12: { 3, 6, 1, 4, },
13: { 3, 6, 4, 1, },
14: { 4, 1, 3, 6, },
15: { 4, 1, 6, 3, },
16: { 4, 3, 1, 6, },
17: { 4, 3, 6, 1, },
18: { 4, 6, 1, 3, },
19: { 4, 6, 3, 1, },
20: { 6, 1, 3, 4, },
21: { 6, 1, 4, 3, },
22: { 6, 3, 1, 4, },
23: { 6, 3, 4, 1, },
24: { 6, 4, 1, 3, },
25: { 6, 4, 3, 1, },
26: };
Next, I created an array of the 4 operators and I defined a function that can apply them:
1: private char[] operators = { '+', '-', '*', '/' };
2:
3: private double F(double a, char op, double b) {
4: switch (op) {
5: case '+':
6: return a + b;
7: case '-':
8: return a - b;
9: case '*':
10: return a * b;
11: default:
12: return a / b;
13: }
14: }
Finally, I created a function that contains 4 nested loops. The outer 3 loops iterate over the operator permutations. The inner-most loop iterates over the number permutation array. The body of that loop evaluates the 5 expression forms and tests for equality against 24.
1: public void Solve() {
2: foreach (char p in operators) {
3: foreach (char q in operators) {
4: foreach (char r in operators) {
5: for (int i = 0; i < 24; i++) {
6: double a = permutations[i, 0];
7: double b = permutations[i, 1];
8: double c = permutations[i, 2];
9: double d = permutations[i, 3];
10:
11: if (F(F(a, p, b), r, F(c, q, d)) == 24) {
12: Console.WriteLine("({0} {1} {2}) {3} ({4} {5} {6}) = 24",
13: a, p, b, r, c, q, d);
14: return;
15: }
16: if (F(F(F(a, p, b), q, c), r, d) == 24) {
17: Console.WriteLine("(({0} {1} {2}) {3} {4}) {5} {6} == 24",
18: a, p, b, r, c, q, d);
19: return;
20: }
21: if (F(F(a, p, F(b, q, c)), r, d) == 24) {
22: Console.WriteLine("({0} {1} ({2} {3} {4})) {5} {6} == 24",
23: a, p, b, r, c, q, d);
24: return;
25: }
26: if (F(a, p, F(b, q, F(c, r, d))) == 24) {
27: Console.WriteLine("{0} {1} ({2} {3} ({4} {5} {6})) == 24",
28: a, p, b, r, c, q, d);
29: return;
30: }
31: if (F(a, p, F(F(b, q, c), r, d)) == 24) {
32: Console.WriteLine("{0} {1} (({2} {3} {4}) {5} {6}) == 24",
33: a, p, b, r, c, q, d);
34: return;
35: }
36: }
37: }
38: }
39: }
40: }
One of those if-statements discovers and prints the answer. I omit the answer from this article just incase you’re crazy enough to attempt to solve this by hand.
Why stop there? What about a computational solution to a generalized version of the problem? Consider expressions containing N numbers, N-1 binary operators and any number of unary operators. The goal is to discover an expression that equals some specified target value.
Unary operators, such square-root and negation, are kind of a problem. In an RPN expression, a unary operator pops a single value off the stack, it applies its associated unary function and it pushes the result back onto the stack. Unary operators don’t alter the stack size; they can be applied indefinitely. To limit the search space, we’re forced to specify the number of unary operators that can be in the expression.
First, let’s consider ways of generating permutations. Generating permutations of the operators is easier than generating permutations of the numbers because repeats are allowed. It can be done with a simple recursive function:
1: public void PrintPermutations(char[] operators) {
2: PrintPermutations(operators, 0, new char[operators.Length]);
3: }
4:
5: private void PrintPermutations(char[] operators, int index, char[] permutation) {
6: if (index == permutation.Length) {
7: PrintArray(permutation);
8: } else {
9: for (int i = 0; i < operators.Length; i++) {
10: permutation[index] = operators[i];
11: PrintPermutations(operators, index + 1, permutation);
12: }
13: }
14: }
The bootstrap function on line 1 accepts the array of operators. It creates a second array on line 2 to store an individual permutation and it makes a call to the recursive function on line 5. The recursive function acts like the set of nested loops in the prior example. The index variable is an index into the permutation array, but it's essentially the nesting level. The loop on line 9 plugs every possible operator into that position of the array and then it recursively calls the function again to do the same to the rest of the array. Note that index + 1 is passed in the call. If the index equals the length of the array, then it’s full and it’s printed. The output looks like this:
+ + + + + + + - + + + * + + + / + + - + + + - - + + - * + + - / + + * + + + * - + + * * + + * / + + / + + + / - + + / * + + / / + - + + + - + - + - + * + - + / ... / / * * / / * / / / / + / / / - / / / * / / / /
Permuting the numbers can be done using a similar technique; however, additional logic is required to prevent repeats:
1: public void PrintPermutations(double[] numbers) {
2: Array.Sort(numbers);
3: bool[] available = new bool[numbers.Length];
4: for (int i = 0; i < available.Length; i++) {
5: available[i] = true;
6: }
7: PrintPermutations(numbers, 0, new double[numbers.Length], available);
8: }
9:
10: private void PrintPermutations(double[] numbers, int index,
11: double[] permutation, bool[] available) {
12: if (index == numbers.Length) {
13: PrintArray(permutation);
14: } else {
15: double lastNumber = Double.NaN;
16: for (int i = 0; i < available.Length; i++) {
17: if (available[i] && numbers[i] != lastNumber) {
18: available[i] = false;
19: permutation[index] = lastNumber = numbers[i];
20: PrintPermutations(numbers, index + 1, permutation, available);
21: available[i] = true;
22: }
23: }
24: }
25: }
The bootstrap function on line 1 accepts the numbers to permute. That array may contain duplicate numbers. To make it easier to discover duplicates, the array is sorted on line 2. On line 3, an array of boolean flags is allocated to the same length as the numbers array. Lines 4—6 initialize the elements to true. As each number is placed into the permutation, the code will note that it can’t be used again by setting the corresponding index of the available array to false. The arrays are passed to the recursive function on line 10. The loop on lines 16—24 scans the available array for the next unused number. Since the sorted numbers array may contain duplicates, before the loop plugs an available number into the permutation array, it checks that it doesn’t match the last number it plugged into the same position. After the recursive call on line 20, it renders the number available again.
My generalized solution uses those recursive techniques of producing permutations as part of building RPN expressions. An RPN expression is a list of numbers and operators. I abstracted the elements of the list into this interface:
1: public interface IElement {
2: void Evaluate(Stack<double> stack);
3: void Print(Stack<string> stack);
4: }
Each element is able to evaluate itself and to print itself. For evaluation, it pops 0, 1 or 2 values off the stack, it applies a function to those values and it pushes a new value back onto the stack. It prints itself in infix notation also by pulling values off a stack and pushing on a new one.
Here’s the implementation of the number element:
1: public class Number : IElement {
2:
3: public double value;
4:
5: public Number(double value) {
6: this.value = value;
7: }
8:
9: public void Evaluate(Stack<double> stack) {
10: stack.Push(value);
11: }
12:
13: public void Print(Stack<string> stack) {
14: stack.Push(value.ToString());
15: }
16: }
Number is evaluated and printed by simply pushing its contained value onto the stack.
The binary operators are modeled as follows:
1: public delegate double BinaryFunction(double a, double b);
2:
3: public class BinaryOperator : IElement {
4:
5: private BinaryFunction binaryFunction;
6: private string name;
7:
8: public BinaryOperator(BinaryFunction binaryFunction, string name) {
9: this.binaryFunction = binaryFunction;
10: this.name = name;
11: }
12:
13: public void Evaluate(Stack<double> stack) {
14: double b = stack.Pop();
15: double a = stack.Pop();
16: stack.Push(binaryFunction(a, b));
17: }
18:
19: public void Print(Stack<string> stack) {
20: string b = stack.Pop();
21: string a = stack.Pop();
22: stack.Push(string.Format("({0} {1} {2})", a, name, b));
23: }
24: }
The constructor accepts a binary function, defined by the delegate, and a name. The Evaluate() and Print() functions are straightforward. They pop 2 values off the stack, they process them and they push a new value back onto the stack.
The same idea is used for unary operators:
1: public class UnaryOperator : IElement {
2:
3: private UnaryFunction unaryFunction;
4: private string name;
5: private bool before;
6:
7: public UnaryOperator(
8: UnaryFunction unaryFunction, string name, bool before) {
9: this.unaryFunction = unaryFunction;
10: this.name = name;
11: this.before = before;
12: }
13:
14: public void Evaluate(Stack<double> stack) {
15: stack.Push(unaryFunction(stack.Pop()));
16: }
17:
18: public void Print(Stack<string> stack) {
19: stack.Push(string.Format(
20: before ? "{0}({1})" : "({1}){0}", name, stack.Pop()));
21: }
22: }
Unary operators may be printed prefix or postfix. For instance, negation is denoted by a minus-sign to the left of the value. Factorial, on the other hand, is denoted by an exclamation mark to the right of the value. The before parameter passed into the constructor enables Print() to show the operator before or after the value.
A list of IElement objects represents an RPN expression in deferred execution form. To evaluate and to print the expression, the following methods are used:
1: private double EvalutateExpression(List<IElement> elements,
2: Stack<double> stack) {
3: foreach (IElement element in elements) {
4: element.Evaluate(stack);
5: }
6: return stack.Pop();
7: }
8:
9: private void PrintExpression(List<IElement> elements, double target,
10: Stack<string> stack) {
11: foreach (IElement element in elements) {
12: element.Print(stack);
13: }
14: string expression = stack.Pop();
15: Console.WriteLine("{0} = {1}", expression, target);
16: }
The stack passed into the methods starts out empty. The methods iterate over the list using the stack to hold intermediate values. The final value in the stack is returned.
Finally, to find an expression that equals a specified target value, a large recursive method is used. I’ll break it down for you:
1: private void Solve(
2: Number[] numbers,
3: UnaryOperator[] unaryOperators,
4: BinaryOperator[] binaryOperators,
5: double target,
6: List<IElement> elements,
7: bool[] numbersAvailable,
8: bool[] unaryOperatorsAvailable,
9: int stackSize,
10: Stack<double> numberStack,
11: Stack<string> stringStack) {
The numbers, unaryOperators, binaryOperators and target are the parameters that specify the problem. The elements list is the RPN expression under construction. The numbersAvailable boolean array is used as shown in a prior example for computing the permutations of the numbers. Since unary operators can be applied indefinitely, this recursive function prevents duplicates using the unaryOperatorsAvailable array. If you want the expression to contain a specific unary operator a certain number of times, list the operator that number of times within the unaryOperators array. The stackSize represents the size of the stack if the partially formed RPN expression in elements were to be evaluated. Finally, numberStack and stringStack are used for evaluating and printing the RPN expression once it is fully formed.
The method expands the partial RPN expression by plugging in every possible number:
1: bool remainingNumbers = false;
2: double lastNumber = Double.NaN;
3: for (int i = 0; i < numbersAvailable.Length; i++) {
4: if (numbersAvailable[i] && numbers[i].value != lastNumber) {
5: remainingNumbers = true;
6: elements.Add(numbers[i]);
7: numbersAvailable[i] = false;
8: Solve(numbers, unaryOperators, binaryOperators, target, elements,
9: numbersAvailable, unaryOperatorsAvailable, stackSize + 1,
10: numberStack, stringStack);
11: numbersAvailable[i] = true;
12: elements.RemoveAt(elements.Count - 1);
13: }
14: }
The loop is analogous to the loop used for computing the number permutations seen in a prior example. Each iteration checks if the number is available and if the number was already plugged-in in a previous iteration (the numbers array is pre-sorted). If a number is available, it is appended to the RPN expression, the recursive method is called again and finally the number is removed from the expression. The remainingNumbers flag is set if it discovered an available number. Note that appending a number to the expression will increase the stack size by 1. See the value passed into the recursive call.
Next, the method does virtually the same thing for the unary functions. The only difference being that it also has to check if the stack size is at least 1. When the recursive call is made, the stackSize variable is left the same.
1: if (stackSize >= 1) {
2: for (int i = 0; i < unaryOperatorsAvailable.Length; i++) {
3: if (unaryOperatorsAvailable[i]) {
4: elements.Add(unaryOperators[i]);
5: unaryOperatorsAvailable[i] = false;
6: Solve(numbers, unaryOperators, binaryOperators, target, elements,
7: numbersAvailable, unaryOperatorsAvailable, stackSize,
8: numberStack, stringStack);
9: unaryOperatorsAvailable[i] = true;
10: elements.RemoveAt(elements.Count - 1);
11: }
12: }
13: }
Then, the method plugs-in every possible binary operator. This code is simpler because it doesn’t have to check for duplicates:
1: if (stackSize >= 2) {
2: for (int i = 0; i < binaryOperators.Length; i++) {
3: elements.Add(binaryOperators[i]);
4: Solve(numbers, unaryOperators, binaryOperators, target, elements,
5: numbersAvailable, unaryOperatorsAvailable, stackSize - 1,
6: numberStack, stringStack);
7: elements.RemoveAt(elements.Count - 1);
8: }
9: }
Finally, here’s the remainder of the recursive method:
1: if (stackSize == 1 && !remainingNumbers) {
2: if (target == EvalutateExpression(elements, numberStack)) {
3: PrintExpression(elements, target, stringStack);
4: }
5: }
6: }
It checks if there is only 1 element in the stack and that it ran out of numbers to append to the RPN expression. If so, it evaluates the expression and compares the result to the target. If it’s expression that we’re looking for, it gets printed.
Here’s the bootstrap method that calls the recursive function:
1: public void Solve(double[] numbers, UnaryOperator[] unaryOperators,
2: BinaryOperator[] binaryOperators, double target) {
3: Array.Sort(numbers);
4: Number[] nums = new Number[numbers.Length];
5: for (int i = 0; i < numbers.Length; i++) {
6: nums[i] = new Number(numbers[i]);
7: }
8: List<IElement> elements = new List<IElement>();
9: bool[] numbersAvailable = new bool[numbers.Length];
10: for (int i = 0; i < numbersAvailable.Length; i++) {
11: numbersAvailable[i] = true;
12: }
13: bool[] unaryOperatorsAvailable = new bool[unaryOperators.Length];
14: for (int i = 0; i < unaryOperatorsAvailable.Length; i++) {
15: unaryOperatorsAvailable[i] = true;
16: }
17: Stack<double> numberStack = new Stack<double>();
18: Stack<string> stringStack = new Stack<string>();
19: Solve(nums, unaryOperators, binaryOperators, target, elements,
20: numbersAvailable, unaryOperatorsAvailable, 0, numberStack,
21: stringStack);
22: }
It’s pretty straightforward. Note that numberStack and stringStack are allocated here and they are only used for evaluating and printing fully formed RPN expressions.
To use the bootstrap method for solving The 24 Puzzle, the following call is made:
1: public static void Solve24Puzzle() {
2: Example4 example4 = new Example4();
3: example4.Solve(
4: new double[] { 1, 3, 4, 6 },
5: new UnaryOperator[0],
6: new BinaryOperator[] {
7: new BinaryOperator((a, b) => a + b, "+"),
8: new BinaryOperator((a, b) => a - b, "-"),
9: new BinaryOperator((a, b) => a * b, "*"),
10: new BinaryOperator((a, b) => a / b, "/")
11: },
12: 24);
13: }
How many integers can you generate using only four 4’s and any set of functions? The recursive method used in The 24 Puzzle solution can be slightly modified to solve The Four 4’s puzzle. Instead of hunting for a target value, all expressions that evaluate to an integer are stored in a SortedDictionary<int, List<IElement>>. To make it more interesting, only the shortest expressions are kept. Here’s the modified segment of code:
1: if (stackSize == 1 && !remainingNumbers) {
2: double value = EvalutateExpression(elements, numberStack);
3: int floored = (int)Math.Floor(value);
4: if (value == floored) {
5: if (expressions.ContainsKey(floored)) {
6: if (elements.Count < expressions[floored].Count) {
7: expressions[floored] = new List<IElement>(elements);
8: }
9: } else {
10: expressions[floored] = new List<IElement>(elements);
11: }
12: }
13: }
For binary operators, I’ll use addition, subtraction, multiplication, division and exponentiation. For unary operators I’ll use negation, square-root and factorial. However, to reduce the computation time, I’ll request that each unary operator be used at most once. If you want to use a particular unary operator more than once, simply add it to the UnaryOperator array as many times as desired.
1: public static void SolveFour4sPuzzle() {
2: Example5 example5 = new Example5();
3: UnaryOperator negate = new UnaryOperator(a => -a, "-", true);
4: UnaryOperator squareRoot
5: = new UnaryOperator(a => Math.Sqrt(a), "sqrt", true);
6: UnaryOperator factorial = new UnaryOperator(a => {
7: if (a == Math.Floor(a) && a >= 0 && a <= 12) {
8: return factorials[(int)a];
9: } else {
10: return Double.NaN;
11: }
12: }, "!", false);
13: example5.FindAll(
14: new double[] { 4, 4, 4, 4 },
15: new UnaryOperator[] { negate, squareRoot, factorial },
16: new BinaryOperator[] {
17: new BinaryOperator((a, b) => a + b, "+"),
18: new BinaryOperator((a, b) => a - b, "-"),
19: new BinaryOperator((a, b) => a * b, "*"),
20: new BinaryOperator((a, b) => a / b, "/"),
21: new BinaryOperator((a, b) => Math.Pow(a, b), "^")
22: });
23: }
For factorial, I defined an unsigned integer array for 0! to 12!. It can only be applied to integer intermediate values. The if-statement returns NaN if it can’t evaluate the input value. Consequentially, the entire RPN expression will equal NaN in that case.
Here’s a sample of the output:
0 = (4 + (4 - (4 + 4))) 1 = (4 / (4 + (4 - 4))) 2 = (4 * (4 / (4 + 4))) 3 = (4 - (4 ^ (4 - 4))) 4 = (4 + (4 * (4 - 4))) 5 = (4 + (4 ^ (4 - 4))) 6 = (4 + ((4 + 4) / 4)) 7 = (4 + (4 - (4 / 4))) 8 = (4 - (4 - (4 + 4))) 9 = (4 + (4 + (4 / 4))) 10 = (4 + (4 + (4 - sqrt(4)))) 11 = (4 + ((4 + (4)!) / 4)) 12 = (4 * (4 - (4 / 4))) 13 = ((4 + (sqrt(4) * (4)!)) / 4) 14 = (4 + (4 + (4 + sqrt(4)))) 15 = ((4 * 4) - (4 / 4)) 16 = (4 + (4 + (4 + 4))) 17 = ((4 * 4) + (4 / 4)) 18 = (4 * (4 + (sqrt(4) / 4))) 19 = ((4)! - (4 + (4 / 4))) 20 = (4 * (4 + (4 / 4))) 21 = ((4 / 4) - (4 - (4)!)) 22 = (4 + ((4 * 4) + sqrt(4))) 23 = (((4 * (4)!) - 4) / 4) 24 = (4 + (4 + (4 * 4))) 25 = ((4 + (4 * (4)!)) / 4) 26 = (((4 + 4) / 4) + (4)!) 27 = (4 - ((4 / 4) - (4)!)) 28 = ((4 * (4 + 4)) - 4) 29 = (4 + ((4 / 4) + (4)!)) 30 = ((4 * (4 + 4)) - sqrt(4))
This article, along with any associated source code and files, is licensed under The GNU Lesser General Public License.
Download the source here.
Copyright © 2008 Michael Birken
Updated: 2008.08.02