# 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]

### 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])
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.