Enigmatic Code

Programming Enigma Puzzles

Enigma 1157: Never the same result

From New Scientist #2313, 20th October 2001

Albion, Borough, City, Rangers and United have played another tournament. This time each team played each of the other teams twice. The two matches that any two teams played against each other had different results, even in the case of City, which did not draw any of its matches.

Two points were awarded for a win and one point for a draw. After each team had played each of the other teams once, United was in the lead, one point ahead of Rangers, which was one point ahead of City, which was one point ahead of Borough, which was one point ahead of Albion.

But by the end of the tournament the positions were completely the opposite: Albion finished one point ahead of Borough, which was one point ahead of City, which was one point ahead of Rangers, which was one point ahead of United.

If you knew the results of the first match between Borough and United you could deduce with certainty the results of all the other matches played.

Give the result of the first match Borough played against each of the other four teams, naming the opponents in each match.

[enigma1157]

Enigma 354: Football again… and why, why, why?

From New Scientist #1503, 10th April 1986 [link]

In the following football table and addition sum letters have been substituted for digits (from 0 to 9). The same letter stands for the same digit wherever it appears and different letters stand for different digits.

The three teams are eventually going to play each other once — or perhaps they have already done so.

Enigma 354 - Table

(Two points are given for a win and one point to each size in a drawn match).

Enigma 354 - Sum

Find the scores in the football matches and write the addition sum out with numbers substituted for letters.

[enigma354]

Enigma 1158: Anti-Magic

From New Scientist #2314, 27th October 2001

George quickly solved the popular magic square puzzle which asks you to arrange the numbers 1 to 16 in a 4 × 4 grid so that the four rows. the four columns and the two diagonals all have the same sum — so he tried to be different. He has now found an “Anti-Magic Square”, using the numbers 1 to 16, but the ten totals are all different. They are in fact ten consecutive numbers, but in no particular sequence in relation to the square grid.

One of the diagonals in George’s square contains four consecutive numbers and the other contains four prime numbers, each in ascending numerical order from top to bottom.

One row contains four numbers in ascending numerical order from left to right.

What are those four numbers?

Enigma 8 was also about anti-magic squares.

[enigma1158]

Enigma 353: Up the polls

From New Scientist #1502, 3rd April 1986 [link]

When electing a mayor, our town councillors each vote for one of the candidates, and if a candidate obtains over half the votes in this first count he is elected. If this fails to happen, then the candidate with the least votes “donates” his votes entirely to one of the remaining candidates and takes no further part of the procedure.

The new totals are then calculated and if one candidate has over half the votes, or if a candidate has been first in the two counts, then he is elected. If both those fail to happen, then again the candidate with fewest votes in the second count donates his votes to one of the remaining candidates and retires. This continues until someone has over half the votes or has been top in any two counts.

When the current mayor was elected the 31 counsellors each voted for their choice of one of the five candidates, and each candidate received a different number (but less than half) of the votes. So the candidate with fewest votes donated his and retired. The second count gave a new clear leader, but it was still indecisive. The third account gave a new clear leader, but it too was still indecisive. At last, on the fourth count, the mayor was elected, and in none of the counts had he been placed second.

How many votes did that mayor get in the very first vote?

[enigma353]

Enigma 1159: Measure for measure

From New Scientist #2315, 3rd November 2001

I bought a few yards of expensive material recently and I suspected that I had been short-measured. So I took it to the local trading standards officer who measured it exactly in inches. She did not tell me the exact length but she did tell me that it involved two decimal places.

She then told me what the length was to the nearest inch (where exact halves are rounded up) and this did equal the whole number of yards which I had purchased.

Also, as required by a European directive, she changed her exact measurement in inches to centimetres (1 inch = 2.54 centimetres) and she told me the length of the material to the nearest centimetre.

From the things which she told me I was in fact able to work out the exact length of the material in inches and to see that I had actually been sold slightly more material than I had asked for.

How many yards of material had I asked for?

[enigma1159]

Enigma 352: In the bag

From New Scientist #1501, 27th March 1986 [link]

Yesterday, I was presented with an unusual box containing 13 painted Easter eggs. Each egg was either red, white or blue and there was at least one egg of each colour. If I had been in a dark room, the minimum number of eggs I would have had to withdraw from the box to be certain of picking at least three eggs of the same colour was the same as the number of blue eggs in the box.

Being superstitious, I decided against leaving 13 eggs in the box and transferred a number to a black bag. This bag may not have been empty before I added the coloured eggs. If it wasn’t, then it contained one or more black eggs and nothing else. However, two things are certain. One is that if I were in a dark room, the minimum number of eggs I would now have to withdraw from the box to be sure of having at least three eggs of the same colour is the same as the number of blue eggs in the bag. The second is that the chances of picking out a white egg from the bag with one attempt are the same as the chances of picking out a white egg from the box with one attempt.

But I am in a dark room. Trying to deduce the contents of that black back without turning the light on and looking is keeping me awake late into the night.

How many red, white, blue and black (if any) eggs are there in the bag?

[enigma352]

Enigma 1160: Sum logic

From New Scientist #2316, 10th November 2001

Enigma 1160

Joe made this puzzle for his son. It consists of nine small squares in a square tray. As shown, one square is marked with a plus sign and the rest numbered 1 to 8. The puzzle involves removing the plus sign and then sliding a square into the space left by the plus sign.

From then on each move consists of sliding a square into a vacant space and finally replacing the plus sign in its original position. As shown the numbers do not add up. 123 + 45 does not equal 678. The object of the puzzle is to finish so the numbers do add up.

In how many different ways can this be achieved?

[enigma1160]

Enigma 351: Four flies

From New Scientist #1500, 20th March 1986 [link]

