OddThinking

Introducing Alphametics

Alphametics (aka verbal arithmetic, cryptarithmetic and others) puzzles are an old puzzle where letters are substituted for numbers in simple equations. Go search for alphametics for lots of examples.

These puzzles never really captured my fancy, which is, weirdly enough, why I recently implemented a “puzzle helper” to help solve them.

These puzzles are trivially solved on a computer through brute force. The largest ones have only about 3.6 million (= 10!) possible combinations. (Apparently, though, varying the base makes it NP-complete.)

What I did

My solver only attempts addition problems. It doesn’t do (much) brute force, and only implements a few simple constraints – not enough to solve most puzzles. However, the user can give it a prod along towards a solution.

Constraint 1: If you are the leftmost letter of a line, you are not a zero.

Fairly straightforward. If you have a 0 in the most-significant position, you would normally omit it.

Constraint 2: If you are an unsolved letter, you don’t have the same value as any of the solved letters.

Again, fairly straightforward.

Constraint 3: A letter may only have values that are plausible for the column(s) it is in.

Let me explain that further.

A column consists of a set of summands. The summands include a carry digit from the previous column. The rightmost column’s carry digit is constrained to zero.

A column also includes two output digits – representing the units column (i.e. result mod 10) and the tens column (i.e. result div 10). The tens column digit is the carry digit for the column to the left. The leftmost column’s tens column is constrained to zero.

If you go through every possible value of the summands, and look at every possible results column that gives, and cross out the ones that don’t fit given the current knowledge, you get a set of plausible values for each position in the column. Each letter is constrained to be a plausible value for each of the positions it appears in.

(Going through every possible combination of 2 or 3 digits is a bit brute-forceish. Forgive me.)

What I didn’t do

I didn’t simply brute force all of the possible combinations.

I didn’t try any fancy stuff to determine if a value could be eliminated because it was used by more than one partially-solved letters. (e.g. if A can only be either 1 or 2, and B can only be either 1 or 2, then C cannot be either 1 nor 2.)

I didn’t try to track relationships between numbers (like N = E + 1, and E can’t be 3 so N can’t be 2.)

Result

This is a puzzle before the solving engine starts. (Actually, Constraint 1 has already been applied.)

The top part of the screen shows the puzzle. The third row represents the “carry” values. I’ve used Greek letters to distinguish them from the puzzle letters. The Greek letters are not constrained to avoid conflicts – they may be the same as each other or as any other letter.

(The carry letter should probably appear slightly further to the left to match how most people write them. Forgive me.)

The bottom part shows each of the letters and their possible values in yellow.

In the running software, the yellow letters are clickable: left-click = select that value, right-click = discard that value.

[Stop Press: Can you see the bug? See comments.]

Here’s how far the software gets without human intervention.

You can see that once a letter is solved, the correct digit is substituted in in the sum at the top.

With a few choice hints from the user, we finally get to a solution.

So what?

Why did I do this puzzle if I find it so uninteresting?

Two weeks ago, I wrote:

If I was ever hired to take these disposable prototypes and replace them with massively over-engineered production code, I could certainly see the opportunity for a puzzle-solving framework (including a Prioritised Command Set) to do most of the infrastructure work.

I decided to have a stab at such a framework – and in Version 1.0, I think I have managed to avoid over-engineering it too badly.

The code is divided into three distinct areas.

The first part is the infrastructure code. It knows nothing about Alphametics. It only accounts for slightly less than 250 lines of Python, but it largely drives the structure of the rest of the code.

The second part is the Alphametic-solving code. It accounts for just over 400 lines, and is the least interesting part.

Of course, lines of code are a largely meaningless metric. I can point to about 40 of those lines of code that caused as much trouble as the rest of the code. They were the ones that implement the iteration over every legal combination of operands for Constraint 3. I completely underestimated the complexity of what was required there. My first completed implementation was totally re-written, and then again, and then again, and then again, until I finally understood what needed to be done.

The third part of the code is UI stuff. It is another 300 lines of code.

There are several things I am happy about three things in the UI code.

I managed to use the Model-View-Controller pattern to separate the UI display concerns from the puzzle-solving part. In fact, the model was already solving puzzles before there was any GUI , so I know it is independent.

The same objects (letters) are even associated with two different views (in the sum at the top, and each line of the table at the bottom). I think I will be able to display more information while retaining clarity by supporting more than one view of an object.

I have (largely) implemented Aristotle’s suggestion to have the objects redraw themselves on demand without a need for a central authority. (Still some improvements possible here.)

Finally, a small item, but it makes me happy. I now support window-resizing.

Conclusion

Alphametic puzzles aren’t my cup-of-tea, but they were useful in trialling a new puzzle-solving framework.

It still needs some work, and the proof of a framework isn’t in the first application that uses it, but in the third, so I am not crowing about it too much yet.

However, it shows some good progress.