{"id":189,"date":"2021-01-21T21:52:10","date_gmt":"2021-01-21T21:52:10","guid":{"rendered":"https:\/\/www.kindsonthegenius.com\/data-science\/?p=189"},"modified":"2021-01-21T21:52:10","modified_gmt":"2021-01-21T21:52:10","slug":"solving-cryparithetic-puzzle-in-python","status":"publish","type":"post","link":"https:\/\/www.kindsonthegenius.com\/data-science\/solving-cryparithetic-puzzle-in-python\/","title":{"rendered":"Solving Cryparithetic Puzzle in Python"},"content":{"rendered":"

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.<\/p>\n

The objective is to find out the digit represented by each letter that satisfies a given equation.<\/p>\n

     SEND\r\n+    MORE\r\n---------\r\n=   MONEY\r\n<\/pre>\n
In this example, the solution to the puzzle is:
\nO = 0, M = 1, Y = 2, E = 5, N = 6, D = 7, R = 8, and S = 9.<\/p>\n
which gives us:<\/p>\n
     9567\r\n+    1085\r\n---------\r\n=   10652\r\n<\/pre>\n
Another example<\/strong> is give below<\/p>\n
      CP\r\n+     IS\r\n+    FUN\r\n--------\r\n=   TRUE\r\n<\/pre>\n
Here, the solution is R=0, T=1, C=2, P=3, S=4, E=5, U-6,<\/span> I=7, N=8, F=9<\/span><\/p>\n
which gives us:<\/p>\n
      23\r\n+     74\r\n+    968\r\n--------\r\n=   1065<\/pre>\n
 <\/p>\n
Modelling the Problem<\/strong><\/p>\n
Step 1<\/strong>: The first step is to identify the variables. In this case, out variables are all the letters in the problem. They are:<\/p>\n
C, P, I, S, F, U, N, T, R, E<\/p>\n
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.<\/p>\n
from<\/span> ortools.sat.python<\/span> import<\/span> cp_model\r\nmodel =<\/span> cp_model.<\/span>CpModel()\r\n<\/pre>\n
The next code sets up the variables
\n<\/p>\n
base =<\/span> 10<\/span>\r\n\r\nc =<\/span> model.<\/span>NewIntVar(1<\/span>, 9<\/span>, 'C'<\/span>)\r\np =<\/span> model.<\/span>NewIntVar(0<\/span>, 9<\/span>, 'P'<\/span>)\r\ni =<\/span> model.<\/span>NewIntVar(1<\/span>, 9<\/span>, 'I'<\/span>)\r\ns =<\/span> model.<\/span>NewIntVar(0<\/span>, 9<\/span>, 'S'<\/span>)\r\nf =<\/span> model.<\/span>NewIntVar(1<\/span>, 9<\/span>, 'F'<\/span>)\r\nu =<\/span> model.<\/span>NewIntVar(0<\/span>, 9<\/span>, 'U'<\/span>)\r\nn =<\/span> model.<\/span>NewIntVar(0<\/span>, 9<\/span>, 'N'<\/span>)\r\nt =<\/span> model.<\/span>NewIntVar(1<\/span>, 9<\/span>, 'T'<\/span>)\r\nr =<\/span> model.<\/span>NewIntVar(0<\/span>, 9<\/span>, 'R'<\/span>)\r\ne =<\/span> model.<\/span>NewIntVar(0<\/span>, 9<\/span>, 'E'<\/span>)\r\n\r\n# List of variables<\/span>\r\nletters =<\/span> [c, p, i, s, f, u, n, t, r, e]\r\n<\/pre>\n
 <\/p>\n
Step 2:<\/strong> Then we identify the constraints<\/p>\n
The variables are letter and can take on single digit value<\/p>\n
Therefore we can establish the following constraints<\/p>\n