Smudged secret messages

This Riddler is a twist on a classic problem: decoding equations! Here is the paraphrased problem:

The goal is to decode two equations. In each of them, every different letter stands for a different digit. But there is a minor problem in both equations. In the first equation, letters accidentally were smudged and are now unreadable. (These are represented with dashes below.) But we know that all 10 digits, 0 through 9, appear in the equation.

What digits belong to what letters, and what are the dashes? In the second equation, one of the letters in the equation is wrong. But we don’t know which one. Which is it?

Here is my detailed solution:
[Show Solution]

This type of puzzle is called a cryptarithm, but this variant has the additional twist of smudges or errors that make the puzzle more challenging. Just like Sudoku, the puzzle involves filling numbers in a grid subject to several rules. Similarly, we can solve the problem by carefully and methodically deducing the solution using logic. In this post, I’m going to present a completely different approach; integer programming! By encoding the problem as an integer program, we can leverage powerful solvers to rapidly find the solution.

You might be thinking: if we’re asking a computer to solve the problem, then why not just have the computer check all possibilities? In this case, there are 10! = 3,628,800 different ways to assign the letters to the digits 0 through 9. This is certainly within the realm of possibility. I wrote code to do this and it took about 16 seconds to loop through all permutations. If we stop once we find a solution, we can expect this approach to take about 8 seconds. Not bad, but not particularly elegant either… I’ve included a link to all my code at the bottom of this post in case you’re interested in seeing how I went about coding it.

First problem

The secret code is:
\[
EXMREEK + EHKREKK = -K\!-\!H\!-\!X\!-\!E
\]The first thing to observe is that there are six distinct letters: $\{E,X,M,R,K,H\}$ and there are four smudges. Since each number 0 through 9 must appear exactly once, this tells us that the four smudges must correspond to different numbers. Therefore, we can add more variables and write the equation as:
\[
EXMREEK + EHKREKK = AKBHCXDE
\]

We will use ten binary numbers to encode each letter. For example, the letter $E$ is encoded using the list of binary numbers $\{E_0,E_1,\dots,E_9\}$ and represented as:
\[
E = E_1 + 2 E_2 + 3 E_3 + \cdots + 9 E_9
\]We then add the constraint:
\[
E_0 + E_1 + \cdots + E_9 = 1\qquad\text{for }\{E,X,M,\dots,D\}
\]This forces exactly one of the $E_j$ to equal $1$. This will be our way of encoding $E=j$. We also encode the other 9 letters in a similar way. Next, we must ensure that each letter corresponds to a distinct number. We do this by adding the constraints
\[
E_j + X_j + M_j + \cdots + D_j = 1\qquad\text{for }j=0,\dots,9
\]This ensures that the digit $j$ is associated to exactly one of the letters.

Next, we introduce variables to represent the “carry-over” digits. Since we’re adding two numbers, we will only ever carry over 0 or 1 for each digit. Let’s call these variables $Q_j$. The sum then looks like:
\[
\begin{array}{cccccccc}
Q_1&Q_2&Q_3&Q_4&Q_5&Q_6&Q_7& \\
& E & X & M & R & E & E & K \\
+ & E & H & K & R & E & K & K \\ \hline
A & K & B & H & C & X & D & E
\end{array}
\]We then add a constraint for each of the “columns” that includes the carry-over digits. Starting from the right, we have:
\begin{align}
K + K &= 10 Q_7 + E \\
Q_7 + E + K &= 10 Q_6 + D \\
Q_6 + E + E &= 10 Q_5 + X \\
&\;\;\vdots \\
Q_2 + E + E &= 10 Q_1 + K \\
Q_1 &= A
\end{align}Taking a tally of what we’ve got so far, each letter above is encoded using ten binary variables, which we can substitute into each of the constraints above. The net result is that we must find 107 binary variables that satisfy 28 linear equality constraints. There is no objective function here; it’s just a feasibility problem. In other words, any combination of the variables that satisfies the equality constraints is a legitimate solution.

