Sunday Times Teaser 3256 – Domino-Do

by BRG on 16 February 2025

by Victor Bryant

Published Sunday February 16 2025 (link)

I have a standard set of 28 dominoes with a number of spots from zero to six at each end, and each possible pair of numbers occurring once in the set. When two dominoes in a line touch, the two adjacent ends must have the same number of spots.

I started a line by placing one of the dominoes on a table. Then, in correct domino style, I placed another adjacent to it at the right-hand end. I continued in this way (placing each domino at either end of the line) until more than 14 dominoes were lined up. At each stage the total number of spots on the table was a different odd number less than 100. In fact, the last two totals were prime but the first two totals were not.

From the left, what were the first six dominoes in the line (in the form 1-4, 4-0, …)?

From → Uncategorized

2 Comments Leave one →

BRG permalink

This version is based on John’s version below which outperformed my old version and was also
structurally simpler. But I have changed the logic around lines 22..34 because I feel that this is
quite difficult to follow in John’s version.


from collections import defaultdict

# give full output or just the answer
full = True

# primes below 100
prms = {3, 5, 7, 11}
prms |= {2} | {n for n in range(13, 100, 2) if all(n % p for p in prms)}

# the 28 dominoes (not including (0, 0)), split into 'evens' and 'odds'
# with the latter not including primes
d_all = set((a, b) for a in range(7) for b in range(a, 7)) - {(0, 0)}
evens = set(d for d in d_all if not sum(d) & 1)
odds = set(d for d in d_all if ((t := sum(d)) & 1) and t not in prms)

can = lambda x: x if x[0] < x[1] else x[::-1]

# place from dominoes in <dms> with the pip sums 
# so far in <sms> and the line so far in <dln>
def place(dms, sms, dln):
  if (ln := len(dln)) > 14 and sms[-1] in prms and sms[-2] in prms:
    yield dln, sms
  else:
    # consider the next remaining domino and collect possible
    # placings on the right or left and 'as is' or reversed
    to_do = list()
    for nd in dms:
      p, q = nd
      rd = q, p
      # place on the right
      if p == dln[-1][-1]:
        to_do.append((nd, dln + (nd,)))
      if p != q and q == dln[-1][-1]: 
        to_do.append((rd, dln + (rd,)))
      
      # place on the left if necessary
      if ln > 1:
        if p == dln[0][0]:
          to_do.append((rd, (rd,) + dln))
        if p != q and q == dln[0][0]:
          to_do.append((nd, (nd,) + dln))
  
    for nd, dx in to_do:
      sm = sms[-1] + sum(nd)
      # the pip sum must be less than 100 and the first
      # two pip sums must not be prime 
      if sm < 100 and (ln > 1 or sm not in prms):
        yield from place(dms - {can(nd)}, sms + (sm,), dx)
    
# for solutions and pip sum sequences
sols = defaultdict(set)
psms = defaultdict(list)

# select the first domino and consider it in either order
for t in(odds):
  for d in (t, t[::-1]):
    for dln, sms in place(evens, (sum(d),), (d,)):
      sols[dln[:6]] |= {dln[6:]}
      psms[dln[6:]] += [sms]

# count the numbers of different pip sum sequences
# reccord each sequence and its frequency
cts, d2c = defaultdict(set), defaultdict(dict)
for dln, sms in psms.items():
  for v in sms: 
    ct = sms.count(v)
    if ct not in cts[dln]:
      cts[dln].add(ct)
      d2c[dln][ct] = [1, v]
    else:
      d2c[dln][ct][0] += 1
    
def print_doms(ds):
  return ' | '.join(f"{a}{b}" for a, b in ds)

# output any answers      
for sol, l_dln in sols.items():
  for dln in l_dln:
    print(f"Domino line: {print_doms(sol)} ... ")
    # output pip sum sequence frequency counts
    print(f"  ... {dln}\n pip sum (counts, sequence):")
    # collect totals and outputs indexed on pip sum item frequency (1,2,4 or 8)
    t1, t2, df2r = 0, 0, {}
    for f, (vc, v) in zip(sorted(d2c[dln].items(), key=lambda x: x[1][1]),
                          sorted(d2c[dln].values(), key=lambda x: x[1])):
      df2r[f[0]] = f" {vc // f[0]:>3} x {f[0]} = {vc:>3}  {v}"
      t1 += vc // f[0]
      t2 += vc
    print('\n'.join(v for k, v in sorted(df2r.items())))
    print(f" ---       ---\n {t1}       {t2}\n ===       ===\n")

from collections import defaultdict

# give full output or just the answer

full = True

# primes below 100

prms = {3, 5, 7, 11}

prms |= {2} | {n for n in range(13, 100, 2) if all(n % p for p in prms)}

# the 28 dominoes (not including (0, 0)), split into 'evens' and 'odds'

# with the latter not including primes

d_all = set((a, b) for a in range(7) for b in range(a, 7)) - {(0, 0)}

