Enigmatic Code

Programming Enigma Puzzles

Enigma 1113: Ten + ten = twenty

From New Scientist #2269, 16th December 2000 [link]

In the multiplications shown, where the combined products of multiplications (I) and (II) (both identical) equal the product of multiplication (III), each letter consistently represents a specific digit, different letters being used for different digits while asterisks can be any digit.

The multiplications in fact are not difficult to solve, and easier still if I told you that TEN is even.

How much is TWENTY?

[enigma1113]

Advertisements

5 responses to “Enigma 1113: Ten + ten = twenty

  1. Jim Randell 29 May 2017 at 9:45 am

    The first two multiplication sums are the same, so TWENTY is twice the result.

    I’ve recently changed the internals of the SubstitutedExpression() solver so that you can specify the alphametic component of expressions using curly braces. This means you don’t have to explicitly specify the symbols used via the --symbols parameter, and allows you to use functions in expressions that would otherwise clash with the alphametic symbols (for example, in the code below, the “a” and “c” in the calls to match() are not interpreted as alphametic symbols, as they are not enclosed in curly braces, whereas as the “a” and “c” in {abc} * {TEN} are).

    As you’ve probably noticed I’ve also recently added the match() function to the enigma.py library, this matches the first argument (as a string) against the template given in the second argument. It is a repackaging of the fnmatch.fnmatch() function from the Python standard library, rather than using regular expressions.

    This following run file executes in 419ms.

    #!/usr/bin/env pypy -m enigma -r
    
    #      a b c                d e f
    #      T E N                g h i
    #  ---------          -----------
    #    ? ? ? ?                ? ? ?
    #  ? ? ? ?                ? ? ?
    #  ? ? ?                ? ? ?
    #  ---------          -----------
    #  ? ? ? ? ?   * 2 =  T W E N T Y
    #  =========          ===========
    
    SubstitutedExpression
    
    --distinct="ENTWY"
    --invalid="13579,N"
    --answer="{TWENTY}"
    
    "2 * {abc} * {TEN} = {TWENTY}"
    "match({abc} * {N}, '????')"
    "match({abc} * {E}, '????')"
    "match({abc} * {T}, '???')"
    "match({abc} * {TEN}, '?????')"
    
    "{def} * {ghi} = {TWENTY}"
    "match({def} * {i}, '???')"
    "match({def} * {h}, '???')"
    "match({def} * {g}, '???')"
    

    Solution: TWENTY = 109416.

    The first two multiplication sums are: 282 × 194 = 54708 (= 1128 + 2538_ + 282__).

    The third sum is: 141 × 776 = 109416 (= 846 + 987_ + 987__).

  2. geoffrounce 29 May 2017 at 1:11 pm

    I mostly used your layout for the multiplication tables and found the requirement for TEN to be even not strictly necessary.

    I also found multiple solutions for the third multiplication, but unique results for the two repeated multiplications and the value of TWENTY. There seemed to be more than ten answers for the third multiplication, but I have only shown five results at the end of my code.

    % A Solution in MiniZinc
    %       a b c                d e f
    %       T E N                g h i
    %   ---------          -----------
    %     ? ? ? ?                ? ? ?
    %   ? ? ? ?                ? ? ?
    %   ? ? ?                ? ? ?
    %   ---------          -----------
    %   j k l m n  * 2  =  T W E N T Y
    %   =========          ===========
    
    include "globals.mzn";
    
    var 1..9:T; var 0..9:W; var 0..9:E;  var 0..9:N;  var 0..9:Y; 
    
    constraint all_different([T,W,E,N,Y]);
    
    var 100..999 : TEN = 100*T + 10*E + N;
    constraint TEN mod 2 == 0; 
    
    var 100000..999999: TWENTY = 100000*T + 10000*W + 1000*E 
    + 100*N + 10*T + Y;
    
    var 0..9:a;  var 0..9:b;  var 0..9:c;  var 0..9:d;  var 0..9:e;
    var 0..9:f;  var 0..9:g;  var 0..9:h;  var 0..9:i;  var 0..9:j;
    var 0..9:k;  var 0..9:l;  var 0..9:m;  var 0..9:n;  
    
    constraint a > 0 /\ d > 0 /\ g > 0 /\ j > 0;
    
    var 100..999: abc = 100*a + 10*b +  c;
    var 100..999: def = 100*d + 10*e +  f;
    var 100..999: ghi = 100*g + 10*h +  i;
    var 10000..99999: jklmn = 10000*j + 1000*k + 100*l + 10*m + n;
    
    % 1st multiplication (repeated for 2nd multiplication)
    constraint abc * TEN == jklmn;
    constraint (N * abc) + (E * abc * 10) + (T * abc * 100) == jklmn;
    
    % 3rd multiplication
    constraint def * ghi == TWENTY;
    constraint (i * def) + (h * def * 10) + (g * def * 100) == TWENTY;
    
    % 3rd multiplication is also the sum of the 1st and 2nd multiplications
    constraint jklmn * 2 == TWENTY;
    
    solve satisfy;
    
    output ["TWENTY = " ++ show(TWENTY) ++ "\n" ++
            "1st and 2nd multiplications = " ++ show(abc) ++ " X " ++ show(TEN)
             ++ " = " ++ show(jklmn) ++ "\n" ++
            "3rd multiplication = " ++ show(def) ++ " X " ++ show(ghi)
             ++ " = " ++ show(TWENTY)];
    
    % TWENTY = 109416
    % 1st and 2nd multiplications = 282 X 194 = 54708
    % 3rd multiplication = 776 X 141 = 109416
    % ----------
    % TWENTY = 109416
    % 1st and 2nd multiplications = 282 X 194 = 54708
    % 3rd multiplication = 582 X 188 = 109416
    % ----------
    % TWENTY = 109416
    % 1st and 2nd multiplications = 282 X 194 = 54708
    % 3rd multiplication = 564 X 194 = 109416
    % ----------
    % TWENTY = 109416
    % 1st and 2nd multiplications = 282 X 194 = 54708
    % 3rd multiplication = 388 X 282 = 109416
    % ----------
    % TWENTY = 109416
    % 1st and 2nd multiplications = 282 X 194 = 54708
    % 3rd multiplication = 376 X 291 = 109416
    % ----------
    % Finished in 137msec
    
    
    
    • Jim Randell 29 May 2017 at 1:48 pm

      @geoff: I think you are getting multiple solutions because you need to check the “shape” of the intermediate multiplications in the sums. So you need some equivalent of the match() expressions in my solution.

      Adding the following constraints to your model will get you down to a single, unique solution:

      constraint 999 < abc * N /\ abc * N < 10000;
      constraint 999 < abc * E /\ abc * E < 10000;
      constraint 99 < abc * T /\ abc * T < 1000;
      
      constraint 99 < def * i /\ def * i < 1000;
      constraint 99 < def * h /\ def * h < 1000;
      constraint 99 < def * g /\ def * g < 1000;
      

      Also the following two pairs of constraints in your model are equivalent within the pair, so you only need the first one of each pair.

      % 1st multiplication (repeated for 2nd multiplication)
      constraint abc * TEN == jklmn;
      constraint (N * abc) + (E * abc * 10) + (T * abc * 100) == jklmn;
       
      % 3rd multiplication
      constraint def * ghi == TWENTY;
      constraint (i * def) + (h * def * 10) + (g * def * 100) == TWENTY;
      
      • geoffrounce 29 May 2017 at 2:59 pm

        Hi Jim, Yes, your extra constraints work OK and give a single solution, as you state.
        A useful programming critique.

        At least my answer for TWENTY was still OK – I guess the answer is not affected by the “shape” of the third multiplication?

        Re programming these alphametic Enigma puzzles, I have found another type which was difficult in MiniZinc i.e. the type where only one letter is wrong e.g. Enigma 197. The techniques you used in Python for this Enigma don’t seem readily applicable to a MiniZinc solution.

        Interested if you think a MiniZinc solution is possible for Enigma 197?
        (or maybe is not possible)

        • Jim Randell 30 May 2017 at 5:44 pm

          @geoff: My method of solving the kind of puzzle you refer too (Enigma 29, Enigma 197, Enigma 284, Puzzle 76) has been to generate a series of alphametic sums that differ from the given incorrect sum in one place, and then run them all through the SubstitutedSum() solver from the enigma.py library. In the case of Enigma 197 this requires checking 192 different alphametic sums, but fortunately the solver deals with them all in under a second.

          An alternative would be to use the general alphametic solver, and generate a sum for each position in the original sum, where the symbol at that position is a new alphametic symbol that does not have to take on a different digit value from the other symbols. That way, for Enigma 197 we only require checking 24 different alphametic sums. Unfortunately using the SubstitutedExpression() solver turns out to be slower than checking the 192 sums using the SubstitutedSum() solver.

          Another way would be to consider partial sums. The given alphametic sum gives no solutions, but we can consider it without the leftmost column, and if that has solutions we can try substituting the symbols for each place in the column. If not we remove another column from the left, and try again. This method would require checking 8 (each column) + 3 (each place in the column) = 11 sums. But I didn’t code this approach up.

          But each of these approaches would require a MiniZinc model for each of the sums considered. You can automate their generation using the minizinc.py library, but the end result will still be quite slow.

          An approach that uses a single MiniZinc model, is to create a new alphametic sum abcdefgh + ijkmnpqr = stuvwxyz, with symbols that don’t have to have different digit values (just as well as we have 24 symbols and only 10 digits), but the symbols do have to match up with the original incorrect sum except in exactly one position.

          I’ve posted the MiniZinc model as a comment on Enigma 197.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: