Recursive 24

Introduction

The card game "24" is widely used in elementary schools to help students learn arithmetic facts and problem solving skills. If you aren't familiar with the game, take a few minutes to read over the tutorial page and watch the instructional video.

Making students play this game is cruel. Why should they be forced to struggle with these cards when a computer could find solutions almost instantly?

Your goal for this project is prevent untold suffering among elementary school students by programming a recursive 24 solver.

Requirements

You must complete the implementation of the solve method in TwentyFourSolver.java so that it conforms to the provided JavaDoc comments. We are providing a finished version of an application named TwentyFour.java that makes it possible to access your solver from the command-line. The first argument to the application will represent the target value and the remaining arguments are numbers that are used to construct the solution. Your application should work correctly even if the target value is not 24. It should also work correctly regardless of how many numbers are provided.

Here are some examples of what it should look like to interact with the application once the solver is completed.

• Here is a typical case:

  $ java TwentyFour 24 3 5 6 1 
  6 * 3 = 18
  18 + 1 = 19
  19 + 5 = 24
  $
  

• Here is a case with a non-24 target value:

  $ java TwentyFour 17 3 5 6 1 
  3 - 1 = 2
  2 * 6 = 12
  12 + 5 = 17
  

• More than four numbers on the card:

  $ java TwentyFour 17 3 5 6 7 1
  1 + 6 = 7
  7 - 5 = 2
  2 * 7 = 14
  14 + 3 = 17
  

• A card with only one number. (Nothing is printed because no operations are required.)

  $ java TwentyFour 17 17
  $
  

• No possible solution:

  $ java TwentyFour 24 3 3 4 10
  No solution exists!
  $
  

The output of your application should exactly match the formatting in the examples above. Note that many 24 cards have multiple solutions. Where multiple solutions exist, any correct solution is acceptable.

Designing an Algorithm

It will be your responsibility to develop a correct recursive algorithm. The example below is designed to get you thinking in the right direction.

Example Solution Steps

We can think of the 24 problem as filling in the boxes in a diagram like the following:

The goal is to fill each of the green boxes with one of the four numbers from the card, and each of the blue boxes with an arithmetic operator. In this case, the following solution would work:

There are many possible strategies for solving this problem. Let's consider the approach of working backwards from 24. Assuming we are working with the numbers 2, 2, 7, and 10, we might first try filling the last two boxes with "×" and "2". These choices may not be correct, but we can try them out to see where they take us:

Once we've decided to end with "× 2", only one possible value will work for C: it must be 12. This leaves us in this position:

We can continue to work backwards by placing "+" and "7" in the second line:

If this is going to work, then "B" must be equal to 5:

Continuing to work backwards, let's try placing "÷" and "10":

For this to work A would need to be 50, but all we have left for the final box is 2. We must have made a mistake somewhere earlier in the process. Let's back up and try "÷" and "2" instead:

At this point, we know that A must be 10, and our last number is 10. Success!

Submission and Grading

You must submit your completed code through Web-CAT by the project deadline. The scoring for this assignment will be broken into two components:

• A: Correctly determining which problems have a solution: 75%
• B: Correct printing of results: 25%

You can only receive credit for part B if your code passes all of the submission tests for part A.

Implementation Tips

You may want to warm up for this assignment by completing the CodingBat exercises groupSum and groupSum6. These problems are different from 24, but they may get you thinking along the right lines.

Here is a page of solutions that may be useful for constructing tests.

One odd aspect of this assignment is that we are working with integer values, but storing them as doubles. This is necessary because integer arithmetic in Java would lead us to invalid solutions: we don't want a solution that includes the step "5 / 2 = 2".

Determining if a Double Contains An Integer

There are several possible approaches to this problem. The simplest solution is to use the mod operator:

if ((num % 1) == 0)
{
   System.out.println("It's an int!");
}

If there is no remainder when we divide by 1, then we know the number must have been an integer.

Printing Doubles as Integers

Even if a double contains an integer value, by default it will be printed with a trailing ".0". This code:

double a = 3;
System.out.println(a);

Will print "3.0".

Again, there are multiple ways we could address this problem. One possibility is to cast to an int before printing. Other possibilities include using System.out.printf or String.format.

Going Further

The approach suggested in Section 3 is only guaranteed to find solutions that satisfy the following assumptions:

1. A number from the card must always be used as the second operand.
2. Each arithmetic operation must include at least one number from the card.

Assumption 1 would disallow a solution like this:

Assumption 2 would disallow a solution like this:

Since the rules of the game allow for either of these solutions to be used, our recursive solver will miss some valid solutions.

Dropping assumption 1 wouldn't cause much difficulty for our "working backwards from 24" strategy: we could just try both possible operand orderings as we work our way toward a solution.

Unfortunately, dropping assumption 2 makes the problem significantly more difficult. The strategy of working backwards from 24 by picking numbers from the card doesn't work if we need to perform operations that don't use any numbers from the card.

For the purpose of this assignment, your code is only required to recognize solutions that satisfy assumptions 1 and 2 above. If you want to take the assignment further, you are welcome to develop a more general solver.

---