evens = set(d for d in d_all if not sum(d) & 1)

odds = set(d for d in d_all if ((t := sum(d)) & 1) and t not in prms)

can = lambda x: x if x[0] < x[1] else x[::-1]

# place from dominoes in <dms> with the pip sums

# so far in <sms> and the line so far in <dln>

def place(dms, sms, dln):

if (ln := len(dln)) > 14 and sms[-1] in prms and sms[-2] in prms:

yield dln, sms

else:

# consider the next remaining domino and collect possible

# placings on the right or left and 'as is' or reversed

to_do = list()

for nd in dms:

p, q = nd

rd = q, p

# place on the right

if p == dln[-1][-1]:

to_do.append((nd, dln + (nd,)))

if p != q and q == dln[-1][-1]:

to_do.append((rd, dln + (rd,)))

# place on the left if necessary

if ln > 1:

if p == dln[0][0]:

to_do.append((rd, (rd,) + dln))

if p != q and q == dln[0][0]:

to_do.append((nd, (nd,) + dln))

for nd, dx in to_do:

sm = sms[-1] + sum(nd)

# the pip sum must be less than 100 and the first

# two pip sums must not be prime

if sm < 100 and (ln > 1 or sm not in prms):

yield from place(dms - {can(nd)}, sms + (sm,), dx)

# for solutions and pip sum sequences

sols = defaultdict(set)

psms = defaultdict(list)

# select the first domino and consider it in either order

for t in(odds):

for d in (t, t[::-1]):

for dln, sms in place(evens, (sum(d),), (d,)):

sols[dln[:6]] |= {dln[6:]}

psms[dln[6:]] += [sms]

# count the numbers of different pip sum sequences

# reccord each sequence and its frequency

cts, d2c = defaultdict(set), defaultdict(dict)

for dln, sms in psms.items():

for v in sms:

ct = sms.count(v)

if ct not in cts[dln]:

cts[dln].add(ct)

d2c[dln][ct] = [1, v]

else:

d2c[dln][ct][0] += 1

def print_doms(ds):

return ' | '.join(f"{a}{b}" for a, b in ds)

# output any answers

for sol, l_dln in sols.items():

for dln in l_dln:

print(f"Domino line: {print_doms(sol)} ... ")

# output pip sum sequence frequency counts

print(f" ... {dln}\n pip sum (counts, sequence):")

# collect totals and outputs indexed on pip sum item frequency (1,2,4 or 8)

t1, t2, df2r = 0, 0, {}

for f, (vc, v) in zip(sorted(d2c[dln].items(), key=lambda x: x[1][1]),

sorted(d2c[dln].values(), key=lambda x: x[1])):

df2r[f[0]] = f" {vc // f[0]:>3} x {f[0]} = {vc:>3} {v}"

t1 += vc // f[0]

t2 += vc

print('\n'.join(v for k, v in sorted(df2r.items())))

print(f" --- ---\n {t1} {t2}\n === ===\n")

Giving the results:


Domino line: 53 | 33 | 31 | 11 | 15 | 55 ... 
  ... ((5, 4), (4, 2), (2, 2), (2, 0), (0, 6), (6, 6), (6, 4), (4, 4), (4, 0))
 pip sums (counts, sequence):
 302 x 1 = 302  (9, 15, 25, 31, 33, 37, 39, 45, 57, 67, 75, 79, 85, 89, 97)
 201 x 2 = 402  (9, 15, 25, 31, 33, 37, 39, 45, 57, 67, 75, 79, 83, 89, 97)
  22 x 4 =  88  (9, 15, 25, 31, 33, 37, 41, 43, 49, 55, 67, 77, 85, 89, 97)
 ---       ---
 525       792
 ===       ===

Domino line: 53 | 33 | 31 | 11 | 15 | 55 ... 
  ... ((5, 4), (4, 2), (2, 2), (2, 0), (0, 4), (4, 4), (4, 6), (6, 6), (6, 0))
 pip sums (counts, sequence):
 230 x 1 = 230  (9, 15, 25, 31, 33, 37, 39, 43, 51, 61, 73, 79, 83, 89, 97)
 207 x 2 = 414  (9, 15, 25, 31, 33, 37, 39, 43, 51, 61, 73, 77, 83, 89, 97)
  31 x 4 = 124  (9, 15, 25, 31, 33, 37, 39, 43, 47, 55, 65, 77, 83, 89, 97)
   3 x 8 =  24  (9, 15, 25, 31, 35, 37, 39, 43, 47, 55, 65, 77, 83, 89, 97)
 ---       ---
 471       792
 ===       ===

Domino line: 53 | 33 | 31 | 11 | 15 | 55 ...

... ((5, 4), (4, 2), (2, 2), (2, 0), (0, 6), (6, 6), (6, 4), (4, 4), (4, 0))

pip sums (counts, sequence):

