During this activity, students will be able to:

- Solve cryptarithmetic puzzles by modeling them as a constraint-satisfaction problem (CSP).

**This activity must be developed in the pre-assigned teams of two.**

Using the updated `csp`

(constraint-satisfaction problem) module developed and descriped in chapter 3 of [KOPEC], write a Python script called `cryptarithmetic_puzzle.py`

that solves cryptarithmetic puzzles involving addition of two or more addends. **It is highly recommended that you reread this chapter of the book to make sure you have an adequate understanding of the algorithm being used.**

As defined in Wikipedia:

Cryptarithmetic is a type of mathematical game consisting of a mathematical equation among unknown numbers, whose digits are represented by letters of the alphabet. The goal is to identify the value of each letter. The equation is typically a basic arithmetic operation, such as addition.

Example:

I L U V + U ――――――――― Y E S

A solution to the above puzzle would be:

- E = 0
- I = 2
- L = 3
- S = 6
- U = 9
- V = 5
- Y = 4

And we can verify it:

2 3 9 5 + 9 ――――――――― 4 0 6

In your `cryptarithmetic_puzzle.py`

script, write a function called `solve_cryptarithmetic_puzzle`

that takes two inputs: a list of strings with the equation addends and a string with the equation result. Use the following code as a starting point:

from csp import Constraint, CSP def solve_cryptarithmetic_puzzle( addends: list[str], result: str) -> Optional[dict[str, int]]: # The rest of the function's code goes here ... # The rest of the module's code goes here ...

If the function finds a solution it should return a dictionary where the keys are the uppercase letters contained in the strings from `addends`

and `result`

, while the corresponding values are the digits from 0 to 9. The function should return `None`

if no solution was found.

So, for example, the following code:

solve_cryptarithmetic_puzzle(['i', 'luv', 'u'], 'yes'))

should return:

{'E': 0, 'I': 2, 'L': 3, 'S': 6, 'U': 9, 'V': 5, 'Y': 4}

**NOTE:** Your function will need to create an instance of the `CSP`

class from the `csp`

module. When doing so, youâ€™ll need to define at some point the *variables*, *domains*, and *constraints* for this problem. It is importante that the *variables* are specified as a list of strings containing only **uppercase letters sorted in ascending order**. If you do not follow this indication your code might have some issues with the unit tests (it may take longer to run or some tests might fail even if they produce a technically correct solution).

Test your program using the following unit tests:

