Creating a cryptographic solver in C ++

Question

I am planning a C ++ program that accepts 3 lines that represent a cryptographic puzzle. For example, given TWO, TWO and FOUR, the program will find a replacement for the numbers for each letter so that the mathematical expression

TWO + TWO ------ FOUR 

true, with the inputs supposedly read to the right. Of course, one way to do this is to simply brute force, assigning each possible substitution for each letter by nested cycles, repeating the sum many times, etc., until a final answer is found.

My thought is that although this is terribly inefficient, the basic loop checking function can be a feasible (or even necessary) way - after doing a series of deductions to limit the domains of each variable. I find it hard to imagine, but would it be wise to first adopt a general / augmented structure like this (each X is an optionally different digit, and each C is a carry character, which in this case will be either 0 or 1)?

  CCC.....CCC XXX.....XXXX + XXX.....XXXX ---------------- CXXX.....XXXX 

With this in mind, some thoughts on planning:

-Good leading zeros will not be given in the problem, I probably should add enough of them when necessary, so that even things output / combine operands.

-I think that I should start with a set of possible values ​​0-9 for each letter, possibly saved as vectors in the "domains" table, and exclude the values ​​from this, since conclusions are drawn. For example, if I see several letters arranged in this way

  A C -- A 

I can say that C is zero, and this excludes all other values ​​from its scope. I can come up with a lot of conclusions, but generalizing them to all kinds of small situations and putting them in code seems complicated at first glance.

-Accepting, I have a good series of conclusions that go through things and load a lot of values ​​from the domain table, I believe that I still just go around everything and hope that the state space is small enough to create a solution in a reasonable amount of time. But it seems like more is needed for this! - maybe some kind of smart equations to set up or something like that.

Tips are welcome!

Answer 1

Cryptographic problems are classic constraint satisfaction problems . Basically, you need to have your program generate constraints based on input, so that you end up with the following:

 O + O = 2O = R + 10Carry1 W + W + Carry1 = 2W + Carry1 = U + 10Carry2 T + T + Carry2 = 2T + Carry2 = O + 10Carry3 = O + 10F 

Generalized pseudocode:

 for i in range of shorter input, or either input if they're the same length: shorterInput[i] + longerInput2[i] + Carry[i] = result[i] + 10*Carry[i+1] // Carry[0] == 0 for the rest of the longer input, if one is longer: longerInput[i] + Carry[i] = result[i] + 10*Carry[i+1] 

Additional restrictions based on the definition of the problem:

 Range(digits) == {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} Range(auxiliary_carries) == {0, 1} 

So for your example:

 Range(O, W, T) == {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} Range(Carry1, Carry2, F) == {0, 1} 

Once you have created restrictions to limit the search space, you can use the CSP resolution methods, as described in the related article, to go through the search space and determine your solution (if it exists, of course). The concept of (local) consistency is very important here, and using it can significantly reduce the search space for the CSP.

As a simple example, note that cryptocriticality generally does not use leading zeros, which means that if the result is longer than both inputs, the ending digit, i.e. the last portable digit, should be 1 (so in your example, this means F == 1 ). This restriction can then be extended backwards, as this means that 2T + Carry2 == O + 10 ; in other words, the minimum value for T should be 5, since Carry2 can be no more than 1 and 2 (4) + 1 == 9. There are other ways to improve the search (algorithm for minimal conflicts, etc.), but I would chose not to turn this answer into a full-fledged CSP class, so I will leave you a further investigation.

(Note that you cannot make assumptions such as A+C=A → C == 0 , except for at least a significant column due to the possibility of C being 9 and the carry digits in the column equal to 1. This means that C will generally be limited to {0, 9} , so you weren’t completely disconnected.)

Answer 2

You can iterate over this problem from right to left, that is, the way you perform the actual operation. Start with the rightmost column. For each digit that you encounter, you check if there is already a task for this digit. If there is, you use its value and continue. If this does not happen, you enter a cycle for all possible numbers (possibly without using already used ones, if you want a bijective map) and continue recursively with each possible purpose. When you reach the sum line, you again check to see if a variable has already been assigned to the specified digit. If this is not the case, you assign the last digit of your current amount, and then proceed to the next column with a higher value, taking the carry with you. If you already have a task, and it is consistent with the last digit of your result, you do the same. If there is an appointment, and he does not agree, then you interrupt the current branch and return to the next cycle, where you have other numbers.

The advantage of this approach is that many variables are determined by the sum, rather than guessed from the front. In particular, for letters that are found only in the sum line, this can be a huge victory. In addition, you can detect errors at an early stage, while avoiding the choice of letters in some cases where the choice you have made so far is already incompatible. The downside may be a slightly more complex recursive structure of your program. But once you fix it, you also learned a lot about turning thoughts into code.

Answer 3

I solved this problem on my blog using a randomized mountain climbing algorithm. The main idea is to choose a random assignment of numbers to the letters, to “score” the task by calculating the difference between the two sides of the equation, then changing the purpose (swapping two digits) and recounting, keeping those changes that improve the evaluation and discarding of those changes that they don’t do it. This is climbing a hill because you only accept changes in one direction. The problem with climbing the hill is that it sometimes gets stuck at a local maximum, so everyone throws away the current attempt so often and starts over; that the randomization part of the algorithm. The algorithm is very fast: it solves every cryptorhythm that I gave it in a split second.