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:
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?
Answer
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.
No comments:
Post a Comment