solver.py

from constraint import Problem
import re

import random
random.seed(1)

class CryptarithmeticSolver:
    def __init__(self, equations):

        self.equations = equations
        letters = re.findall(r"[A-Z]", "".join(equations))
        self.variables = sorted(set(letters)) # in our example we play with "ABCDEFGHJK" excluding I for clarity
        self.problem = Problem()

    def analyze_equation_structure(self, equation):
        """
        Analyze equation structure to extract terms and their patterns.
        Returns terms, operator, and digit counts for each term.
        """
        lhs, rhs = equation.split("=")
        lhs = lhs.strip()
        rhs = rhs.strip()
        
        operators = {"+": "+", "-": "-", "*": "*", "/": "/"}
        operator = next((op for op in operators if op in lhs), None)
        if not operator:
            raise ValueError(f"Unsupported operation in equation: {equation}")
            
        term1, term2 = [t.strip() for t in lhs.split(operator)]
        result = rhs.strip()
        
        return {
            "term1": term1,
            "term2": term2,
            "result": result,
            "operator": operator
        }

        
    def setup_variable_constraints(self):
        """Set up the basic constraints for the puzzle."""
        self.problem.addVariables(self.variables, range(len(self.variables)))
        
        # All variables must have different values
        self.problem.addConstraint(
            lambda *values: len(values) == len(set(values)), 
            self.variables
        )
    
    def set_mathematical_constraints(self, equation):
        """Set up the mathematical constraints for each equation."""
        structure = self.analyze_equation_structure(equation)
        term1, term2 = structure["term1"], structure["term2"]
        result = structure["result"]
        operator = structure["operator"]

        # Get only the variables/letters for the current equation       
        relevant_vars = list(set(term1 + term2 + result))

        
        def constraint(*args):
            assignment = dict(zip(relevant_vars, args))
            
            t1 = self.evaluate_term(term1, assignment)
            t2 = self.evaluate_term(term2, assignment)
            r = self.evaluate_term(result, assignment)
            
            if any(x is None for x in (t1, t2, r)):
                return False

            # Constraint 1: the sum of the left term and right term must match the result and the result should always be even or higher than the two terms added together    
            if operator == "+": return t1 + t2 == r and r >= max(t1, t2)
            # Constraint 2: the subtraction of the left term and right term must match the result and the results should be even or smaller than the right term subtracted from the left term. Result should be non-negative
            if operator == "-": return t1 - t2 == r and t1 >= t2 and (t1 - t2) >= 0
            # Constraint 3: the multiplication of the left term and right term must match the result and the result should be even or higher than the two terms multiplied together. Assuming left and right are non-negative
            if operator == "*": return t1 * t2 == r and r >= max(t1, t2)
            # Constraint 4: the division of the left term by the right term must match the result. Division by zero is not allowed. Division is only allowed with no remainder (whole numbers)
            if operator == "/": return t2 != 0 and t1 % t2 == 0 and t1 // t2 == r
            
        self.problem.addConstraint(constraint, relevant_vars)


    def add_generalized_constraints(self):
        """Add constraints based on general mathematical properties."""
        for equation in self.equations:
            structure = self.analyze_equation_structure(equation)
            term1, term2, result = structure["term1"], structure["term2"], structure["result"]
            op = structure["operator"]
            
            # Get all variables involved in this equation
            letters_involved = list(set(term1 + term2 + result))

            for term in [term1, term2, result]:
                if term[0] in self.variables:
                    # Constraint 5: if there are two or more letters in left or right term, then the first letter within that term cannot be 0
                    self.problem.addConstraint(lambda x: x > 0, [term[0]])
            
            # # Constraint 6: For multiplication, if result ends in 0, one factor must end in 0
            if op == "*" and result[-1] == "0":
                def zero_product_constraint(*args):
                    assignment = dict(zip(letters_involved, args))
                    t1_last = self.evaluate_term(term1[-1], assignment)
                    t2_last = self.evaluate_term(term2[-1], assignment)
                    return t1_last == 0 or t2_last == 0
                
                self.problem.addConstraint(zero_product_constraint, 
                                        [term1[-1], term2[-1]])

    @staticmethod
    def evaluate_term(term, assignment):
        """Convert a string of letters into its numeric value."""
        if len(term) == 1:
            return assignment.get(term, None)
        
        value = 0
        for i, letter in enumerate(reversed(term)):
            if letter not in assignment:
                return None
            value += 10 ** i * assignment[letter]
        return value
    
    
    def solve(self):
        """Solve the cryptarithmetic puzzle."""
        self.setup_variable_constraints()
  
        for equation in self.equations:
           self.set_mathematical_constraints(equation)
        self.add_generalized_constraints()
        
        return self.problem.getSolutions()

def main():
    equations = [
        "H * DDDB = HCAF",
        "H * CEC = GBDA",
        "CEC - JDJ = EAE",
        "GBDA + DGED = CAKE",
        "HCAF + EAE = CAKE",
        "DDDB + JDJ = DGED"
    ]
    
    solver = CryptarithmeticSolver(equations)
    solutions = solver.solve()
    
    print(f"Found {len(solutions)} solution(s):")
    for solution in solutions:
        print(solution)

if __name__ == "__main__":
    main()