16
$\begingroup$

According to Wikipedia, Alphametics, also known as verbal arithmetic, can be defined as "a type of mathematical game consisting of a mathematical equation among unknown numbers, whose digits are represented by letters. The goal is to identify the value of each letter."

For example, the problem:

SEND + MORE = MONEY

has the solution (mouse over to see):

O = 0, M = 1, Y = 2, E = 5, N = 6, D = 7, R = 8, S = 9.

Obviously, these can be solved by a brute force algorithm that involves attempting every possible variation of number/letter pairs. However, I don't want to use brute-force - that's an easy programming hack.

What I want to know is: What are some good general strategies for intelligently solving these verbal arithmetic problems by hand?

$\endgroup$
  • 2
    $\begingroup$ "Verbal arithmetic" is very confusing. It sounds like you're asking how to perform arithmetic using words, not the letter-number puzzles you're talking about here. $\endgroup$ – Joe Z. May 21 '14 at 22:40
  • $\begingroup$ "Verbal arithmetic" is what Wikipedia calls it. I agree, it is somewhat confusing, but I couldn't come up with a better term myself. If you feel that we need a new name for it, feel free to bring it up in meta. $\endgroup$ – Xynariz May 21 '14 at 22:49
  • $\begingroup$ Wikipedia also lists "cryptarithm" and "alphametics". Personally I prefer "cryptarithm". $\endgroup$ – Joe Z. May 22 '14 at 1:51
6
$\begingroup$

My setup is similar to Emrakul's, but since the OP asked for patterns, I will explore what Emrakul left as an exercise. And while I'll mostly discuss the same tips as in Xynariz's answer, his approach does not consider carry digits generally, which can miss possible solutions.

Like in Sudoku, there are quite a few patterns, some of which are very situational and convoluted and it'd be a hard exercise to not forget some case. However, there are some patterns that are more direct and frequent than others.

Generally, the themes involve pinpointing some letter to the values 0, 1 or 9, or deducing that a letter must be odd, even or within some range. The intersection of such clues should narrow down the possible values for a letter. For example, if you have $A = even$ and $A \lt 4$, then you know $A \in \{0, 2\}$ (this notation means A can be one of the following values).

Before starting looking for clues, I'd advise explicitly writing all equations including a carry digit, $c_n$, where $c_n$ is the overflow from the previous column, $n-1$. Since the starting column is 1, $c_0 = 0$. For the example in the OP, that would be:

$D + E = Y \pmod{10}$
$N + R + c_1 = E \pmod{10}$
$E + O + c_2 = N \pmod{10}$
etc...

If you're dealing with only two addends, $c_n \in \{0, 1\}$. For 3 addends, $c_n \in \{0, 1, 2\}$. That's because the highest value for the first column can be $9 + 9 + 9 = 27$ and since $c_1 \le 2$, any subsequent columns can be at most $29$. In general, for $k$ addends, $c_n \le k - 1$.

Look for more digits in the result than in the addends.

For $A + B = CD$, we know that $A + B$ must overflow since $C$ is a leading digit and can't be $0$. This forces us to conclude $C = 1$. Explicitly, that would be written as $0 + 0 + c_1 = C \Leftrightarrow c_1 = C$, with $C \not= 0$ and $c_1 \in \{0, 1\}$. Therefore, $C = 1$.

A special case of this is $A + BC = DEF$. Similar to above we know $D = 1$ and $c_2 = 1$, which means $0 + B + c_1 \ge 10$. But since $B \le 9$, the only possibility is for $B = 9$ and $c_1 = 1$. By extension, $E = 0$. As you can see, by plugging in equations newly deduced values, we can create a chain effect.

Look for the same letter in one of the addends and the sum.

The pattern $A + B + c_n = A \pmod{10}$ means we add a multiple of 10 to $A$. For two addends this means either

  • $B = 0, c_n = 0, c_{n+1} = 0$, or
  • $B = 9, c_1 = 1, c_{n+1} = 1$

Look for multiple occurances of a letter in the addends.

Here we try to establish the parity of a letter. $A + A + c_n = 2*A + c_n = B \pmod{10}$ can mean either

  • $c_n = 0, B = even$, or
  • $c_n = 1, B = odd$

Consider the example $xAAx + xAAx = xCBx$, where we don't care what $x$ is or whether it exists; it only serves to show we focus on two columns in local context. Since the result in both sums is different, a carry digit is involved in only one of them. This means either

  • $c_1 = 1, B = odd, A \le 4, c_2 = 0, C = even$, or
  • $c_1 = 0, B = even, A \ge 5, c_2 = 1, C = odd$

Carry digits matter, too!

Any restrictions you can deduce is progress. Consider the case $xABA + xACA = xADA$. Obviously from the first column we get $A = 0, c_1 = 0$. However, we also notice $A + A + c_2 = A$, which means $c_2 = 0$. Now we can write $B + C = D \le 9$. Imagine we later conclude $B \ge 7$. This would instantly mean $B = 7, C = 1, D = 9$. This is because we require all 3 letters to be different and $C = 0$ would result to $B = D$.