Four unfriendly flies are sitting watching the cricket. Each is on the boundary of the ground, which is perfectly circular. Their names, in order round the edge, are At, Bet, Cot and Dut.

The length of each of the straight lines At-Bet, Bet-Cot, Cot-Dut and Dut-At is an exact whole number of flymins (this is, the flies’ unit of distance). Two of those lines actually have the same length. Furthermore, the total of these four lengths is precisely the same number as the area (in square flymins) of the quadrilateral At-Bet-Cot-Dut.

If I tell you that that area does not include the pitch (which is at the centre of the ground), can you tell me the four lengths?

[enigma351]

Solving Alphametics with Python, Part 2

In my previous article (Solving Alphametics with Python) I explored some possibilities for improving on the speed of a simple algorithm for solving general Alphametic expressions using Python’s eval() function. I implemented a way of solving Alphametics without calling eval() for every potential letter-to-digit assignment, and also a way of reducing the number of possibilities we need to consider in the common case of expressions involving equality.

That article received a comment from Arthur Vause, in which he shared his own program that addresses the problem of repeated calls to eval() by writing code that generates a program that considers the possibilities, and then getting Python to execute that.

I’ve taken this idea a bit further and instead of having code that generates a relatively short program, instead it can generate a series of nested loops and if statements with all the logic of the valid/invalid assignments built into the structure of the generated program itself. This gives us something that may not look elegant, but executes quickly, (and can be handled by PyPy without problems).

So, for a problem like Enigma 1530:

TOM × 13 = DALEY

my code produces a program like this:

def solve():
  for T in [1, 2, 3, 4, 5, 6, 7, 8, 9]:
    for O in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:
      if O != T:
        for M in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:
          if M != T and M != O:
            TOM = M + O*10 + T*100
            x = TOM * 13
            (x, Y) = divmod(x, 10)
            if Y != T and Y != O and Y != M:
              (x, E) = divmod(x, 10)
              if E != T and E != O and E != M and E != Y:
                (x, L) = divmod(x, 10)
                if L != T and L != O and L != M and L != Y and L != E:
                  (x, A) = divmod(x, 10)
                  if A != T and A != O and A != M and A != Y and A != E and A != L:
                    (x, D) = divmod(x, 10)
                    if D != T and D != O and D != M and D != Y and D != E and D != L and D != A and D != 0 and x == 0:
                      yield { 'A': A, 'D': D, 'E': E, 'L': L, 'M': M, 'O': O, 'T': T, 'Y': Y }

(This is a slightly simplified version, but you get the idea).

Firstly, this code isn’t elegant. But we don’t really care about that in this instance. No-one is going to look at it, it’s just going to be executed. (I know I have asked you to look at it in this post).

Here’s an explanation of how the generated program works:

(Lines 2-6)

In this example, the only letters we need to consider the values of are T, O, and M, and instead of using itertools.permutations() and rejecting assignments with invalid digits we don’t need to generate possibilities with invalid assignments in the first place.

For example, we don’t need to consider the possibility of T being zero (because leading zeros are not allowed), so we don’t put 0 in the possible values of T. Any other invalid digits assignments can be removed in the same way.

(Lines 7-8)

Once we have the values of T, O, M, we construct the value of TOM and calculate the left-hand side of the expression (TOM × 13).

(Lines 9-18)

We then try and match this result to the value we are looking for (DALEY), by repeatedly examining the final digit. For each digit we examine we either match it an existing assignment (if it is a letter we have already seen), or we check that it is a new assignment (if it is a letter we haven’t already seen).

In this case, all the letters are new, so we just need to check that their values don’t reuse any of the digits we have already assigned. When we get to the leading digit (D) we also need to check that it is non-zero, and that we have used up all the digits of the result.

(Line 19)

If we make it through all that we have found a solution, so we return a dictionary mapping the letters to the digit values.

This approach can easily deal with multiple expressions in a single program — once we have finished with one expression we just generate the code for the next one until all expressions are exhausted. If we reach the end when the code is executed all the expressions are satisfied, and we can return the dictionary for the solution.

I’ve implemented this approach in the enigma.py library (from version 2016-06-25), as the function substituted_expression() and changed the SubstitutedExpression() solver to use this.

Comparative timings are given in the table below, using the examples from the previous article.

The columns are:

1 = Raymond Hettinger’s code, using repeated calls eval() for a single expression, multiple expressions are chained together using “and”. The code is modified so that single digit 0 values are allowed. Note: This can’t deal with expressions in bases other than 10.

2 = The previous version of the enigma.py code, as described in the previous article. It uses a single call to eval() for a single expression, but can chain individual expression solutions together to solve problems involving multiple expressions.

3 = The current version of the enigma.py code, as described in this article. Multiple expressions can be evaluated in a single call to eval().

4 = The SubstitutedSum() solver form the enigma.py library. This can only deal with expressions that are simple sums (but can chain expressions together, operate in different bases and allow initial assignments and invalid assignments).

    1      2      3      4    test
 94.4s   4.6s   0.32s  0.19s  (LBRLQQR + LBBBESL + LBRERQR + LBBBEVR = BBEKVMGL)
 75.0s   0.44s  0.07s  0.07s  (HMPDM + BHPHM = RCDHA) (RBAD + PQHD = AADD)
 92.7s   4.2s   0.37s  ----   (SAND + SUN + SEX + SEA = IBIZA) (SAND > SUN > SEX > SEA)
  2.6s   0.93s  0.11s  ----   (PAY + ASP + YES + ERR + RYE + SPA = YAPS) (P < A < Y < E < R < S)
 32.0s   0.22s  0.04s  ----   (TOM * 13 = DALEY)
 45.7s   0.26s  0.04s  ----   (CUT + UTC + TCU = MEDS) ((RIO + IOR + ORI) * MEDS = OMTTOUI)
 47.0s   1.1s   0.14s  ----   ((ENI * GMA) % 1000 = MES) (ENI + GMA = SUM) (I > 2 * U)
