A friend nerd-sniped me with this problem:
send
+ more
------
money
where each letter represents a digit 0-9 and must take on a unique value.
You can of course try to solve this problem through trial and error (though there are 108 unique possibilities).
You can also try a Sudoku-style logic-based approach. You might, for example, immediately set m=1.
You can try this approach to solve the puzzle below:
If you solved it, well done! There are actually 25 valid solutions, though 24 of them set m=0, so they're not the sort of solutions most people would immediately find.
For the rest of this post, we'll focus on the one solution where m=1.
I solved this problem on pen and paper, but I wondered how we might solve this computationally.
We can of course try brute force search (108 is not very big for a computer), but is there a smarter way 1?
Think about it and if you come up with a solution, email me at daniel [at] kats [dot] coffee. I'll update this tomorrow with the answer I came up with.
Update & Computational Solution
I got a lot of very smart answers. Many of you realized that if you use the fact that the numbers must be unique, you will only search 10!/2 solutions in the worst case.
A lot of you also figured out rules to this problem such as n = e + 1, but were unsure how to make a computer learn those kinds of rules.
I implemented 3 different kinds of solutions: one brute-force, one brute-force that searches only the unique possibilities, and one using constraint search2.
In basic AI, for example in Sudoku solvers, you can express general constraints over variables (relationships between variables like all variables in a group must take unique values, or a domain constraint such as (m = 0 or m = 1)).
You can then use those constraints to dramatically speed up your search.
I implemented the most basic type: constraint search with Forward Checking (FC). The idea here is, if you know some partial assignment of variables won't work out, you don't need to try different values for other variables. For example, take a look at the partially-filled Sudoku puzzle below:
We can see that there are no possible values for the highlighted cell. There's no point in trying to solve the rest of the puzzle, we know it's not possible.
Here are the methods I implemented, together with their performance (Python3.9 on an old Macbook Pro).
| Technique | Use m=1 Trick
? | Variable Order | Time (seconds, 5 runs) | Number of Solutions Tried (5 runs) | Theoretical Worst Case |
|---|---|---|---|---|---|
| {{ isSmallScreen() ? row.run_params.solver.split('_').join('-') : row.run_params.solver }} | {{ row.run_params.letter_order }} | {{ row.results.agg.mean_time.toFixed(3) }} ± {{ row.results.agg.stdev_time.toFixed(3) }} | {{ Math.round(row.results.agg.mean_states).toLocaleString() }} ± {{ Math.round(row.results.agg.stdev_states).toLocaleString() }} |
If you tried to program a solution, you may have noticed that the order in which you try to set the variables makes a big difference. You can see this in the table above - random variable orderings produce huge fluctuations in the number of solutions tried. I also created a "worst-case" variable ordering that would get the number of states checked before a solution is found as close to the theoretical maximum as possible. In that case, the runtime is a lot more stable.
Notice that the Forward Checking technique tries only around 70 solutions before finding the correct answer, so it's extremely efficient.
In terms of constraints, I used the simple fact that for each column (for example e, o, n), either e + o (mod 10) = n,
or e + o + 1 (mod 10) = n, when you carry the 1 from the previous column.
Mod 10 here means the remainder after dividing by 10.
We can get even better results by adding constraints which prevent the leading digits from being 0.
However, for a problem of this size, using just the brute_force_uniq technique together with the m=1 trick, a pretty old laptop can find the solution in a fraction of a second.
The brute_force_uniq solution is also far simpler to write: under 25 lines of code. In contrast, the Forward Checking solution was over 100 lines.
This post has lead to a very interesting discussion on Hacker News. As folks there have pointed out, this type of puzzle is called "alphametic", and one implicit rule is solutions with leading-zero digits are invalid.
As mentioned above, Forward Checking is the most basic technique in the field of Constraint Programming (CP). Other possible techniques are Arc Consistency and Path Consistency, though these are severe overkill for our little problem. Every time I open Hacker News, I learn so much! There's an excellent comment discussing AC3 vs AC4 vs AC2001 for those interested, none of which I knew.
You can find all the code on Github.