# File: cryptarithmetic_puzzle_test.py from unittest import TestCase, main from cryptarithmetic_puzzle import solve_cryptarithmetic_puzzle class TestCryptarithmetic(TestCase): def test_cryptarithmetic_puzzle_1(self): self.assertEqual( {'X': 1, 'Y': 2, 'Z': 8}, solve_cryptarithmetic_puzzle(['x', 'y', 'z'], 'xx')) def test_cryptarithmetic_puzzle_2(self): self.assertEqual( {'A': 0, 'B': 1, 'C': 2, 'D': 4, 'E': 5, 'F': 7, 'G': 8, 'H': 9, 'I': 3, 'J': 6}, solve_cryptarithmetic_puzzle(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'], 'IJ')) def test_cryptarithmetic_puzzle_3(self): self.assertEqual( {'A': 1, 'B': 9, 'C': 8}, solve_cryptarithmetic_puzzle(['ab', 'bc', 'ca'], 'abc')) def test_cryptarithmetic_puzzle_4(self): self.assertEqual( {'X': 1, 'Y': 9, 'Z': 8}, solve_cryptarithmetic_puzzle(['xx', 'yy', 'zz'], 'xyz')) def test_cryptarithmetic_puzzle_5(self): self.assertEqual( {'X': 9, 'Y': 1, 'Z': 8}, solve_cryptarithmetic_puzzle(['xxxx', 'yyyy', 'zzzz'], 'yxxxz')) def test_cryptarithmetic_puzzle_6(self): self.assertEqual( {'X': 1, 'Y': 9, 'Z': 8}, solve_cryptarithmetic_puzzle(['xxxx', 'yyyy', 'zzzz'], 'xyyyz')) def test_cryptarithmetic_puzzle_7(self): self.assertIsNone( solve_cryptarithmetic_puzzle(['x', 'y', 'z'], 'xxx')) def test_cryptarithmetic_puzzle_8(self): self.assertIsNone( solve_cryptarithmetic_puzzle(['x', 'y', 'z'], 'xyz')) def test_cryptarithmetic_puzzle_9(self): self.assertEqual( {'E': 0, 'I': 2, 'L': 3, 'S': 6, 'U': 9, 'V': 5, 'Y': 4}, solve_cryptarithmetic_puzzle(['i', 'luv', 'u'], 'yes')) def test_cryptarithmetic_puzzle_10(self): self.assertEqual( {'A': 7, 'E': 8, 'G': 9, 'P': 1}, solve_cryptarithmetic_puzzle(['egg', 'egg'], 'page')) def test_cryptarithmetic_puzzle_11(self): self.assertEqual( {'A': 0, 'D': 4, 'H': 7, 'M': 3, 'R': 1, 'T': 5, 'Y': 9}, solve_cryptarithmetic_puzzle(['math', 'myth'], 'hard')) def test_cryptarithmetic_puzzle_12(self): self.assertEqual( {'F': 1, 'I': 3, 'M': 4, 'N': 7, 'S': 0, 'U': 6, 'W': 2}, solve_cryptarithmetic_puzzle(['fun', 'sun'], 'swim')) def test_cryptarithmetic_puzzle_13(self): self.assertEqual( {'D': 5, 'E': 1, 'N': 0, 'O': 6, 'V': 3}, solve_cryptarithmetic_puzzle(['odd', 'odd'], 'even')) def test_cryptarithmetic_puzzle_14(self): self.assertEqual( {'F': 0, 'O': 2, 'R': 4, 'T': 1, 'U': 6, 'W': 3}, solve_cryptarithmetic_puzzle(['two', 'two'], 'four')) def test_cryptarithmetic_puzzle_15(self): self.assertEqual( {'A': 0, 'F': 1, 'L': 3, 'W': 4, 'Y': 5}, solve_cryptarithmetic_puzzle(['fly', 'fly', 'fly'], 'away')) def test_cryptarithmetic_puzzle_16(self): self.assertEqual( {'A': 1, 'E': 8, 'H': 2, 'L': 3, 'P': 0, 'T': 9}, solve_cryptarithmetic_puzzle(['EAT', 'THAT'], 'APPLE')) def test_cryptarithmetic_puzzle_17(self): self.assertEqual( {'G': 8, 'O': 1, 'T': 2, 'U': 0}, solve_cryptarithmetic_puzzle(['to', 'go'], 'out')) def test_cryptarithmetic_puzzle_18(self): self.assertEqual( {'D': 1, 'E': 5, 'M': 0, 'N': 3, 'O': 8, 'R': 2, 'S': 7, 'Y': 6}, solve_cryptarithmetic_puzzle(['SEND', 'MORE'], 'MONEY')) if __name__ == '__main__': main()

Finally, make sure no type or PEP 8 style errors are produced by using the `mypy`

and `pycodestyle`

linters. You can incorporate these tools into VS Code or you can run them at the terminal.

Place in a comment at the top of the `cryptarithmetic_puzzle.py`

source file the authorsâ€™ personal information (student ID and name), for example:

#---------------------------------------------------------- # Lab #4: Cryptarithmetic with CSP # General cryptarithmetic puzzle solver. # # Date: 27-Sep-2022 # Authors: # A01770771 Kamala Khan # A01777771 Carol Danvers #----------------------------------------------------------

To deliver the `cryptarithmetic_puzzle.py`

file, please provide the following information:

Only one team member needs to upload the file.

**Due date is Tuesday, September 27.**