109.2s   8.6s   0.99s  ----   (ALPHA + BETA + GAMMA = DELTA) (ALPHABET % 26 = 0) (ALPHABET % 24 = 0) (GAMMA % 3 = 0)
 85.3s   0.19s  0.04s  ----   (ENIG * MA == AM * gIne) (E - N - M == M - n - e) (N == n + n) (IN == nI + nI)
 ----    7.6s   0.55s  0.31s  (GOLD + DALEY = THOMAS) [base=11]
 ----	55.6s	0.96s  0.08s  (FAREWELL + FREDALO = FLINTOFF) [base=11]
107.9s   2.9s   0.40s  0.07s  (ELGAR + ENIGMA = NIMROD) [O=0]
134.6s   1.3s   0.24s  0.09s  (WILKI + NSON = JONNY) [no digit is 9]
 87.2s   0.48s  0.05s  0.08s  (1939 + 1079 = 6856) [digits cannot stand for themselves]
 78.4s   0.55s  0.08s  ----   (BRAIN + STRAIN + AGAIN = ENIGMA) (is_cube(ATE))
 74.1s   2.6s   0.16s  ----   (ETA + BETA + THETA = DELTA) (is_prime(PHI)) (is_prime(PSI))
109.6s   0.72s  0.05s  ----   (SEVEN - THREE = FOUR) (is_prime(SEVEN)) (is_prime(FOUR)) (is_prime(RUOF)) (is_square(TEN))
 55.5s   0.44s  0.06s  ----   (M * TIMES = ENIGMA)
 92.0s  12.7s   0.61s  0.10s  (SAINT + GEORGE = DRAGON) (E % 2 = 0)
 59.0s   0.45s  0.06s  ----   (AB * CDE = FGHIJ) (AB + CD + EF + GH + IJ = CCC)

As we see, the approach described in this article is generally hundreds of times faster than the repeated eval() approach, and in some tests more than 2000× faster. It is also generally tens of times faster than the approach described in the previous article. In fact it solves each of the example problems in less than 1s and can solve all of the given example Alphametics in less than 6s total runtime.

If you want to see the actual code that is generated by the solver for a particular problem you can pass a value of 3 or more to the verbose parameter of the solver. e.g.:

% python enigma.py Alphametic -v3 "TOM * 13 = DALEY"
...

And the code (as well as some other debugging information) will be output before the solutions.

Thanks for reading.

Enigma 1161: Shifty division

From New Scientist #2317, 17th November 2001

In a previous Enigma, George asked you to find the smallest number which can be multiplied by four simply by moving the last digit to the front. The answer is 102564 × 4 = 410256. In fact, 102564 is the smallest number which can be multiplied by any integer by moving its last digit to the front.

George is now trying to find numbers which can be divided exactly by some integer (any integer greater than one) simply by moving the last digit (which must not be zero) to the front. He has found two solutions to this puzzle and checked them on his eight-digit calculator. He is now looking for another.

What is the smallest number which George has not yet found which can be divided by some factor using this trick?

[enigma1161]

Enigma 350: Oh, careless pen!

From New Scientist #1499, 13th March 1986 [link]

Four football teams (A, B, C and D) are to play each other once. After some of the matches had been played a table was drawn up giving some details of the matches played, won, lost and so on.

Unfortunately, not only had the digits been replaced by letters, but also (Uncle Bungle and his careless pen again!) one of the letters was wrong on one of the occasions on which it appeared — if it appeared more than once.

The table looked like this:

Enigma 350

(Two points are given for a win, and one point to each side in a drawn match).

Which letter was wrong? What should it be? Find the score in each match.

[enigma350]

Solving Alphametics with Python

Many Enigma puzzles use Alphametics (or Cryptarithms — see the Wikipedia page on Verbal Arithmetic for other terms), where a sum (or other expression) is given with the numbers consistently substituted for letters (or sometimes other symbols).

For example, Enigma 63, consists of solving the following Alphametic sum:

LBRLQQR + LBBBESL + LBRERQR + LBBBEVR = BBEKVMGL.

By the time I came to solving this puzzle I had got a bit bored with writing programs to solve specific Alphametic sum problems, and decided it would be more fun to write a generic solver that could be used to solve any such substituted sum problem. The result was the SubstitutedSum() class in the enigma.py library, which allows various variations on Alphametic sums to be solved in a fairly efficient way.

(The code itself considers the columns of the sum moving from right to left, and when dealing with each column it looks at the possible substitutions for the symbols remaining unassigned in that column, and when it finds a suitable assignment it moves on to the next column to the left).

Later, I added the ability to invoke it directly from the command line, so for simple problems (like Enigma 63) it is not even necessary to write a program:

% python enigma.py SubstitutedSum "LBRLQQR + LBBBESL + LBRERQR + LBBBEVR = BBEKVMGL"
LBRLQQR + LBBBESL + LBRERQR + LBBBEVR = BBEKVMGL
8308440 + 8333218 + 8302040 + 8333260 = 33276958 / B=3 E=2 G=5 K=7 L=8 M=9 Q=4 R=0 S=1 V=6

This runs in 0.14s, which was actually faster than my original programmed solution.


This is all very well (and fast) for Alphametic problems which are simple addition sums, but what about more complication problems. Enigma 1530, for instance, is a multiplication problem, and while it can be solved using SubstitutedSum() by turning the multiplication sum into a repeated addition I was interested in a solver that will work on arbitrary Python expressions.

