by A cryptarithmetic (also called verbal arithmetic) puzzle is a mathematical operation where the numbers are represented by letters. So each letter in the puzzle represent a certain unique digit.
The objective is to find out the digit represented by each letter that satisfies a given equation.
SEND + MORE --------- = MONEY
In this example, the solution to the puzzle is:
O = 0, M = 1, Y = 2, E = 5, N = 6, D = 7, R = 8, and S = 9.
which gives us:
9567 + 1085 --------- = 10652
Another example is give below
CP + IS + FUN -------- = TRUE
Here, the solution is R=0, T=1, C=2, P=3, S=4, E=5, U-6, I=7, N=8, F=9
which gives us:
23 + 74 + 968 -------- = 1065
Modelling the Problem
Step 1: The first step is to identify the variables. In this case, out variables are all the letters in the problem. They are:
C, P, I, S, F, U, N, T, R, E
Not that there will be not repeating variable. Also, the values of the variable are single digits, therefore the ranges are 0 to 9. The code below defines the variable.
from ortools.sat.python import cp_model model = cp_model.CpModel()
The next code sets up the variables
base = 10 c = model.NewIntVar(1, 9, 'C') p = model.NewIntVar(0, 9, 'P') i = model.NewIntVar(1, 9, 'I') s = model.NewIntVar(0, 9, 'S') f = model.NewIntVar(1, 9, 'F') u = model.NewIntVar(0, 9, 'U') n = model.NewIntVar(0, 9, 'N') t = model.NewIntVar(1, 9, 'T') r = model.NewIntVar(0, 9, 'R') e = model.NewIntVar(0, 9, 'E') # List of variables letters = [c, p, i, s, f, u, n, t, r, e]
Step 2: Then we identify the constraints
The variables are letter and can take on single digit value
Therefore we can establish the following constraints
- CP + IS + FUN = TRUE
- each of the letter must be a different digit
- C, I, F, T ≠0 (since leading digit in a number is not zero)
The code below defines the constraints and the objective function
# Define the constraints model.AddAllDifferent(letters) # CP + IS + FUN = TRUE model.Add(c * 10 + p + i * 10 + s + f * base**2 + u * 10 + n == t * 10**3 + r * 10**2 + u * 10 + e)
Step 3: Printing all Solutions
We want the solver to print the solution as it finds them. The code below does that:
# Solution Printer Class class VarArraySolutionPrinter(cp_model.CpSolverSolutionCallback): def __init__(self, variables): cp_model.CpSolverSolutionCallback.__init__(self) self.__variables = variables self.__solution_count = 0 def on_solution_callback(self): self.__solution_count += 1 for v in self.__variables: print('%s=%i ' %(v, self.Value(v)), end='') print() def solution_count(self): return self.__solution_count
Step 4: Invoke the Solver and call the printer.
# Call the solver solver = cp_model.CpSolver() solution_printer = VarArraySolutionPrinter(letters) status = solver.SearchForAllSolutions(model, solution_printer)
The Complete program
If you run the code you will have the following result:
C=6 P=4 I=3 S=5 F=9 U=2 N=8 T=1 R=0 E=7 C=3 P=4 I=6 S=5 F=9 U=2 N=8 T=1 R=0 E=7 C=3 P=4 I=6 S=8 F=9 U=2 N=5 T=1 R=0 E=7 C=3 P=2 I=6 S=7 F=9 U=8 N=5 T=1 R=0 E=4 C=3 P=2 I=6 S=5 F=9 U=8 N=7 T=1 R=0 E=4 C=2 P=3 I=7 S=6 F=9 U=8 N=5 T=1 R=0 E=4 C=2 P=3 I=7 S=4 F=9 U=6 N=8 T=1 R=0 E=5 C=2 P=3 I=7 S=5 F=9 U=4 N=8 T=1 R=0 E=6 C=2 P=3 I=7 S=8 F=9 U=4 N=5 T=1 R=0 E=6 C=2 P=3 I=7 S=8 F=9 U=6 N=4 T=1 R=0 E=5 C=2 P=3 I=7 S=5 F=9 U=8 N=6 T=1 R=0 E=4 C=7 P=3 I=2 S=5 F=9 U=8 N=6 T=1 R=0 E=4 C=7 P=3 I=2 S=6 F=9 U=8 N=5 T=1 R=0 E=4 C=6 P=2 I=3 S=7 F=9 U=8 N=5 T=1 R=0 E=4 C=6 P=2 I=3 S=5 F=9 U=8 N=7 T=1 R=0 E=4 C=7 P=3 I=2 S=4 F=9 U=6 N=8 T=1 R=0 E=5 C=7 P=3 I=2 S=8 F=9 U=6 N=4 T=1 R=0 E=5 C=7 P=4 I=2 S=8 F=9 U=6 N=3 T=1 R=0 E=5 C=7 P=8 I=2 S=4 F=9 U=6 N=3 T=1 R=0 E=5 C=7 P=8 I=2 S=3 F=9 U=6 N=4 T=1 R=0 E=5 C=7 P=4 I=2 S=3 F=9 U=6 N=8 T=1 R=0 E=5 C=7 P=6 I=2 S=3 F=9 U=8 N=5 T=1 R=0 E=4 C=7 P=5 I=2 S=3 F=9 U=8 N=6 T=1 R=0 E=4 C=7 P=8 I=2 S=3 F=9 U=4 N=5 T=1 R=0 E=6 C=7 P=8 I=2 S=5 F=9 U=4 N=3 T=1 R=0 E=6 C=7 P=3 I=2 S=5 F=9 U=4 N=8 T=1 R=0 E=6 C=7 P=5 I=2 S=3 F=9 U=4 N=8 T=1 R=0 E=6 C=7 P=3 I=2 S=8 F=9 U=4 N=5 T=1 R=0 E=6 C=7 P=5 I=2 S=8 F=9 U=4 N=3 T=1 R=0 E=6 C=2 P=5 I=7 S=8 F=9 U=4 N=3 T=1 R=0 E=6 C=4 P=6 I=5 S=8 F=9 U=2 N=3 T=1 R=0 E=7 C=5 P=6 I=4 S=8 F=9 U=2 N=3 T=1 R=0 E=7 C=6 P=5 I=3 S=8 F=9 U=2 N=4 T=1 R=0 E=7 C=6 P=5 I=3 S=4 F=9 U=2 N=8 T=1 R=0 E=7 C=6 P=4 I=3 S=8 F=9 U=2 N=5 T=1 R=0 E=7 C=5 P=6 I=4 S=3 F=9 U=2 N=8 T=1 R=0 E=7 C=4 P=6 I=5 S=3 F=9 U=2 N=8 T=1 R=0 E=7 C=4 P=3 I=5 S=6 F=9 U=2 N=8 T=1 R=0 E=7 C=4 P=3 I=5 S=8 F=9 U=2 N=6 T=1 R=0 E=7 C=5 P=3 I=4 S=8 F=9 U=2 N=6 T=1 R=0 E=7 C=5 P=3 I=4 S=6 F=9 U=2 N=8 T=1 R=0 E=7 C=3 P=5 I=6 S=4 F=9 U=2 N=8 T=1 R=0 E=7 C=3 P=5 I=6 S=8 F=9 U=2 N=4 T=1 R=0 E=7 C=3 P=8 I=6 S=5 F=9 U=2 N=4 T=1 R=0 E=7 C=3 P=8 I=6 S=4 F=9 U=2 N=5 T=1 R=0 E=7 C=4 P=8 I=5 S=3 F=9 U=2 N=6 T=1 R=0 E=7 C=5 P=8 I=4 S=3 F=9 U=2 N=6 T=1 R=0 E=7 C=6 P=8 I=3 S=4 F=9 U=2 N=5 T=1 R=0 E=7 C=6 P=8 I=3 S=5 F=9 U=2 N=4 T=1 R=0 E=7 C=5 P=8 I=4 S=6 F=9 U=2 N=3 T=1 R=0 E=7 C=4 P=8 I=5 S=6 F=9 U=2 N=3 T=1 R=0 E=7 C=3 P=7 I=6 S=2 F=9 U=8 N=5 T=1 R=0 E=4 C=3 P=5 I=6 S=2 F=9 U=8 N=7 T=1 R=0 E=4 C=3 P=7 I=6 S=5 F=9 U=8 N=2 T=1 R=0 E=4 C=3 P=5 I=6 S=7 F=9 U=8 N=2 T=1 R=0 E=4 C=2 P=5 I=7 S=6 F=9 U=8 N=3 T=1 R=0 E=4 C=2 P=6 I=7 S=5 F=9 U=8 N=3 T=1 R=0 E=4 C=2 P=6 I=7 S=3 F=9 U=8 N=5 T=1 R=0 E=4 C=2 P=5 I=7 S=3 F=9 U=8 N=6 T=1 R=0 E=4 C=2 P=8 I=7 S=3 F=9 U=4 N=5 T=1 R=0 E=6 C=2 P=5 I=7 S=3 F=9 U=4 N=8 T=1 R=0 E=6 C=2 P=8 I=7 S=3 F=9 U=6 N=4 T=1 R=0 E=5 C=2 P=4 I=7 S=3 F=9 U=6 N=8 T=1 R=0 E=5 C=2 P=4 I=7 S=8 F=9 U=6 N=3 T=1 R=0 E=5 C=2 P=8 I=7 S=4 F=9 U=6 N=3 T=1 R=0 E=5 C=2 P=8 I=7 S=5 F=9 U=4 N=3 T=1 R=0 E=6 C=7 P=6 I=2 S=5 F=9 U=8 N=3 T=1 R=0 E=4 C=7 P=5 I=2 S=6 F=9 U=8 N=3 T=1 R=0 E=4 C=6 P=5 I=3 S=7 F=9 U=8 N=2 T=1 R=0 E=4 C=6 P=7 I=3 S=5 F=9 U=8 N=2 T=1 R=0 E=4 C=6 P=7 I=3 S=2 F=9 U=8 N=5 T=1 R=0 E=4 C=6 P=5 I=3 S=2 F=9 U=8 N=7 T=1 R=0 E=4