Think of the consequences when you derive a relation.

Here's a sneaky one I left out intentionally. Let's go back to $A + A + c_n = B \pmod{10}$. For the second scenario we assumed $c_n = 1$. However, if we were to mentally list the result for all possible values of $A$, we would also notice that $A \ne 9$. This is because $9 + 9 + 1 = 9 \pmod{10}$ would mean $A = B$. For the same reason, if $c_n = 0$ then $A \not= 0$.

On a similar note, from $ABC + DEF = GHI$ we can instantly say $G \ge 3$. Why? Because we require $X \ge 1$, where $X$ is any of the three leading digits. But since they're all different, the smallest sum for $G$ would be $1 + 2$. And since we have $G \le 9$, this means $A \le 8$.

With practice such patterns will become second nature. But explicitly writing every little clue, no matter how unimportant, may bring your attention to restrictions you didn't see. More importantly, as mentioned in the introduction abut the intersection of clues, you never know when or how a clue might come handy. For example, assume we have narrowed down two letters to even and greater than 5, effectively making one 6 and the other 8. If at some point you conclude a third letter must be 6, then you've reached a contradiction and can stop exploring that branch. Which leads me to...

Brute forcing is fine, too.

It's very likely you will narrow down a letter to a bunch of possible values but you can't continue. By assuming every possible value, you continue your derivation and either reach a valid solution or contradiction. The point here is to leave brute forcing for very end. Squeeze every last constraint you can from all the clues to minimise your trial and error load.

If your puzzle has 9 unique letters and you're down to the last 3, you have at most 4 possible values to choose from for each letter. In this case it's trivial to brute force one and see whether you can reach a solution for the rest.

And don't forget, if you're brute forcing for $A$ and $B$, but you already have the equation $A + B + c_3 = C$, with $C = 4, c_3 = 1, c_4 = 1$, you can rearrange it as $B = 13 - A$ and use it.

$\endgroup$
13
$\begingroup$

Some simple strategies I've found are:

  1. Look for zeroes. Any time you have $X + Y = X$ in the ones column, you know that $Y = 0$.
  2. Look for doubles. Any time you have numbers of the format $A + A = B$ in the ones column, you know that $B$ is even, and you know that either $0 < A < 5$ OR that there is a carrying one to the next column.
  3. Look for carrying ones. Any time the answer has more columns in the answer than in the problem, you know that the value in the "extra" column is a $1$. (In the example problem given, you know that $M = 1$.)

Tips 1 and 2 can work for columns other than the ones column, but make sure you consider the possibility of carrying. Also, these strategies must be modified if there are more than two "words" being added together.

Edit to add: My answer only covers a very small subset of cases, and will not solve all scenarios. Emrakul's answer describes how to translate the alphametic problem into smaller algebraic equations, and gives a sample of how to start solving the problem. Reti43's answer goes into more detail about how to find certain patterns in those algebraic equations that can help you solve it faster. While both answers are a bit technical, they are both very good reads, and far more helpful than my answer.

$\endgroup$
  • 1
    $\begingroup$ A is not necessarily restricted to less than 5 in A + A = B. For example, 7 + 7 = 4 (mod 10). However, what you do know is that there must be no carry from the addition in the previous column, or else you'd get 2*A + carry = even + odd = odd. And X + Y = X is actually X + Y + carry = X, so you can either have (Y = 0, carry = 0), or (Y = 1, carry = 1). $\endgroup$ – Reti43 Apr 23 '16 at 10:10
  • $\begingroup$ @Reti43 While that part of my answer was specifically referring to the ones column (so there can be no carry into that column), you are correct about the fact that there can be carry out of that column if A > 4. I'll update the answer to reflect that. $\endgroup$ – Xynariz Apr 25 '16 at 15:20
  • $\begingroup$ Yes, keeping it general ensures you won't ignore any solutions that involve carry digits. Obviously for the first column you start with carry = 0. By the way, I just realised that I meant Y = 9, carry = 1 above. $\endgroup$ – Reti43 Apr 25 '16 at 15:33
  • $\begingroup$ This is exactly the sort of general solution I was hoping to get when I posted this question. Feel free to post an answer with generalized solutions like that! While the brute-force approach in the accepted answer works, "intuitive guessing" strategies are ones I find easier to use. $\endgroup$ – Xynariz Apr 25 '16 at 15:39
11
$\begingroup$

The optimal way to solve this is to create linear equations of the problem.

I'll take the following problem:

K Y O T O
O S A K A + 
-----------
T O K Y O