There is such a solver (originally by Raymond Hettinger) which appears in several places on the web. The gist of it is to generate all the possible assignments of letters to digits, then substitutes them into the expression and call Python’s eval() function on it. In pseudo-code:

# solve <expr> as an alphametic expression
def solve(expr):

  # extract the letters from expr
  letters = <letters occurring in expr>

  # consider possible assignments for each letter
  for digits in permutations('0123456789', len(letters)):

    # replace letters with corresponding digits
    new_expr = <expr with <letters> replaced by <digits>>

    if eval(new_expr):
      # output the solution
      <output solution>

This is obviously much slower than a specialised solver, as it can consider up to 10! = 3,628,800 different assignments of letters to digits, and then it calls eval() on each one. Each call to eval() will involve a parsing, compiling and finally execution stage.

While this is undoubtedly a very concise piece of code, that does indeed allow for the solving of arbitrary Alphametic expressions there are a couple of problems with it in general use.

Firstly (as previously mentioned), it is a bit slow. Generally it takes about a minute to consider all the possible assignments of 10 different digits to 10 letters (depending on the complexity of the expression).

Usually, my first weapon of choice to speed up Python programs is to try running them using PyPyUnfortunately programs that make heavy use of eval() don’t benefit from the speed increases of PyPy, and my test program ran about 2.5× faster under CPython than under PyPy.

Secondly it isn’t that easy to extend it to incorporate the additional features that I added in to SubstitutedSum() (like solving in a different base, or specifying which assignments are allowed (to allow solutions using leading zeros), etc).

The code as published removes leading zeros from consideration (and the way it is written it will also exclude 0 itself as a standalone digit, which may or may not be what you want). If you try to allow leading zeros you run into problems. A literal of the form 072 is a Syntax Error in Python 3, and in Python 2 it evaluates to 58 as it is assumed to be octal, neither of which is particularly helpful behaviour in this situation.

Instead my SubstitutedExpression() code takes the initial expression, and replaces the words in it with placeholder arguments. It then uses eval() once to parse and compile a function that takes the numerical values of each word in the original expression. It then generates all the possible letter-to-digit assignments, generates the numbers that correspond to the words in the expression and passes those to the compiled function to see if the original expression is satisfied.

The pseudo-code for this is:

# solve <expr> as an alphametic expression
def solve(expr):

  # replace the words in expr with placeholders
  (body, words) = replace_words(expr)

  # make an executable function from <body>
  fn = eval("lambda <args>: <body>")

  # extract the letters in the words
  letters = <letters in <words>>

  # consider possible assignments for each letter
  for digits in permutations(irange(0, 9), len(letters)):

    # map the words to numbers using the digits
    args = list((<word> with <letters> replaced by <digits>) for <word> in <words>)

    # compute the result of the expression
    if fn(args):
      <output solution>

This works well, and allows us to use PyPy to gain a speed increase, and also to consider numbers in bases other than 10 and to allow leading zeros, as well as supporting the other bells and whistles carried over from the SubstitutedSum() solver.

It is however still slower than it needs to be in many cases. For instance, in Enigma 1530, we need to solve the (partial) Alphametic multiplication sum: TOM × 13 = DALEY. The whole expression has 8 letters that need to be substituted for digits, potentially requiring us to look at 10×9×8×7×6×5×4×3 = 1,814,400 possible assignments. But if we look at just the left hand side of the sum, there are only 3 letters in: TOM × 13, which only requires looking at 10×9×8 = 720 possible assignments. For each of those assignments we can look at the resulting product and then try and match it against the Alphametic result of: DALEY. Thereby reducing the number of possibilities we need to consider by a factor of 2,520.

The pseudo-code now looks something like this:

# solve <expr> = <value> as an alphametic equation
def solve(expr, value):

  # replace the words in expr with placeholders
  (body, words) = replace_words(expr)

  # make an executable function from <body>
  fn = eval("lambda <args>: <body>")

  # extract the letters in the words
  letters = <letters in <words>>

  # consider possible assignments for each letter
  for digits in permutations(irange(0, 9), len(letters)):

    # map the words to numbers using the digits
    args = list((<word> with <letters> replaced by <digits>) for <word> in <words>)

    # compute the result of the expression
    result = fn(args)

    # does the result match <value>
    solution = match(value, result)
    if solution:
      <output solution>

(While this approach appears to limit us to only considering Alphametic expressions of the form: <expr> = <value>, where <value> is a single literal (either an Alphametic “word” or an integer literal), this is not really a restriction, since boolean expressions evaluate to 0 or 1 we can treat any expression that doesn’t follow this pattern as: bool(<expr>) = 1, and we are back to an expression of the form: <expr> = <value>).

This is basically the approach I have used in the implementation of the SubstitutedExpression() solver in the enigma.py library (and I’ve allowed Alphametic() to be used as an alias for it to save typing). It can be invoked directly from the command line, so for many problems it is not necessary to write a separate program.

I have also allowed for several Alphametic expressions to be solved simultaneously. The solution (mapping from letters to digit values) that is generated from the first is used as a starting point for the second expression, and so on until all of the expressions are satisfied. The solver includes a heuristic algorithm to decided what order the expressions should be evaluated to try and minimise the number of possible assignments considered. (Although you can turn off the reordering if you prefer).

These are the command line arguments that can be used:

