CodeStepByStep

Write a recursive function named cryptaSolver that uses backtracking to solve Cryptarithm puzzles as described on this page. In a Cryptarithm puzzle, an "addition problem" is posed between two words that "add up" to produce a third word as their sum. For example, consider the puzzle below at left, along with one correct solution to the puzzle at right:

   LOVE                     5970
 + HATE         ==>       + 4260
  PEACE                    10230

 puzzle                 solution

The idea is that the letters are each stand-ins for individual digit values from 0-9 inclusive. The goal of the puzzle is to see if there is a mapping of letters to numbers that produces a correct mathematical equation where the sum of the first two operands equals the third value. For example, if the letter L is replaced by 5, and O by 9, and V by 7, and so on, you can produce the equation shown above at right, which is a correct solution because 5970 + 4260 does equal 10230.

When substituting letters for numbers, all occurrences of a given letter must map to the same integer value. For example, in our example above, the E in LOVE must become the same integer value as the E in HATE and the two Es in PEACE. No two letters can substitute for the same digit; if the letter H becomes 4, no other letter can also become 4 in that puzzle. It is okay for a leading digit to be a zero, such as if L, H, or P were assigned to the value 0 in the puzzle above.

Your function will be passed a Cryptarithm puzzle by reference as a structure that contains the three strings (two operands and sum), along with two methods for replacing or un-replacing all occurrences of a given letter with a given integer in all three strings. For example, if you call puzzle.replace('X', 4); on the structure, all occurrences of the letter 'X' will become occurrences of the number 4 in the three strings in the puzzle. The struct also defines a << operator that prints the puzzle in the format shown above. Below is the struct's declaration along with an example call to your function:

// provided structure type
struct Cryptarithm {
    string op1, op2, sum;
    void replace(char c, int i);
    void unreplace(char c, int i);
};

// calling your function
Cryptarithm puzzle {"LOVE", "HATE", "PEACE"};
cryptaSolver(puzzle);

Your code should stop exploring once it finds and prints any single correct solution. A correct solution is defined as one where all characters have been substituted for unique integer values and where the sum of op1 and op2 is exactly equal to sum. If your code finds a solution to the puzzle, you should print the puzzle to the console using its << operator. If there is no solution to the given puzzle, your function should produce no output.

The library functions stringToInteger and/or integerToString may help you when solving this problem.

Assumptions: You may assume that the puzzle's op1, op2, and sum values are non-empty strings that contain only uppercase letters, though the strings might not be the same length. You may assume that the puzzle is always an addition puzzle where you are trying to find a mapping where op1 + op2 is equal to sum, and doesn't involve any other math operations.

Efficiency: While your code is not required to have any particular Big-Oh, you should avoid code that is extremely inefficient, repeatedly revisits the same path many times, and so on. You should not explore obviously invalid paths, such as trying to assign the same digit value to two or more different letters. In a very clever implementation it would be possible to improve efficiency by checking partial results, such as replacing only the ones digit and seeing if those add up properly before proceeding. It is not required nor recommended to make these kinds of arithmetic optimizations. You can create a full mapping of all the letters in the puzzle to integers before checking whether the mapping produces a correct solution. You should choose reasonable collections that efficiently implement the operations you need.

Constraints: Obey the following restrictions in your solution:

• Do not declare any global variables.
• You are allowed to use collections as needed to help you solve the problem.
• Your code can contain loops as needed, but your overall algorithm must be recursive.
• You are allowed to define other "helper" functions if you like; they are subject to these same constraints.