What you need to do to solve this is to set up a sequence of linear equations that represent the carryovers and equations. I'll denote $x_n$ as the single-digit carryover, and $C_n$ as the double-digit carryover. $x_n$ must be either 0 or 1, and $C_n$ must be either $0$ or $10$. (I'm going to replace $O$ with $P$ for readability.)

What one ends up with is:

$\begin{align} P+A&=P+C_1\\ T+K&=Y+C_2-x_1\\ P+A&=K+C_3-x_2\\ Y+S&=P+C_4-x_3\\ K+P&=T-x_4\end{align}$

And an important property: $C_n=10*x_n$.

In essence, these equations represent the individual carryovers. Take the second column: $T + K = Y$, but if $Y$ has $1$ added from the carryover of $O + A$, then it needs to allow for that with $x_1$. Additionally, $10$ of the value of $T + K$ may have carried over into the next column, so one needs to add $C_2$. This is repeated for each column.

The next thing to do is set up a table of possible values, that looks something like:

A : 0 1 2 3 4 5 6 7 8 9
K : 0 1 2 3 4 5 6 7 8 9
P : 0 1 2 3 4 5 6 7 8 9
S : 0 1 2 3 4 5 6 7 8 9 
T : 0 1 2 3 4 5 6 7 8 9
Y : 0 1 2 3 4 5 6 7 8 9 

Additionally, make note of the values of $C_1$ through $C_4$ and $x_1$ through $x_4$.

There are a couple conditions to take note of, which will further restrict what the values of $A, K, P, S, T,$ and $Y$ (and therefore $C_n$ and $x_n$) can be: Primarily, no single value can be greater than nine.

At this point, it turns into a reduction of linear equations. This method is guaranteed to quickly solve any puzzle.


I'll go a couple steps into the problem here:

$P + A = P + C_1$, so $A = C_1$. We therefore know that $A = C_1 = x_1 = 0$, since $C_1$ is either $0$ or $10$. First problem solved! We update our table and equations (the first equation is now useless):

T + K = Y + C_2
P     = K + C_3 - x_2
Y + S = P + C_4 - x_3
K + P = T       - x_4

A : 0
K :   1 2 3 4 5 6 7 8 9
P :   1 2 3 4 5 6 7 8 9
S :   1 2 3 4 5 6 7 8 9 
T :   1 2 3 4 5 6 7 8 9
Y :   1 2 3 4 5 6 7 8 9 

The rest is left as an exercise to the reader. It isn't an easy problem to solve, and takes some manual reduction. However, if you'd like to verify your solution:

$A=0, K=4, P/O=3, S=2, T=7, Y=1$; $C_2=10x_1=1$; all other $C_n = 0$ The final problem becomes $41373+32040=73413$

$\endgroup$
  • 2
    $\begingroup$ Relevant nitpickery: the constraints on the values mean that this isn't just a linear system per se (at least, not of the sort that that phrase generally brings to mind, a set of equations that can be solved via gaussian elimination). Typically these sorts of systems are underconstrained (for instance, your sample problem has 5 equations in 14 unknowns!) and the constraints of both integrality and range (and sometimes uniqueness!) are absolutely essential in solving the problems. $\endgroup$ – Steven Stadnicki Jun 7 '14 at 0:52
  • 6
    $\begingroup$ This all means that they'd be more accurately called linear programming problems, and integer linear programming is actually NP-hard in the abstract (NP-complete in this case since it's obvious that a solution can be verified in polynomial time). These techniques usually work well, but I definitely wouldn't say 'guaranteed to quickly solve any puzzle' in the abstract. $\endgroup$ – Steven Stadnicki Jun 7 '14 at 0:53
  • $\begingroup$ I just wanted to mention that with the submission of (Reti43's answer)[puzzling.stackexchange.com/a/31429/11], I moved the accepted answer to his. The reason I did this is because I felt that this answer does a very good job describing how to translate the problem from alphametic to algebraic, but that his answer does a better job describing how to take that algebraic and solve it. However, I wanted to make a clear point: Both are very good answers. $\endgroup$ – Xynariz Apr 26 '16 at 17:43
  • 1
    $\begingroup$ @Xynariz Makes sense to me! No worries, and thanks! $\endgroup$ – Aza Apr 26 '16 at 18:43
1
$\begingroup$

Note that cryptarithms are NP-hard if you don't insist on base 10, see https://www.ics.uci.edu/~eppstein/pubs/Epp-SN-87.pdf.

I suspect the number 10 doesn't have any special features that make base 10 cryptarithms significantly easier than cryptarithms in any other basis, other than being small.

Thus I bet that no technique will turn the problem of solving cryptarithms into a polynomial-time problem; no technique will (in some sense) be a fundamental improvement over (pruned) brute force search.

Most likely the best way of pruning your search is finding what appears to be the most constrained letter, defaulting to right-to-left, and trying out all possibilities, aborting the current branch of your search if you run into contradictions.

The currently accepted answer has good suggestions which will guide you toward the richest sources of constraints and contradictions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.