% python enigma.py Alphametic --help
usage: SubstitutedExpression [<opts>] <expression> [<expression> ...]
options:
 --symbols=<string> (or -s<string>) = symbols to replace with digits
 --base=<n> (or -b<n>) = set base to <n>
 --assign=<letter>,<digit> (or -a<l>,<d>) = assign digit to letter
 --digits=<digit>,... or --digits=<digit>-<digit> (or -d...) = available digits
 --invalid=<digit>,<letters> (or -i<d>,<ls>) = invalid digit to letter assignments
 --first (or -1) = stop after the first solution
 --reorder=<n> (or -r<n>) = allow reordering of expressions (0 = off, 1 = on)
 --verbose[=<n>] (or -v[<n>]) = verbosity (0 = off, 1 = solutions, 2 = more)
 --help (or -h) = show command-line usage

Here are some examples of Alphametic Enigma problems that can be solved directly using the SubstitutedExpression() solver from the command line. (I use the Alphametic alias to make the command line more compact):


First we solve a simple Alphametic sum — Enigma 63:

LBRLQQR + LBBBESL + LBRERQR + LBBBEVR = BBEKVMGL.

% pypy enigma.py Alphametic "LBRLQQR + LBBBESL + LBRERQR + LBBBEVR = BBEKVMGL"
(LBRLQQR + LBBBESL + LBRERQR + LBBBEVR = BBEKVMGL)
(8308440 + 8333218 + 8302040 + 8333260 = 33276958) / B=3 E=2 G=5 K=7 L=8 M=9 Q=4 R=0 S=1 V=6

This runs in 4.8s, so the SubstitutedSum() solver is over 30× faster in this case.


A more complex problem, consisting of two simultaneous Alphametic sums is given in Enigma 5:

HMPDM + BHPHM = RCDHA,
RBAD + PQHD = AADD.

% pypy enigma.py Alphametic "HMPDM + BHPHM = RCDHA" "RBAD + PQHD = AADD"
(HMPDM + BHPHM = RCDHA) (RBAD + PQHD = AADD)
(24504 + 12524 = 37028) (3180 + 5620 = 8800) / A=8 B=1 C=7 D=0 H=2 M=4 P=5 Q=6 R=3

This runs in 0.46s. The same problem can be handled by the SubstitutedSum() solver in 0.045s, which is 10× faster.


Enigma 1407 has an Alphametic sum and an additional condition:

SAND + SUN + SEX + SEA = IBIZA,
SAND > SUN > SEX > SEA.

% pypy enigma.py Alphametic "SAND + SUN + SEX + SEA = IBIZA" "SAND > SUN > SEX > SEA"
(SAND + SUN + SEX + SEA = IBIZA) (SAND > SUN > SEX > SEA)
(9304 + 970 + 956 + 953 = 12183) (9304 > 970 > 956 > 953) / A=3 B=2 D=4 E=5 I=1 N=0 S=9 U=7 X=6 Z=8
(9306 + 970 + 954 + 953 = 12183) (9306 > 970 > 954 > 953) / A=3 B=2 D=6 E=5 I=1 N=0 S=9 U=7 X=4 Z=8

This takes 4.1s vs. 0.34s for my programmed solution.


Enigma 1664 is a similar problem:

PAY + ASP + YES + ERR + RYE + SPA = YAPS,
P < A < Y < E < R < S.

% pypy enigma.py Alphametic "PAY + ASP + YES + ERR + RYE + SPA = YAPS" "P < A < Y < E < R < S"
(PAY + ASP + YES + ERR + RYE + SPA = YAPS) (P < A < Y < E < R < S)
(123 + 291 + 369 + 688 + 836 + 912 = 3219) (1 < 2 < 3 < 6 < 8 < 9) / A=2 E=6 P=1 R=8 S=9 Y=3

This runs in 0.9s vs. 0.03s for my programmed solution.


Enigma 1530 is a multiplication problem:

TOM × 13 = DALEY.

% python enigma.py Alphametic "TOM * 13 = DALEY"
(TOM * 13 = DALEY)
(796 * 13 = 10348) / A=0 D=1 E=4 L=3 M=6 O=9 T=7 Y=8

This takes 0.08s vs. 0.04s for a programmed solution using SubstitutedSum(), so it is only 2× faster.


Enigma 323 has two Alphametic sums, although the exact answer is not given for the second one:

CUT + UTC + TCU = MEDS,
RIO + IOR + ORI = <missing>,
MEDS × <missing> = OMTTOUI.

% pypy enigma.py Alphametic "CUT + UTC + TCU = MEDS" "(RIO + IOR + ORI) * MEDS = OMTTOUI"
(CUT + UTC + TCU = MEDS) ((RIO + IOR + ORI) * MEDS = OMTTOUI)
(487 + 874 + 748 = 2109) ((563 + 635 + 356) * 2109 = 3277386) / C=4 D=0 E=1 I=6 M=2 O=3 R=5 S=9 T=7 U=8

This runs in 0.25s, compared to 0.04s for my programmed solution.


Enigma 253 has a sum, a product and a condition.

ENI + GMA = SUM,
ENI × GMA = ??MES,
I > 2 × U.

This one is faster if we order the expressions ourselves.

% pypy enigma.py Alphametic --reorder=0 "(ENI * GMA) % 1000 = MES" "ENI + GMA = SUM" "I > 2 * U"
(ENI + GMA = SUM) ((ENI * GMA) % 1000 = MES) (I > 2 * U)
(279 + 156 = 435) ((279 * 156) % 1000 = 524) (9 > 2 * 3) / A=6 E=2 G=1 I=9 M=5 N=7 S=4 U=3

This runs in 1.2s. If we let the solver choose the ordering of the clauses it takes 2.2s. My programmed solution (which uses SubstitutedSum()) takes 0.09s.


Enigma 1261 has an Alphametic sum with several additional conditions:

ALPHA + BETA + GAMMA = DELTA,
24 and 26 divide ALPHABET,
3 divides GAMMA.

Again, we get a faster solution if we order the clauses ourselves:

