Enigmatic Code

Programming Enigma Puzzles

Enigma 1692: Key factors

From New Scientist #2859, 7th April 2012 [link]

Clever logic should enable you to find the nine-figure number that I have in mind. It consists of the digits 1 to 9 in some order, and in the number each digit is next to another that differs from it by one.

In just one case a digit has both neighbours differing from it by one. Furthermore, the solution is exactly divisible by more than three-quarters of the numbers 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 and 12.

What is the nine-figure number?

[enigma1692]

Advertisements

5 responses to “Enigma 1692: Key factors

  1. Jim Randell 3 April 2012 at 10:20 pm

    Here’s my initial solution in Python. It runs in 316ms.

    from itertools import permutations
    from enigma import concat
    
    for d in permutations(range(1, 10)):
      # the first two digits must differ by 1
      if abs(d[0] - d[1]) != 1: continue
      # likewise the last two digits
      if abs(d[7] - d[8]) != 1: continue
    
      # for the rest, count how many neighbours differ by 1
      c = list((1 if abs(d[i-1] - d[i]) == 1 else 0) +
               (1 if abs(d[i] - d[i+1]) == 1 else 0) for i in range(1, 8))
      # only one should have 2 neighbours that differ by 1
      if c.count(2) != 1: continue
      # and the rest should only have 1 neighbour that differs by 1
      if c.count(1) != 6: continue
    
      # what is the number?
      n = int(concat(*d))
    
      # find the divisors
      ds = list(i for i in range(1, 13) if n % i == 0)
      # there should be more than 9 of them
      if len(ds) < 10: continue
    
      print(n, ds)
    

    Solution: The number is 436578912.

    • Jim Randell 4 April 2012 at 8:17 am

      Here’s a faster program that uses recursion. It runs in 54ms.

      from enigma import concat
      
      # the 9-digit number must be even, so let's accumulate the digits in reverse
      
      digits = set(range(1, 10))
      
      # flag is set when we've got a digit that differs by 1 from both neighbours
      def solve(ds, flag=False):
        # are we done?
        if len(ds) == 9:
          # check the final digit differs by 1 from the previous one
          if abs(ds[7] - ds[8]) != 1: return
          # and that we have exactly one digit that differs by 1 from both neighbours
          if flag ^ (abs(ds[6] - ds[7]) != 1): return
          # so, what is the number (remember the digits are in reverse order)
          n = int(concat(*reversed(ds)))
          # find the divisors
          l = list(i for i in range(1, 13) if n % i == 0)
          if len(l) > 9: print(n, l)
        # last digit must be even
        elif len(ds) == 0:
          for d in digits:
            if d % 2: continue
            solve([d])
        # penultimate digit must differ from the last by one
        elif len(ds) == 1:
          for d in digits.intersection((ds[0] - 1, ds[0] + 1)):
            solve(ds + [d])
        # try adding another digit
        else:
          for d in digits.difference(ds):
            # count the neighbours of the previous digit
            n = (1 if abs(ds[-2] - ds[-1]) == 1 else 0) + (1 if abs(ds[-1] - d) == 1 else 0)
            # must be 1 or 2 (if 2 hasn't already been used)
            if not(n == 1 or (n == 2 and not flag)): continue
            solve(ds + [d], flag or (n == 2))
      
      solve([])
      
  2. geoffrounce 27 July 2017 at 4:58 pm
    % A Solution in MiniZinc
    include "globals.mzn";
    
    var 1..9:A;   var 1..9:B;  var 1..9:C;
    var 1..9:D;   var 1..9:E;  var 1..9:F;
    var 1..9:G;   var 1..9:H;  var 1..9:I;
    
    constraint all_different ( [A,B,C,D,E,F,G,H,I] );
    
    var 100000000..999999999: ABCDEFGHI = I + 10*H + G*100 + F*pow(10,3)
    + E*pow(10,4) + D*pow(10,5) + C*pow(10,6) + B*pow(10,7) + A*pow(10,8);
    
    % In the number each digit is next to another that differs from it by one
    % Number is ABCDEFGHI below
    constraint 
    ( abs(B-A) == 1 \/ abs(B-C) == 1 ) /\                  
    ( abs(C-B) == 1 \/ abs(C-D) == 1 ) /\   
    ( abs(D-C) == 1 \/ abs(D-E) == 1 ) /\    
    ( abs(E-D) == 1 \/ abs(E-F) == 1 ) /\    
    ( abs(F-E) == 1 \/ abs(F-G) == 1 ) /\     
    ( abs(G-F) == 1 \/ abs(G-H) == 1 ) /\   
    ( abs(H-G) == 1 \/ abs(H-I) == 1 );       
    
    % In just one case a digit has both neighbours differing from it by one
    constraint 
    ( abs(B-A) == 1 /\ abs(B-C) == 1 ) \/
    ( abs(C-B) == 1 /\ abs(C-D) == 1 ) \/
    ( abs(D-C) == 1 /\ abs(D-E) == 1 ) \/
    ( abs(E-D) == 1 /\ abs(E-F) == 1 ) \/
    ( abs(F-E) == 1 /\ abs(F-G) == 1 ) \/
    ( abs(G-F) == 1 /\ abs(G-H) == 1 ) \/
    ( abs(H-G) == 1 /\ abs(H-I) == 1 );
    
    % The solution is exactly divisible by more than three-quarters of the 
    % numbers 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 and 12. 
    constraint sum ( [ ABCDEFGHI mod 2 == 0,
    ABCDEFGHI mod 3 == 0, ABCDEFGHI mod 4 == 0, ABCDEFGHI mod 5 == 0, 
    ABCDEFGHI mod 6 == 0, ABCDEFGHI mod 7 == 0, ABCDEFGHI mod 8 == 0, 
    ABCDEFGHI mod 9 == 0, ABCDEFGHI mod 10 == 0, ABCDEFGHI mod 11 == 0, 
    ABCDEFGHI mod 12 == 0 ] ) > 8;   % as number mod 1 is always zero
    
    solve satisfy;
    
    output [ "Nine-figure number is " ++ show(ABCDEFGHI) ];
    
    % Nine-figure number is 436578912
    % Finished in 65msec
    
    • Jim Randell 28 July 2017 at 3:23 pm

      @geoff: When I execute this model with the mzn-gecode -a solver it finds 9 solutions (one of which is the correct answer).

      There’s a problem with the constraint at line 15. If each digit is next to a digit that differs from it by one, then we know that A and B must differ by one, and also H and I must differ by one. So we need to check those and the neighbours of C, D, E, F, and G. So a correct constraint would be:

      constraint 
       (abs(A - B) == 1) /\
       (abs(B - C) == 1 \/ abs(C - D) == 1) /\   
       (abs(C - D) == 1 \/ abs(D - E) == 1) /\    
       (abs(D - E) == 1 \/ abs(E - F) == 1) /\    
       (abs(E - F) == 1 \/ abs(F - G) == 1) /\     
       (abs(F - G) == 1 \/ abs(G - H) == 1) /\   
       (abs(H - I) == 1);
      

      Also the constraint at line 25 checks if any of the digits has two neighbours that differ from it by one, whereas we need to check that there is exactly one of the digits that satisfies this condition. Fortunately MiniZinc has the exactly() predicate that can be used to check this:

      constraint exactly(1, [
        (abs(A - B) == 1 /\ abs(B - C) == 1),
        (abs(B - C) == 1 /\ abs(C - D) == 1),
        (abs(C - D) == 1 /\ abs(D - E) == 1),
        (abs(D - E) == 1 /\ abs(E - F) == 1),
        (abs(E - F) == 1 /\ abs(F - G) == 1),
        (abs(F - G) == 1 /\ abs(G - H) == 1),
        (abs(G - H) == 1 /\ abs(H - I) == 1)
      ], 1);
      

      With these changes I get a model which produces only one solution, which is the answer to the problem.

      On my machine the mzn-gecode solver was the only one that gave an answer in a reasonable time using this model.

      • geoffrounce 28 July 2017 at 3:46 pm

        Jim,
        Point taken. I did not spot this problem – it only gave one correct solution when I ran it on the Geocode solver, without looking for multiple solutions.

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: