Advanced Algorithms

Lab #5: Cryptarithmetic with CSP


During this activity, students will be able to:


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 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.


   L U V
+      U
   Y E S

A solution to the above puzzle would be:

And we can verify it:

   3 9 5
+      9
   4 0 6

Implementation Details

In your 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 answer. Use the following code as a starting point:

from csp import Constraint, CSP

def solve_cryptarithmetic_puzzle(
        addends: list[str],
        answer: 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 answer, 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 #1: 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 a technically correct solution is produced).

NOTE #2: Contrary to what [KOPEC] indicates, your solution code should allow the first letter of answer to be zero. Take this into account, otherwise some of the unit tests will most definitely fail.

Test your code using the tests in the file Finally, make sure no type or PEP 8 style errors are produced by using the mypy and pycodestyle linters. You can run them at the terminal like this:



Place in a comment at the top of the source file the authors’ personal information (student ID and name), for example:

# Lab #5: Cryptarithmetic with CSP
# General cryptarithmetic puzzle solver.
# Date: 13-Oct-2023
# Authors:
#           A01770771 Kamala Khan
#           A01777771 Carol Danvers

Upload Instructions

To deliver the file, please provide the following information:

Request PIN

Only one team member needs to upload the file.

Due date is Friday, October 13.