Making a cryptaritmetic solver in C++

Question

I am planning out a C++ program that takes 3 strings that represent a cryptarithmetic puzzle. For example, given TWO, TWO, and FOUR, the program would find digit substitutions for each letter such that the mathematical expression

   TWO 

+  TWO 

------

  FOUR

is true, with the inputs assumed to be right-justified. One way to go about this would, of course, be to just brute force it, assigning every possible substitution for each letter with nested loops, trying the sum repeatedly, etc., until the answer is finally found.

My thought is that though this is terribly inefficient, the underlying loop-check thing may be a feasible (or even necessary) way to go--after a series of deductions are performed to limit the domains of each variable. I'm finding it kind of hard to visualize, but would it be reasonable to first assume a general/padded structure like this (each X represents a not-necessarily distinct digit, and each C is a carry digit, which in this case, will either be 0 or 1)? :

   CCC.....CCC

   XXX.....XXXX

+  XXX.....XXXX

----------------

  CXXX.....XXXX 

With that in mind, some more planning thoughts:

-Though leading zeros will not be given in the problem, I probably ought to add enough of them where appropriate to even things out/match operands up.

-I'm thinking I should start with a set of possible values 0-9 for each letter, perhaps stored as vectors in a 'domains' table, and eliminate values from this as deductions are made. For example, if I see some letters lined up like this

 A

 C

--

 A

, I can tell that C is zero and this eliminates all other values from its domain. I can think of quite a few deductions, but generalizing them to all kinds of little situations and putting it into code seems kind of tricky at first glance.

-Assuming I have a good series of deductions that run through things and boot out lots of values from the domains table, I suppose I'd still just loop over everything and hope that the state space is small enough to generate a solution in a reasonable amount of time. But it feels like there has to be more to it than that! -- maybe some clever equations to set up or something along those lines.

Tips are appreciated!

Answer 1

Cryptarithm is a sort of mathematical puzzles in which the digits are replaced by letters of the alphabet or other symbols. If a similar letter occurs more than once, it must be assigned the same digit each time. No two distinct letters may be assigned the same digit. So, the query is to find the unique digit corresponding to a unique letter. Cryptarithmetic is the science and art of designing and solving cryptarithms.

Here you can refer to this link for C++ program for Solving Cryptarithmetic Puzzles: 

https://www.geeksforgeeks.org/c-code-article-backtracking-set-8-solving-cryptarithmetic-puzzles/

Cryptarithmetic is a class of mathematical puzzles in which the digits are replaced by letters of the alphabet or other symbols. In Artificial Intelligence this problem is under the category of constraint satisfaction problem So if you wish to learn about Artificial Intelligence then visit this Artificial Intelligence Course.