Enigmatic Code

Programming Enigma Puzzles

Enigma 430: Let your fingers do the walking

From New Scientist #1580, 1st October 1987 [link]

Enigma 430

My Welsh friend, Dai the dial, has a telephone number consisting of nine different digits and, as you telephone him on my push-button phone illustrated above, you push a sequence of buttons each adjacent (across or down) to the one before.

The digit not used in his number is odd, the last digit of the number is larger than the first, and (ignoring the leading digit if it is zero) the number is divisible by 21.

What is Dai’s number?

[enigma430]

5 responses to “Enigma 430: Let your fingers do the walking

  1. Jim Randell 5 January 2018 at 8:41 am

    A nice straightforward Python 3.6 program executes in 42ms.

    Run: [ @repl.it ]

    # adjacent digits
    adj = {
      '1': '24',
      '2': '135',
      '3': '26',
      '4': '157',
      '5': '2468',
      '6': '359',
      '7': '48',
      '8': '5790',
      '9': '68',
      '0': '8',
    }
    
    # odd digits
    odd = set('13579')
    
    # find sequences of adjacent digits
    # n - how many additional digits required
    # s - sequence so far
    def solve(n, s):
      # are we done?
      if n == 0:
        yield s
      else:
        for d in adj[s[-1]]:
          if d not in s:
            yield from solve(n - 1, s + d)
    
    # consider possible starting digits
    for d in adj.keys():
      # and solve for 8 remaining digits
      for s in solve(8, d):
        # not all the odd digits are used
        if not odd.difference(s): continue
        # the final digit is larger than the first
        if not(s[-1] > s[0]): continue
        # the number is divisible by 21
        if int(s) % 21 != 0: continue
        # output a solution
        print(s)
    

    Solution: Dai’s phone number is 087412563.

  2. Hakan Kjellerstrand 6 January 2018 at 6:31 pm

    Here’s a MiniZinc model.

    include "globals.mzn"; 
    int: n = 9;
    array[1..10] of set of int: dial =
    [
      {2,4},     % 1
      {1,3,4},   % 2
      {2,6},     % 3
      {1,5,7},   % 4
      {2,4,6,8}, % 5
      {3,5,9},   % 6
      {4,8},     % 7
      {5,7,9,0}, % 8
      {6,8},     % 9
      {8},       % 0
    ];
    
    % decision variables
    array[1..n] of var 0..9: x;
    var int: num;
    var 0..9: not_used;
    
    % n = to_num_base(a, base)
    function var int: to_num_base(array[int] of var int: a, int: base) =
              let { int: len = card(index_set(a));
                    var int: n = sum(i in index_set(a)) (
                       pow(base, len-i) * a[i] 
                     );
             } in n
    ;
    % base 10
    function var int: to_num(array[int] of var int: a) = to_num_base(a, 10);
    solve satisfy;
    constraint
       all_different(x) /\
       forall(i in 2..n) (
         x[i-1] in dial[x[i]]
       ) /\
       num = to_num(x) /\
       forall(i in 1..n) (
         not_used != x[i]
       )  /\
       not_used mod 2 = 1
    ;
    
    output 
    [
      show(x[i])
      | i in 1..n
    ];
    
  3. geoffrounce 7 January 2018 at 11:07 am

    Hakan/Jim: An interesting MiniZinc solution

    The last line of the Enigma description reads;

    “The digit not used in his number is odd, the last digit of the number is larger than the first, and (ignoring the leading digit if it is zero) the number is divisible by 21.”

    I can see the first constraint in this sentence is included in the code, but the other two constraints in this sentence do not seem needed in the code to find a solution ?

    Also, in the array/ number conversion, why does the leading ‘0’ digit in the answer not get lost in the conversion to a number ?

  4. Hakan Kjellerstrand 7 January 2018 at 12:00 pm

    @geoffrounce Thanks for your comments. Here are answers regarding the MiniZinc model.

    1) The constraint about the last digit is larger than the first is not needed in the model (since the first number is 0). Though I have to admit that I forgot it.

    2) The statement “the number (ignoring the leading digit if it’s zero) is divisible by 21” is a copy-paste mistake of mine in the code above. The constraint section should read as following, i.e. I omitted the last constraint:

    constraint
       all_different(x) /\
       forall(i in 2..n) (
         x[i-1] in dial[x[i]]
       ) /\
       num = to_num(x) /\
       forall(i in 1..n) (
         not_used != x[i]
       ) /\
       not_used mod 2 = 1 /\
       num mod 21 = 0
    ;
    

    Sorry about that!

    3) “num” is converted to a proper number, so the leading 0 is ignored. Though, the answer is not printing “num”, but the full array (the “show(x[i]) | i in 1..n” in the output section).

    The full model is here: http://hakank.org/minizinc/enigma_430_let_the_fingers_do_the_walking.mzn

  5. Jim Randell 7 January 2018 at 9:48 pm

    Here’s my MiniZinc solution. I assign the digits (including the digit that is not used in the phone number) into the array [[ d ]], indices d[1] – d[9] represent the phone number, d[10] is the unused digit.

    include "globals.mzn";
    
    
    % the digits of the phone number (d[1] - d[9]), and d[10] is the unused digit
    array[1..10] of var 0..9: d;
    
    % all digits are used
    constraint all_different(d);
    
    % the last digit of the phone number is larger than the first
    constraint d[1] < d[9];
    
    % the unused digit is odd
    constraint d[10] mod 2 = 1;
    
    
    % the phone number as an integer
    var int: n = sum (i in 1..9) (d[i] * pow(10, 9 - i));
    
    % the phone number is divisible by 21
    constraint n mod 21 = 0;
    
    
    % adjacent digits (note this is indexed by d + 1)
    array[1..10] of set of 0..9: adj = [
      {8},          % 0
      {2, 4},       % 1
      {1, 3, 5},    % 2
      {2, 6},       % 3
      {1, 5, 7},    % 4
      {2, 4, 6, 8}, % 5
      {3, 5, 9},    % 6
      {4, 8},       % 7
      {5, 7, 9, 0}, % 8
      {6, 8},       % 9
    ];
    
    % each digit in the phone number is adjacent to the previous one
    constraint forall (i in 1..8) (d[i + 1] in adj[d[i] + 1]);
    
    
    solve satisfy;
    

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: