Enigmatic Code

Programming Enigma Puzzles

BrainTwister #16: Order, order!

6 Comments Posted by on 19 April 2024

From New Scientist #3487, 20th April 2024 [link] [link]

(a) Arrange the digits 1-9 in a line so that each pair of adjacent digits differs by either 2 or 3.

(b) Arrange the digits 1-9 in a line so that each pair of adjacent digits sums to a prime number.

(c) Now arrange the digits 1-9 in a line so that each pair of adjacent digits (when read as a two-digit number) appears in the times tables from 1 × 1 up to 9 × 9.

[braintwister16]

braintwister

6 responses to “BrainTwister #16: Order, order!”

  1. Jim Randell 19 April 2024 at 4:29 pm

    Here is a solution using the [[ SubstitutedExpression() ]] solver from the enigma.py library.

    We use the same set of expressions for each part, but change the function were are using to test adjacent digits.

    It runs in 86ms. (Internal runtime is 17ms).

    Run: [ @replit ]

    from enigma import (
  SubstitutedExpression, irange, primes, subsets, tuples,
  sprintf as f, join, printf
)

digits = list(irange(1, 9))

# (a) digits differ by 2 or 3
fn_a = lambda x, y: abs(x - y) in {2, 3}

# (b) digits sum to a prime number
primes.expand(17)
fn_b = lambda x, y: (x + y) in primes

# (c) digits give a product 1*1 to 9*9
prods = set(a * b for (a, b) in subsets(digits, size=2, select='R'))
fn_c = lambda x, y: (10 * x + y) in prods

# common parameters
exprs = list(f("fn({x}, {y})") for (x, y) in tuples("ABCDEFGHI", 2))
answer = "(A, B, C, D, E, F, G, H, I)"

# consider each question
for (q, fn) in zip("abc", [fn_a, fn_b, fn_c]):
  # construct a solver using the specified function
  p = SubstitutedExpression(exprs, digits=digits, env=dict(fn=fn), answer=answer)
  # output answers
  for ans in p.answers(verbose=0):
    printf("({q}) {ans}", ans=join(ans, sep=" ", enc="[]"))
  printf()

    Solution: (a) There are 30 possible arrangements, for example: (1 3 5 2 4 7 9 6 8); (b) There are 140 possible arrangements, for example: (1 2 3 4 7 6 5 8 9); (c) There is 1 possible arrangement: (7 2 8 1 6 3 5 4 9).

    Reply
    • Hugo 19 April 2024 at 5:55 pm

      If part (a) had specified 3 or 7 as the difference, there would be just one solution:
      3 6 9 2 5 8 1 4 7 (or the inverse). Admittedly it is not hard to find.
      If the difference is to be 2 or 5 there are four solutions (and their inverses).

      Reply
  2. ruudvanderham 21 April 2024 at 6:17 am

    Here’s one brute force solution, which runs slowly (but still within 30 seconds) and a much faster solution (runs in 30 ms on my iPad).

    Note that I use my -just released- istr module that makes it possible to use strings as if they were integers in calcuations. This can be quite handy in solving several enigmas. You can find the extensive readme on http://www.github.com/salabim/istr . There you’ll also find how to install from PyPI.
    @Jim you could consider adding it to our enigma module: it is just one class.

    Brute force:

    from istr import istr
import itertools

allset = istr({i * j for i in range(1, 10) for j in range(i, 10) if 10 <= i * j <= 99})
solutions = {i: [] for i in (1, 2, 3)}

for c in istr(itertools.permutations(range(1, 10), 9)):
    if all(abs(c1 - c2) in (2, 3) for c1, c2 in zip(c, c[1:])):
        solutions[1].append("".join(c))
    if all(c1 + c2 in (2, 3, 5, 7, 11, 13, 17, 19) for c1, c2 in zip(c, c[1:])):
        solutions[2].append("".join(c))
    if all(c1 | c2 in allset for c1, c2 in zip(c, c[1:])):
        solutions[3].append("".join(c))

for part in (1, 2, 3):
    print(f"Part {part} has {len(solutions[part])} solutions:")
    print(*solutions[part])
    print()

    Fast recursive version:

    from istr import istr

one_to_nine = istr(range(1, 10))

friends = {part: {} for part in (1, 2, 3)}
for digit in one_to_nine:
    friends[1][digit] = {friend for friend in one_to_nine if abs(digit - friend) in (2, 3)}


for digit in one_to_nine:
    friends[2][digit] = {friend for friend in one_to_nine if digit + friend in istr(2, 3, 5, 7, 11, 13, 17, 19)}


multiples = {i * j for i in one_to_nine for j in one_to_nine if 10 <= i * j <= 99 and 0 not in i * j}

for digit in one_to_nine:
    friends[3][digit] = {friend for friend in one_to_nine if digit | friend in multiples}