% pypy enigma.py Alphametic --reorder=0 "ALPHABET % 26 = 0" "ALPHABET % 24 = 0" "ALPHA + BETA + GAMMA = DELTA" "GAMMA % 3 = 0"
(ALPHABET % 26 = 0) (ALPHABET % 24 = 0) (ALPHA + BETA + GAMMA = DELTA) (GAMMA % 3 = 0)
(56375904 % 26 = 0) (56375904 % 24 = 0) (56375 + 9045 + 15225 = 80645) (15225 % 3 = 0) / A=5 B=9 D=8 E=0 G=1 H=7 L=6 M=2 P=3 T=4

This takes 8.6s. If we let the solver choose the ordering of the clauses it take 13s. These compare with 0.06s for my programmed solution.


Enigma 245 uses some symbols that are not standard capital letters. We use “e”, “n” and “g” to stand for the reversed capitals, and we can specify these on the command line argument:

ENIG × MA = AM × gIne,
E − N − M = M − n − e,
N = n + n,
IN = nI + nI.

% pypy enigma.py Alphametic --symbols=ENIGMAeng "ENIG * MA == AM * gIne" "E - N - M == M - n - e" "N == n + n" "IN == nI + nI"
(ENIG * MA == AM * gIne) (E - N - M == M - n - e) (N == n + n) (IN == nI + nI)
(6895 * 12 == 21 * 3940) (6 - 8 - 1 == 1 - 4 - 0) (8 == 4 + 4) (98 == 49 + 49) / A=2 E=6 G=5 I=9 M=1 N=8 e=0 g=3 n=4

It runs in 0.2s compared with 0.03s for my programmed solution.


We can solve problems in number bases other than 10, e.g. Enigma 1581: 

THOMAS − DALEY = GOLD (in base 11).

I’ve rearranged the expression into an addition sum to reduce the number of free symbols on the left hand side of the expression (GOLD + DALEY only has 7 free symbols, THOMAS − DALEY has 10).

% pypy enigma.py Alphametic --base=11 "GOLD + DALEY = THOMAS"
(GOLD + DALEY = THOMAS)
(639A + A7985 = 103274) / A=7 D=10 E=8 G=6 H=0 L=9 M=2 O=3 S=4 T=1 Y=5

This runs in 9.5s vs. 0.33s using SubstitutedSum() (which can also solve problems in different bases).

Note that the letter A appears both as a symbol to be substituted and a digit in base 11 numbers, so there is the possibility of confusion. We could eliminate it completely by using lowercase letters for the symbols:

% pypy enigma.py Alphametic --base=11 --symbols=adeghlmosty "gold + daley = thomas" 
(gold + daley = thomas)
(639A + A7985 = 103274) / a=7 d=10 e=8 g=6 h=0 l=9 m=2 o=3 s=4 t=1 y=5

A similar approach works for Enigma 1663:

FAREWELL + FREDALO = FLINTOFF (in base 11).

% pypy enigma.py Alphametic --symbols=adefilnortw --base=11 "farewell + fredalo = flintoff" 
(farewell + fredalo = flintoff)
(6157A788 + 6573189 = 68042966) / a=1 d=3 e=7 f=6 i=0 l=8 n=4 o=9 r=5 t=2 w=10
(61573788 + 657A189 = 68042966) / a=1 d=10 e=7 f=6 i=0 l=8 n=4 o=9 r=5 t=2 w=3

This runs in 55s. The SubstitutedSum() solver takes 0.08s.


Enigma 1361 gives us one of the assignments to start with:

ELGAR + ENIGMA = NIMROD.

We can add the assignment as an additional clause:

% pypy enigma.py Alphametic "ELGAR + ENIGMA = NIMROD" "O = 0"
(ELGAR + ENIGMA = NIMROD) (O = 0)
(71439 + 785463 = 856902) (0 = 0) / A=3 D=2 E=7 G=4 I=5 L=1 M=6 N=8 O=0 R=9

This runs in 2.6s.

Or we can solve it in a single expression and assign the letter O using a command line option:

% pypy enigma.py Alphametic -v2 --assign=O,0 "ELGAR + ENIGMA = NIMROD"
(ELGAR + ENIGMA = NIMROD)
(71439 + 785463 = 856902) / A=3 D=2 E=7 G=4 I=5 L=1 M=6 N=8 O=0 R=9

Which also runs in 2.6s.

The –assign option also works in the SubstitutedSum() solver, which solves this problem in 0.07s.


We can specify which digit are available — in Enigma 1272 the digit 9 is not used:

JONNY = WILKI + NSON.

We also re-order the sum so that the expression is on the left hand side of the equals sign.

% pypy enigma.py Alphametic --digits=0,1,2,3,4,5,6,7,8 "WILKI + NSON = JONNY" 
(WILKI + NSON = JONNY)
(48608 + 3723 = 52331) / I=8 J=5 K=0 L=6 N=3 O=2 S=7 W=4 Y=1
(48708 + 3623 = 52331) / I=8 J=5 K=0 L=7 N=3 O=2 S=6 W=4 Y=1

This runs in 1.3s compared to 0.05s using the SubstitutedSum() solver.


Enigma 171 is a problem that uses numbers for symbols, but the numbers cannot stand for themselves:

1939 + 1079 = 6856.

We can handle this directly in the solver:

% pypy enigma.py Alphametic -s01356789 -i0,016 -i1,1 -i3,3 -i5,5 -i6,6 -i7,7 -i8,8 -i9,9 "1939 + 1079 = 6856"
(1939 + 1079 = 6856)
(2767 + 2137 = 4904) / 0=1 1=2 3=6 5=0 6=4 7=3 8=9 9=7

This runs in 0.5s vs. 0.08s using the SubstitutedSum() solver.