I coded this up in Julia using JuMP and the Gurobi solver. It took about 0.005 seconds to solve on my laptop (1,600 times faster than the brute-force solution!) and the solution turned out to be:
\begin{align}
B &= 0 & A &= 1 & X &= 2 & K &= 3 & M &= 4 \\
C &= 5 & E &= 6 & R &= 7 & H &= 8 & D &= 9
\end{align}

Second problem

In the second problem, the equation is:
\[
YTBBEDMKD + YHDBTYYDD = EDYTERTPTY
\] In this variant, there is an “error” somewhere in the above sum. In other words, one of the letters is wrong. This seems rather difficult to model, so we will model something related (and equivalent) instead. Instead of saying that one of the letters is wrong, we’ll say that one of the column sums is wrong. Proceeding as we did in the first problem, the equations (with carry-overs) look like:
\[
\begin{array}{cccccccccc}
Q_1&Q_2&Q_3&Q_4&Q_5&Q_6&Q_7&Q_8&Q_9& \\
&Y&T&B&B&E&D&M&K&D \\
+&Y&H&D&B&T&Y&Y&D&D \\ \hline
E&D&Y&T&E&R&T&P&T&Y
\end{array}
\]Let’s introduce new binary variables $Z_1,\dots,Z_{10}$ that encode whether the corresponding column sum is incorrect or not. We want:
\begin{align}
\text{if }Z_1&=0 & &\text{then} & Q_1 &= E \\
\text{if }Z_2&=0 & &\text{then} & Q_2 + Y + Y &= 10 Q_1 + D \\
\text{if }Z_3&=0 & &\text{then} & Q_3 + T + H &= 10 Q_2 + Y \\
&\;\;\vdots & &\quad \vdots & &\;\;\vdots \\
\text{if }Z_9&=0 & &\text{then} & Q_9 + K + D &= 10 Q_8 + T \\
\text{if }Z_{10}&=0 & &\text{then} & D + D &= 10 Q_9 + Y
\end{align}Therefore, if one of the equalities does not hold, this will result in the corresponding $Z_j$ being equal to $1$. We can then add an objective function; we seek the choice of $\{Y,T,B,\dots,P\}$ and $\{Q_j\}$ and $\{Z_j\}$ such that the sum $Z_1+\dots+Z_{10}$ is minimized. We are told there is one error, so we expect to be able to achieve a sum of 1, and we’ll know where the error lies.

So how do we encode these logical “if this then that” constraints into something more manageable (i.e. something algebraic)? A popular way to do this is via the big M method. I’ll use the third constraint as an example, and let’s rearrange it so it’s equal to zero:
\begin{align}
\text{if }Z_3&=0 & &\text{then} & Q_3+T+H-10 Q_2-Y&=0
\end{align}Since $Q_2,Q_3\in\{0,1\}$ and $T,H,Y\in\{0,\dots,9\}$, by substituting in order to minimize or maximize, we obtain the following bounds:
\[
-19 \le Q_3+T+H-10 Q_2-Y \le 19
\]We can then encode the logical “if this then that” constraint as:
\[
-19Z_3 \le Q_3+T+H-10 Q_2-Y \le 19Z_3
\]Note that when $Z_3=0$, both sides of the inequality become zero, effectively turning it into an equality, which is what we wanted! Conversely, if $Z_3=1$ the left and right sides are replaced by global lower and upper bounds, so the constraint becomes a tautology. I coded this up using Julia/JuMP/Gurobi as before. The result is an integer linear program with 119 binary variables, 20 equality constraints, and 20 inequality constraints. It took about 0.3 seconds to solve on my laptop and the solution turned out to be:
\begin{align}
R&=0 & E&=1 & M&=2 & D&=3 & K&=4 \\
B&=5 & Y&=6 & H&=7 & P&=8 & T&=9
\end{align}The error occurs in the second-last column (K+D=T), which translates to (4+3=9). There are three possible ways to cause this error by changing a single letter:

change the 4 to a 6 (i.e. the K should have been a Y)
change the 3 to a 5 (i.e. the D should have been a B)
change the 9 to a 7 (i.e. the T should have been an H)

If you’re just interested in the answers, here they are:
[Show Solution]

Smudged secret messages

First problem

Second problem

Summary of solutions

Leave a Reply Cancel reply