ILP Part 71 — Typo

This is the seventieth first part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Let’s solve the Literówka problem. It’s almost a regular riddle with digits hidden behind letters but this time one letter in the final sum is incorrect. How do we represent this in ILP?

Let’s see the code first:

We start with lines 1-6 in which we define variables for letters as if they were all correct. We make them all different and set ranges. variable[0] stands for letter A.

In line 8 we add helper variable as we’ll use this constant many times.

Next, in lines 10-36 we implement long addition. Letter “s” stands for sum, “r” for remainder, “d” for integer division. We just unroll the addition algorithm and make it explicit.

Next, in lines 39-51 we implement addition for the final result. Again, first “r” stands for result, second “r” for remainder, “d” for division. No magic here.

Finally, we need to implement the constraint that exactly one letter in final sum is a typo. So we create binary variables in line 53 and make sure three of them are set (line 54).

Finally, we add constraints based on material implication. If given digit is correct then it must meet some constraint. So we go through digits one by one and if they are correct then they must be equal to some other well known variable.


So the final riddle looks like this:

So we can see that the leftmost digit was a typo.