However there is possible ambiguity here. The value on the right hand side of the expression is interpreted either as a “word” (composed of symbols) or an integer literal (composed of numbers). In this case we could interpret the value in either way. The solver will interpret it as a “word” if it is entirely composed of symbols, otherwise it will try and parse it as a number (in the specified base). If both these approaches fail it will raise an error.

It might be better to rename the symbols to avoid any clash. Here is the same problem with the letters abcdefgh used instead of the digits 01356789.

% pypy enigma.py Alphametic -sabcdefgh -i0,abe -i1,b -i3,c -i5,d -i6,e -i7,f -i8,g -i9,h "bhch + bafh = egde"
(bhch + bafh = egde)
(2767 + 2137 = 4904) / a=1 b=2 c=6 d=0 e=4 f=3 g=9 h=7

Enigma 94 has an Alphametic sum and an additional condition.

BRAIN + STRAIN + AGAIN = ENIGMA,
ATE is a perfect cube.

Any of the functions defined in enigma.py is available for use in expressions.

% pypy enigma.py Alphametic "BRAIN + STRAIN + AGAIN = ENIGMA" "is_cube(ATE)"
(BRAIN + STRAIN + AGAIN = ENIGMA) (is_cube(ATE))
(98234 + 518234 + 27234 = 643702) (is_cube(216)) / A=2 B=9 E=6 G=7 I=3 M=0 N=4 R=8 S=5 T=1

This runs in 0.6s, compared to 0.04s for my programmed solution using SubstitutedSum().


Enigma 1627 has an Alphametic sum and some additional conditions.

ETA + BETA + THETA = DELTA,
PHI is prime,
PSI is prime.

% pypy enigma.py Alphametic "ETA + BETA + THETA = DELTA" "is_prime(PHI)" "is_prime(PSI)"
(ETA + BETA + THETA = DELTA) (is_prime(PHI)) (is_prime(PSI))
(250 + 8250 + 54250 = 62750) (is_prime(149)) (is_prime(139)) / A=0 B=8 D=6 E=2 H=4 I=9 L=7 P=1 S=3 T=5

This runs in 2.5s, compared with 0.045s for my programmed solution.


Enigma 1180 has a subtraction sum, and then several constraints on various numbers formed from substituted words:

SEVEN − THREE = FOUR,
SEVEN is prime,
FOUR is prime,
RUOF is prime,
TEN is square.

% pypy enigma.py Alphametic "SEVEN - THREE = FOUR" "is_prime(SEVEN)" "is_prime(FOUR)" "is_prime(RUOF)" "is_square(TEN)" 
(SEVEN - THREE = FOUR) (is_prime(SEVEN)) (is_prime(FOUR)) (is_prime(RUOF)) (is_square(TEN))
(62129 - 58722 = 3407) (is_prime(62129)) (is_prime(3407)) (is_prime(7043)) (is_square(529)) / E=2 F=3 H=8 N=9 O=4 R=7 S=6 T=5 U=0 V=1

This runs in 0.72s compared with 0.06s for my programmed solution.


Enigma 1000 is a division sum:

ENIGMA / M = TIMES.

We can specify this as a full expression (using == as the right hand side of the expression is not a “word” or an integer literal):

% pypy enigma.py Alphametic --invalid=0,EMT "divmod(ENIGMA, M) == (TIMES, 0)"                                                           
(divmod(ENIGMA, M) == (TIMES, 0))
(divmod(180426, 2) == (90213, 0)) / A=6 E=1 G=4 I=0 M=2 N=8 S=3 T=9

This runs in 7.8s.

Or we can re-write the expression to make it more friendly for the solver:

% pypy enigma.py Alphametic --invalid=0,EMT "M * TIMES = ENIGMA"                                       
(M * TIMES = ENIGMA)
(2 * 90213 = 180426) / A=6 E=1 G=4 I=0 M=2 N=8 S=3 T=9

This runs in 0.45s, which compares to 0.042s for my programmed solution.


Here’s the solver let loose on a couple of recent Sunday Times Teaser puzzles:

Sunday Times Teaser 2796

SAINT + GEORGE = DRAGON,
GEORGE is even.

% pypy enigma.py Alphametic "SAINT + GEORGE = DRAGON" "E % 2 = 0"
(SAINT + GEORGE = DRAGON) (E % 2 = 0)
(72415 + 860386 = 932801) (6 % 2 = 0) / A=2 D=9 E=6 G=8 I=4 N=1 O=0 R=3 S=7 T=5

This runs in 8.8s, compared with 0.1s for a programmed solution.


Sunday Times Teaser 2803

AB × CDE = FGHIJ,
AB + CD + EF + GH + IJ = CCC.

% pypy enigma.py Alphametic "AB * CDE = FGHIJ" "AB + CD + EF + GH + IJ = CCC"
(AB * CDE = FGHIJ) (AB + CD + EF + GH + IJ = CCC)
(52 * 367 = 19084) (52 + 36 + 71 + 90 + 84 = 333) / A=5 B=2 C=3 D=6 E=7 F=1 G=9 H=0 I=8 J=4

This runs in 0.5s vs. 0.15s for my programmed solution.


We can see, then, that many Enigma puzzles (and other similar puzzles) can be solved directly using the SubstitutedSum() and SubstitutedExpression() solvers, often with only a few seconds of run time, and while that may be slower in execution time than writing a custom program to solve the puzzle, the amount of time saved in not writing a custom program is more than made up for.

The Alphametic solvers are available as part of the enigma.py library for solving puzzles in Python, and will be kept up to date with improvements there. I will try and keep the calling interface to the solvers the same as that described above.

Enjoy.

Enigma 1162: Triangular or square

