ICS 46 Combinatorial Puzzles

Introduction

In the first three lectures, we saw that recursion can make some seemingly laborious problem solving into a straight-forward exercise. In project 0, we saw that we can check if a solution is valid to summation puzzles. In this assignment, we're going to solve summation puzzles.

In a summation puzzle, you are given three strings of the form POT + PAN = BIB. Typically each is a word, often with a theme to the three chosen. Your goal is to assign a distinct digit to each letter in the equation in order to make the result true. For example, if the puzzle is POT + PAN = BIB, the mapping P:2, O:3, T:1, A:7, N:4, B:5, I:0 will solve this, as 231 + 274 = 505.

Requirements

For this project, you are only required to implement one function found in puzzleSolver.cpp:

bool puzzleSolver(const std::string& s1, const std::string& s2, const std::string& s3, std::unordered_map< char, unsigned > & mapping)

• This function should return true if, and only if, the puzzle is solvable: that is, if there is a mapping of the letters that appear in the three strings to distinct digits such that the sum of the first two is the third (s1 + s2 == s3).
• No string will have a value larger than 4,294,967,295 in its correct substitution, nor will the addition have any integer-overflow to check for. If you do not know what integer overflow is, you do not need to check during this assignment (although it's worth knowing in general).
• You may assume it is called with three valid non-empty strings as parameters and with an otherwise empty map. The strings will always consist only of all-capital letters.
• The puzzle solution may have a leading zero for a string.
  • For example, in the provided test cases, we see that "UCI + ALEX = MIKE" has a solution. This corresponds to 572 + 8631 = 9203. The puzzle KUCI + ALEX = MIKE also has a solution with the same mapping.
• Your solution must explicitly use recursion in a meaningful way towards solving the problem. You may not solve this by using a function like std::next_permutation (from < algorithm >) to enumerate possibilities.
  • The function puzzleSolver itself need not be recursive if you would prefer to have a helper function that is.
  • Writing your own recursive "next_permutation" function does not constitute a meaningful use of recursion for this problem.
• The function must return a boolean indicating whether or not the puzzle has a solution.
  • If the puzzle does not have a solution, your function should return false.
  • If the puzzle does have a solution your function should return true and have the unordered_map< char, unsigned > parameter contain said solution. That is, the four parameters to the puzzleSolver function need to be such that a correct solution to project 0 would return true with those parameters.
  • If there are multiple solutions, returning any of them is fine. You can think of my grading code as this:
  • I know if the test case has or hasn't a solution. I check that you return the right bool value.
  • If it has a solution, I also run a (correct) solution to proj0's related function on the three strings + the map's status at the end of your function.

Restrictions

• You may use standard libraries as appropriate, unless there is one that makes solving this problem trivial.
• You are explicitly permitted to use std::unordered_set, std::list, std::queue, and std::stack if you so choose. If you want to have a stack, you do not need to use your stack from project zero. You are pretty much required to use std::unordered_map.