I have no idea on how to even start on this. Here is the assignment: Please help if you can. This assignment will give you practice with recursion, and more specifically, backtracking.
Cryptarithms are classic problems that date back about 70 years. In a puzzle magazine in the 20s, readers were asked to solve the following problem:
SEND + MORE ------ MONEY
Readers were supposed to replace each symbol with a digit from 0-9 (i.e., replace all the Ms with a single digit, replace all the Os with a different digit, and so on and so forth). There is only one unique solution to this particular problem (all other solutions do not provide a valid arithmetic expression):
9567 + 1085 ------ 10652
Your job in this assignment is to find all solutions to problems such as the ones above. You are to write a class called Cryptarithm. The constructor takes three parameters, three different strings, the first two being the operands and the third being the solution to the arithmetic equation (not the same as the solution to the cryptarithm).
Your class also needs three additional public methods. The first is getNumSolutions() which returns the number of distinct solutions as an int. The second is getSolutions(), which returns a String with all the solutions inside of it. The solutions should be of the form above (more on this in a bit), each solution separated by a new line. A third method is the toString(). The toString() method should return the original problem, a new line, the solutions, a new line, then the number of solutions possible afterward. See the sample output below to see how the format should be for each of these methods.
There are many ways to solve this problem, but you must do it recursively. Likewise, there are many ways to recursively solve this problem. It is suggested you do it through the use of backtracking. One way to do this is analogous to the eight queens problem we talked about in class. You should come up with a solution for one letter, and then try to recursively solve the remaining unsolved portion. Once you have finished with the recursive call down one path, change the value for the current letter when you come back up and try and travel down the recursive path again. Imagine that each letter represents a column of a chess board in the eight queens problem and each row represents one of the 9 digits.
For this assignment, you are provided a skeleton file as you were in the first couple of assignments. Inside the skeleton file, you will see three different methods. You do not have to use these methods, although they have been left there as an aide to you. Two of them relate to the printing of solutions. getFormattedEquation() will return to you the correct formatted solution, using the first parameter as the first operation, the second parameter as the second operand, and the third as the result. getCharacterRepeated() aides this method. getSymbolsSorted() will take three Strings and return a tight array with all of the letters sorted. For example, if you passed in each of the three Strings from the example above, the method would return the array ['D', 'E', 'M', 'N', 'O', 'R', 'S', 'Y'].
Make sure to use the Java API (especially for the String class, it will be handy) to come up with ideas for handing the letters. Integer.parseInt() will yet again be handy for being able to check if a solution is valid.
In the handouts section there is a sample test file. You'll see calls to the different methods out of order -- this means your methods should work no matter which is called first. You will also see problems with more than one solution or none at all. You should be able to handle any of the above. The output of the test driver is not all-inclusive, you should be sure to try and run some of your own tests. You can find many cryptarithm problems on the Internet -- just look on Google for more, if you so desire. The expected output of the test driver is listed below the code.
Turn in your code in the usual way. You must turn in a regular Java file as you have in the past, even if you are doing the extra credit. This means make sure your Cryptarithm class is up to speed (both in correctness and style), because the ones talked about below will not factor into your grade for this assignment.
Previous Topic