From New Scientist #2318, 24th November 2001

Harry and Tom each chose a four-digit number that was either a perfect square or a triangular number and told me its last two digits. I deduced that Harry’s number was one of exactly two four-digit perfect squares or one of exactly two four-digit triangular numbers, but that Tom’s number was one of exactly three four-digit perfect squares or one of exactly three four-digit triangular numbers.

Then they told me that the sum of the digits of Harry’s number was the same as the sum of the digits of Tom’s number.

What were (a) Harry’s number and (b) Tom’s number?

[enigma1162]

Enigma 349: Not so wordy

From New Scientist #1498, 6th March 1986 [link]

Puzzle magazines are full of word puzzles consisting of an array of letters in which one tries to spot words by reading across rows (in either direction) or by reading up and down the diagonals, or by reading up or down the columns.

The idea in this week’s Enigma is to do the same in the following framework, but this time you are looking for numbers. Find a number bigger than 5 which can be seen in one of those ways in the frame for which the square of the number is also there somewhere, the cube of the number is also there somewhere, and such that the sum of the consecutive integers 1, 2, 3… up to and including that number can be seen somewhere in the framework.

Enigma 349

What is the number?

[enigma349]

Enigma 1163: Clean up the square

From New Scientist #2319, 1st December 2001 [link]

Enigma 1163

Delete two of the three occurrences of each letter in the square (above), so that you leave one letter in each row and in each column.

Look at the square you obtain. What is the letter in the top row, the letter in the second row, …, the letter in the bottom row, in that order?

[enigma1163]

Enigma 348: A piece of cake

From New Scientist #1497, 27th February 1986 [link]

I went to three parties in succession. At each one I was surprised to see an identical cake, bought at the Bêtisserie Noire, and on each occasion the cake was divided equally among all those present, including me.

When I arrived home (what a dog I felt!) I realised to my embarrassment that I had eaten altogether the equivalent of exactly half a cake. Of course, I could have done that by going to three parties with five people at each, so that there would have been 18 pieces of cake at all three parties. But how dull that would have been! However, just as reversing 18 gives 81, a perfect square, so too reversing the digits in the total number of pieces of cake involved in that triple binge produces a perfect square. Is it a two-digit square? Really, I shan’t hand you the answer on a plate.

How many people did I encounter at each party?

[enigma348]

Enigma 1164: Triple count

From New Scientist #2319, 1st December 2001 [link]

I call the number 25 “straight” because when written in words with capital letters it uses only straight lines. In fact, when written in simple capitals, it uses 29 line segments (including the hyphen), 11 of which are horizontal; also it has 10 letters. On the other hand 18 is not straight because it uses a curved G.

I have now written down three straight numbers in words with simple capitals. The first of the numbers is within 1 of the total number of line segments in the three numbers. The second on the numbers is within 1 of the total number of horizontal line segments in the three numbers. And the third of the numbers is within 1 of the total number of letters in the three numbers.

What are the three numbers?

[enigma1164]

Enigma 347: Trellis

From New Scientist #1496, 20th February 1986 [link]

Enigma 347

I went out on Tuesday to buy a piece of trellis to cover a gap which I measured 30 inches wide × 48 inches high. Allowing half an inch spare on all sides for fixing, I needed at least 31 inches × 49 inches.

I found at the shop that they sold the stuff in various sizes. Size 5, for instance, which is shown in the picture, has five rows of five studs (on which the whole thing swivels); size 6 has six rows of six studs and so on.

In every size the studs were 5 inches apart along the slats, which were 1 inch wide, with each end rounded off in a semicircle of ½-inch radius centred on the last stud.

When I told the manager my measurements, he said,” I’m afraid size 11 will be just too small. If you pull it out to 31 inches wide, the height will be just short of 49 inches. So you’d better take size 12. We charge 5p per stud, so that will be £7.20… Yes, certainly we’ll change it if the size should be wrong.”

When I got home, I was horrified to find that I had mis-measured the height of the gap. It was really 84 inches, not 48 inches. So I needed 31 inches × 85 inches. Back I went to the shop, where, having done my homework meanwhile, I was able this time to ask myself for the size most economical of trellis that would meet my requirements exactly.

What was the price of this trellis?

[enigma347]

Enigma 1165: Bull’s-eye

From New Scientist #2320, 15th December 2001 [link]

The darts players at George’s local have devised a seeding system for themselves. Each has determined the number of darts he needs to throw, on average, in order to hit the Bull once. This is his rating — the lower the better. Thanks to remarkable foresight in their parents’ choices of names, the seedings proceeded alphabetically from Alan at No. 1 to Zak at No. 26, with no duplication of initial.

Fred and George met in the pub recently and decided to throw alternately, one dart at a time, until one hit the Bull. The other would then pay for the drinks. Although Fred is the more accurate darts player, they calculated from the ratings that if George threw first they would each have an even chance of winning the sudden-death game.

Duly refreshed, they then calculated from the ratings that this would be an even-money game for any pair of players who are adjacent in the seedings, provided the lower seed throws first. But if Zak played the game against Alan and threw first, his chance of winning would be exactly 10 per cent.

What is George’s rating?

[enigma1165]

Enigma 346: Alphabetical goals

From New Scientist #1495, 13th February 1986 [link]

Five football teams, A, B, C, D and E, are to play each other once. After some of the games had been played a table was drawn up giving some details of the matches played, won, lost etc.

Unfortunately, the digits had been replaced by letters. Each letter stood for the same digit (from 0 to 9) wherever it appeared, and different letters stood from different digits.

The table looked like this:

Enigma 346

(Two points are given for a win and one point to each side in a drawn match).

Find the score in each match.

[enigma346]

Follow

Get every new post delivered to your Inbox.