def solve(not_assigned_digits, assigned_digits, friends):
    if not_assigned_digits:
        for digit in friends[assigned_digits[-1]] & not_assigned_digits if assigned_digits else not_assigned_digits:
            yield from solve(not_assigned_digits - {digit}, assigned_digits | digit, friends)
    else:
        yield assigned_digits


solutions = {}
for part in (1, 2, 3):
    solutions[part] = [solution for solution in solve(set(one_to_nine), "", friends[part])]


for part in (1, 2, 3):
    print(f"Part {part} has {len(solutions[part])} solutions:")
    print(*sorted(solutions[part]))
    print()
    Reply
    • Jim Randell 30 April 2024 at 10:52 am

      Thanks. I’ll have a look at istr.

      One suggestion I might make is to provide a way of iterating through the digits of an istr that provides the individual digits as istr objects. Maybe:

      istr.__iter__ = (lambda self: map(istr, str.__iter__(abs(self))))

      Or provide an istr.digits() method that does this.

      Reply
      • ruudvanderham 30 April 2024 at 1:40 pm

        Thanks for your feedback.
        I have implemented a __iter__ method, albeit implemented slightly different from your suggestion.

        And I have added a new (class) method digits. So now we can do:

            istr.digits() ==> istr('0123456789')
    istr.digits('') ==> istr('0123456789')
    istr.digits('1') ==> istr('1')
    istr.digits('3-') ==> istr('3456789')
    istr.digits('-3') ==> istr('0123')
    istr('1-4', '6', '8-9') ==> istr('1234689')
    istr.digits('1', '1-2', '1-3') ==> istr('112123')

        See PyPI or Github for details.

        Reply
  3. GeoffR 28 April 2024 at 10:55 am

    Three programs for parts (a), (b) and (c)

    Part(a)

    % A Solution in MiniZinc
include "globals.mzn";

% BT 16 - Part (a)
% Arrange the digits 1-9 in a line so that each pair of adjacent
% digits differ by either 2 or 3.

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]);

constraint abs(a - b) == 2 \/ abs(a - b) == 3;
constraint abs(b - c) == 2 \/ abs(b - c) == 3;
constraint abs(c - d) == 2 \/ abs(c - d) == 3;
constraint abs(d - e) == 2 \/ abs(d - e) == 3;
constraint abs(e - f) == 2 \/ abs(e - f) == 3;
constraint abs(f - g) == 2 \/ abs(f - g) == 3;
constraint abs(g - h) == 2 \/ abs(g - h) == 3;
constraint abs(h - i) == 2 \/ abs(h - i) == 3;

solve satisfy;
output [" [a,b,c,d,e,f,g,h,i] = " ++ show([a,b,c,d,e,f,g,h,i]) ];

% [a,b,c,d,e,f,g,h,i] = [8, 6, 9, 7, 5, 2, 4, 1, 3]

    Part(b)

    include "globals.mzn";

% BT 16 - Part (b)
% Arrange the digits 1-9 in a line so that each pair of adjacent
% digits sums to a prime number.

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]);

predicate is_prime(var int: x) = 
x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) 
((i < x) -> (x mod i > 0));

constraint sum([is_prime(a + b), is_prime(b + c), is_prime(c + d),
is_prime(d + e), is_prime(e + f), is_prime(f + g),
is_prime(g + h), is_prime(h + i)] ) == 8;

solve satisfy;

output [ "Digits are: " ++ show( [a, b, c, d, e, f, g, h, i]) ];

% Digits are: Digits are: [9, 4, 1, 2, 3, 8, 5, 6, 7] 
% ----------

    Part (c)

    include "globals.mzn";

% BT16 -  Part (c)
% Now arrange the digits 1-9 in a line so that each pair of adjacent digits 
% (when read as a two-digit number) appears in the times tables from 1 × 1 up to 9 × 9.

% The times tables from 1 × 1 up to 9 × 9
var set of int: products == {
1, 2, 3, 4, 5, 6, 7, 8, 9,
2, 4, 6, 8, 10, 12, 14, 16, 18,
3, 6, 9, 12, 18, 21, 24, 27,
4, 8, 12, 16, 20, 24, 28, 32,
5, 10, 15, 20, 25, 30, 40, 45,
6, 12, 18, 24, 30, 36, 42, 48, 54,
7, 14, 21, 28, 35, 42, 49, 56, 63,
8, 16, 24, 32, 40, 48, 56, 64, 72,
9, 18, 27, 36, 45, 54, 63, 72, 81};
 
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]);

constraint sum( [ (10*a+b) in products, (10*b+c) in products,
(10*c+d) in products, (10*d+e) in products, (10*e+f) in products,
(10*f+g) in products, (10*g+h) in products, (10*h+i) in products] ) == 8;

solve satisfy;

output [ "Digits are: " ++ show([a, b, c, d, e, f, g, h, i]) ];

% Digits are: [7, 2, 8, 1, 6, 3, 5, 4, 9]
% ----------
% ==========
    Reply

Leave a Comment

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