302 x 1 = 302 (9, 15, 25, 31, 33, 37, 39, 45, 57, 67, 75, 79, 85, 89, 97)

201 x 2 = 402 (9, 15, 25, 31, 33, 37, 39, 45, 57, 67, 75, 79, 83, 89, 97)

22 x 4 = 88 (9, 15, 25, 31, 33, 37, 41, 43, 49, 55, 67, 77, 85, 89, 97)

--- ---

525 792

=== ===

Domino line: 53 | 33 | 31 | 11 | 15 | 55 ...

... ((5, 4), (4, 2), (2, 2), (2, 0), (0, 4), (4, 4), (4, 6), (6, 6), (6, 0))

pip sums (counts, sequence):

230 x 1 = 230 (9, 15, 25, 31, 33, 37, 39, 43, 51, 61, 73, 79, 83, 89, 97)

207 x 2 = 414 (9, 15, 25, 31, 33, 37, 39, 43, 51, 61, 73, 77, 83, 89, 97)

31 x 4 = 124 (9, 15, 25, 31, 33, 37, 39, 43, 47, 55, 65, 77, 83, 89, 97)

3 x 8 = 24 (9, 15, 25, 31, 35, 37, 39, 43, 47, 55, 65, 77, 83, 89, 97)

--- ---

471 792

=== ===

John Z. permalink


full = False
p = (2, 3, 5, 7)
ps = p + tuple(x for x in range(11, 100, 2) if all(x % y for y in p))

# populate odd and even summing sets of dominos with both orienations 
# first domino must sum odd and not prime
odds = {(a, b) for a in range(7) for b in range(7) if (a + b) & 1 and
         a + b not in ps}

# subsequent dominos must sum even; can not sum 0 as sums of dominos must be !=
evens = ({(a, b) for a in range(7) for b in range(7) if not (a + b) & 1} -
         {(0, 0)})

def solve(dsf, rd, ts): # dsf = dominoes so far, rd = remaining dominos, totals
  if (len(dsf) > 14) and (ts[-1] in ps) and (ts[-2] in ps):
    yield dsf, ts

  else:
    for rl in (0, 1): # 0: add to left; 1: add to right
      
      if len(dsf) == 1 and rl == 0: # second domino must be on right
        continue

      # find a domino to add
      for s in range(7): 
        if ((nd := (dsf[0 - rl][rl], s)) in rd and # can domino be placed ?
            (tot := ts[-1] + sum(nd)) < 100 and # fewer than 100 spots     
           ((len(dsf) > 1 or tot not in ps))): # first two sums not prime:
          
          yield from solve(dsf + (nd,) if rl # add to right or
                     else (nd[::-1],) + dsf, # add to left
                           rd - {nd, nd[::-1]}, # remove both orientations
                           ts + (tot,)) # spot totals
count = 0        
sol = set()

for d1 in(odds): # select first domino (dominos appear twice: 1|2 2|1 for exmp.)
  for domsol, tt in solve((d1,), evens, (sum(d1),)):
    count += 1
    if domsol not in sol:
      sol |= {domsol}
      print("Solution number:", count, 'Six Dominos:', domsol[:6])
      print("Remaining dominos:", domsol[6:])
      print('Spot totals:', tt)
      print()
print("total paths to solutions", count)

full = False

p = (2, 3, 5, 7)

ps = p + tuple(x for x in range(11, 100, 2) if all(x % y for y in p))

# populate odd and even summing sets of dominos with both orienations

# first domino must sum odd and not prime

odds = {(a, b) for a in range(7) for b in range(7) if (a + b) & 1 and

a + b not in ps}

# subsequent dominos must sum even; can not sum 0 as sums of dominos must be !=

evens = ({(a, b) for a in range(7) for b in range(7) if not (a + b) & 1} -

{(0, 0)})

def solve(dsf, rd, ts): # dsf = dominoes so far, rd = remaining dominos, totals

if (len(dsf) > 14) and (ts[-1] in ps) and (ts[-2] in ps):

yield dsf, ts

else:

for rl in (0, 1): # 0: add to left; 1: add to right

if len(dsf) == 1 and rl == 0: # second domino must be on right

continue

# find a domino to add

for s in range(7):

if ((nd := (dsf[0 - rl][rl], s)) in rd and # can domino be placed ?

(tot := ts[-1] + sum(nd)) < 100 and # fewer than 100 spots

((len(dsf) > 1 or tot not in ps))): # first two sums not prime:

yield from solve(dsf + (nd,) if rl # add to right or

else (nd[::-1],) + dsf, # add to left

rd - {nd, nd[::-1]}, # remove both orientations

ts + (tot,)) # spot totals

count = 0

sol = set()

for d1 in(odds): # select first domino (dominos appear twice: 1|2 2|1 for exmp.)

Sunday Times Teaser 3256 – Domino-Do

by Victor Bryant

Published Sunday February 16 2025 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta