Teaser 3256: Domino-do
From The Sunday Times, 16th February 2025 [link] [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, …)?
[teaser3256]
Frits and 
John Crabtree, 
Ruud, 
GeoffR, and 
Tony Smith are discussing. 
Hugo and 
S2T2 
Jim Randell 8:25 am on 16 February 2025 Permalink |
The totals are all (different) odd numbers, so we must start with an odd domino (that is not prime), and each subsequently placed domino must be even (and not [0-0]). So at most one of the other even dominoes can remain unused.
Here is a constructive program. It starts by find possible placements for the first and second dominoes (an odd domino, and then a non-zero even domino, such that the totals are both non-prime), and then considers viable sets of at least 13 more even dominoes, that give a prime total for the entire line, and then looks for the final placement (that also gives a prime total after the penultimate placement), and then tries to construct a sequence of plays that gives a viable line of dominoes.
This Python 3 program runs in 625ms.
from enigma import (irange, subsets, is_prime, filter2, rev, remove, unpack, delete, multiset, printf) # a standard set of dominoes ds = list(subsets(irange(0, 6), size=2, select='R')) ds.remove((0, 0)) # but we can't play [0-0], as totals must be all different # canonical form of a domino def canonical(d): (x, y) = d; return (d if x < y else (y, x)) # add <k> dominoes from <ds> to the line <ss> (totals so far = <ts>) # return (<domino line>, <totals>, <unused dominoes>) def solve(k, ds, ss, ts): # are we done? if not k: yield (ss, ts, ds) else: # find candidates for the next domino ps = list() for (x, y) in ds: # place right if ss[-1][-1] == x: ps.append((-1, (x, y))) if x != y and ss[-1][-1] == y: ps.append((-1, (y, x))) # place left if ss[0][0] == x: ps.append((0, (y, x))) if x != y and ss[0][0] == y: ps.append((0, (x, y))) # make the placement for (i, d) in ps: t = ts[-1] + sum(d) ds_ = remove(ds, canonical(d)) ss_ = (ss + [d] if i == -1 else [d] + ss) yield from solve(k - 1, ds_, ss_, ts + [t]) # split the dominoes into odd and even (odds, evens) = filter2((lambda x: sum(x) % 2 == 1), ds) # collect required answers rs = multiset() # we start with an odd (non-prime) domino for d in odds: t = sum(d) if is_prime(t): continue # find a placement for the second (even) domino for (ss2, ts2, ds2) in solve(1, evens, [d], [t]): # which gives a non-prime total if is_prime(ts2[-1]): continue # the first placement is on the right, so reflect if necessary if canonical(ss2[1]) == d: ss2 = rev(rev(x) for x in ss2) # count the number of times each end occurs m = multiset.from_seq(*ss2) # look for a set of at least 13 additional even dominoes to place for ds in subsets(ds2, min_size=13): # calculate total number of pips (must be a prime, < 100) t = ts2[-1] + sum(sum(x) for x in ds) if not (t < 100 and is_prime(t)): continue # in the complete line at most 2 ends can appear an odd number of times if sum(n % 2 for n in m.combine(*ds).values()) > 2: continue # consider the final domino, so the penultimate total is prime for (i, dx) in enumerate(ds): tx = t - sum(dx) if not is_prime(tx): continue # place all the other dominoes printf("[trying {ss2} -> {dx}]") dsx = delete(ds, [i]) for (ssx, tsx, _) in solve(len(dsx), dsx, ss2, ts2): # can we place the final domino? for (ss, ts, _) in solve(1, [dx], ssx, tsx): printf("[{d} -> {ss} {ts}]") rs.add(tuple(ss[:6])) # output the answer(s) for (ss, n) in rs.most_common(): printf("{ss} ... [{n} solutions]")Solution: The leftmost dominoes are: [5-3] [3-3] [3-1] [1-1] [1-5] [5-5].
There are two possibilities for the completed line of dominos, each uses the same set of 15 dominos:
The lines are the same for the leftmost 10 dominoes, and then the rightmost 5 dominoes may appear in either direction.
The first play is the odd domino [5-4] (total = 9; odd, not prime), and this is followed on the right by [4-2] (total = 15; odd, not prime).
The remaining dominoes are played (in any viable order) until there is only [5-3] remaining to place on the left end. Before it is played the total is 89 (odd, prime), and after it is played the total is 97 (odd, prime).
The unused even domino is [2-6].
An even domino must have ends that are the same parity, and so since we start with an odd domino (which must have ends that are of different parities) the even numbers accumulate on the even side of the initial domino, and the odd numbers accumulate on the odd side of the initial domino. And when the line is complete every end apart from the two outside ends must be paired with its neighbour, and so must appear an even number of times. The exceptions are the outside ends of the line, so there must be two ends (one of them even, and one of them odd) that appear an odd number of times. And this is the basis for my faster program below that just looks for viable final arrangements of dominoes.
LikeLike
Jim Randell 10:52 am on 18 February 2025 Permalink |
My original program finds all possible play sequences that give a viable line of dominoes, but there are a lot of them.
However, for the most part, we don’t care about the order the dominoes are played in (only the first two moves, and the last move), so here is my program modified to just find viable domino lines.
It has an internal runtime of 2.5ms.
from enigma import (irange, subsets, is_prime, filter2, rev, remove, unpack, multiset, printf) # a standard set of dominoes ds = list(subsets(irange(0, 6), size=2, select='R')) ds.remove((0, 0)) # but we can't play [0-0], as totals must be all different # canonical form of a domino def canonical(d): (x, y) = d; return (d if x < y else (y, x)) # number of pips on a domino pips = sum # mirror a sequence of dominoes mirror = lambda ds: rev(rev(d) for d in ds) # add <k> dominoes from <ds> to the line <ss> # return (<domino line>, <unused dominoes>) def solve(k, ds, ss): # are we done? if not k: yield (ss, ds) else: # find candidates for the next domino ps = list() for (x, y) in ds: # place right if ss[-1][-1] == x: ps.append((x, y)) if x != y and ss[-1][-1] == y: ps.append((y, x)) # make the placement for p in ps: yield from solve(k - 1, remove(ds, canonical(p)), ss + [p]) # split the dominoes into odd and even (odds, evens) = filter2((lambda x: pips(x) % 2 == 1), ds) # we start with an odd (non-prime) domino for d in odds: if is_prime(pips(d)): continue # consider both starting orientations for d1 in (d, rev(d)): # find a placement for the second (even) domino for (ss2, ds2) in solve(1, evens, [d1]): # which gives a non-prime total t = sum(pips(d) for d in ss2) if is_prime(t): continue # the first placement is on the right, so reflect if necessary if canonical(ss2[1]) == d: ss2 = mirror(ss2) # count the number of times each end occurs m = multiset.from_seq(*ss2) # look for a set of at least 13 additional even dominoes to place for ds in subsets(ds2, min_size=13): # calculate total number of pips (must be a prime, < 100) tz = t + sum(pips(x) for x in ds) if not (tz < 100 and is_prime(tz)): continue # in the complete line only the 2 ends are unpaired if sum(n % 2 for n in m.combine(*ds).values()) != 2: continue # consider the final domino, so the penultimate total is prime for dx in ds: tx = tz - pips(dx) if not is_prime(tx): continue # split the remaining even dominoes by parity (ds0, ds1) = filter2((lambda x: x[0] % 2 == 0), ds) # extend the line to the right and left (dsr, dsl) = ((ds0, ds1) if ss2[-1][-1] % 2 == 0 else (ds1, ds0)) for (ssr, _) in solve(len(dsr), dsr, [ss2[-1]]): for (ssl, _) in solve(len(dsl), dsl, [rev(ss2[0])]): # check the final domino is played if not (canonical(ssr[-1]) == dx or canonical(ssl[-1]) == dx): continue # construct the final domino line rs = mirror(ssl) + ssr # output solution printf("{ss2} ... [{dx}]") # first two and last placements printf("-> {rs}") # completed lineLikeLiked by 1 person
Frits 6:33 pm on 17 February 2025 Permalink |
from enigma import SubstitutedExpression, is_prime, tuples # return sorted tuple stup = lambda x, y: (x, y) if x <= y else (y, x) # invalid digit / symbol assignments d2i = dict() for dgt in range(0, 8): vs = set() # only the ends may be seven (unused) if dgt == 7: vs.update('BCDEFGHIJKLMNOP') # HIJKLMNOP may not be odd if dgt % 2: vs.update('HIJKLMNOP') if dgt in {1, 3, 5}: vs.update('Q') # ABCDEFG may not be even if dgt % 2 == 0: vs.update('ABCDEFG') d2i[dgt] = vs # the alphametic puzzle p = SubstitutedExpression( [ # there are 15 dominoes with an even sum of which one may be unused # (6 with an odd number of spots and 9 with an even number of spots). # for the first domino (GH) pick one with an odd sum # temporarily the 2nd domino may be placed on both sides of the 1st domino # so if we find a solution the mirrored version is also valid # notation ABCDEF means a line of 5 dominoes (A-B)(B-C)(C-D)(D-E)(E-F) # odd nums oe even nums # ABCDEF GH IJKLMNOPQ (value 7 means unused) # 1st total is not prime "not is_prime(G + H)", # 2nd total is not prime (for now check both sides of 1st domino) "not is_prime(F + G + G + H) or not is_prime(G + H + H + I)", # at most one even sum is not needed "A + Q != 14", # a domino may not occur twice "len(set(so := [stup(x, y) for x, y in tuples(@odds + (G, ))])) == len(so)", # a domino may not occur twice (following lines added for performance) "stup(J, K) not in {stup(H, I)}", "stup(K, L) not in {stup(H, I), stup(I, J)}", "stup(L, M) not in {stup(H, I), stup(I, J), stup(J, K)}", "stup(M, N) not in {stup(H, I), stup(I, J), stup(J, K), stup(K, L)}", "stup(N, O) not in {stup(H, I), stup(I, J), stup(J, K), stup(K, L)," + "stup(L, M)}", "stup(O, P) not in {stup(H, I), stup(I, J), stup(J, K), stup(K, L)," + "stup(L, M), stup(M, N)}", "stup(P, Q) not in {stup(H, I), stup(I, J), stup(J, K), stup(K, L)," + "stup(L, M), stup(M, N), stup(N, O)}", # domino (0, 0) may not be present "(0, 0) not in tuples((H, ) + @evens)", # a domino may not occur twice (final check) "len(set(se := [stup(x, y) for x, y in tuples((H, ) + @evens)])) == len(se)", # last total is prime and less than 100 "(tot := 2 * sum(@odds + (G, H) + @evens) - (A if A < 7 else 14 + B) - " + "(Q if Q < 7 else 14 + P)) < 100 " + "and is_prime(tot)", # penultimate total is prime "is_prime(tot - (A + B if A < 7 else B + C)) or " + "is_prime(tot - (P + Q if Q < 7 else O + P))", ], macro=dict([("odds", "(A, B, C, D, E, F)")] + [("evens", "(I, J, K, L, M, N, O, P, Q)")]), answer="@odds, (G, H), @evens", d2i=d2i, # a number may not be surrounded by the same number distinct=("AC","CE","EG","BD","DF","HJ","JL","LN","NP","IK","KM","MO","OQ"), base=8, # domino values 0-6, 7 is used for n/a env=dict(stup=stup), reorder=0, verbose=0, # use 256 to see the generated code ) sols = set() # check possible solutions for ans in p.answers(): # right now a mirrored version might also be possible mirror = tuple(x[::-1] for x in ans[::-1]) for i, (f, m, l) in enumerate((ans, mirror)): # check if 2nd domino requirement is valid for the right-hand side if not is_prime(sum(m) + m[-1] + l[0]): f7 = (f + m)[:7] if f[0] < 7 else (f + m)[1:8] f6 = tuple(f"{x}-{y}" for x, y in tuples(f7)) sols.add(f6) for f6 in sols: print("answer:", ', '.join(f6))LikeLike
Frits 1:15 pm on 20 February 2025 Permalink |
from itertools import product # primes below 100 P = {3, 5, 7} P |= {2} | {x for x in range(11, 100, 2) if all(x % p for p in P)} # return sorted tuple stup = lambda x, y: (x, y) if x <= y else (y, x) # dominoes with even sum, except (0, 0) evens = [(i, j) for j in range(7) for i in range(0 if j else 1, j + 1) if(i + j) % 2 == 0] o_evens = [(x, y) for x, y in evens if x % 2] # with odd spots e_evens = [(x, y) for x, y in evens if x % 2 == 0] # with even spots # add <k> dominoes from set <ds> to the line <ss> def solve(k, ds, ss): # are we done? if not k: yield ss else: # place next domino to the right for (x, y) in ds: if ss[-1][-1] == x: yield from solve(k - 1, ds.difference([stup(x, y)]), ss + [(x, y)]) if x != y and ss[-1][-1] == y: yield from solve(k - 1, ds.difference([stup(y, x)]), ss + [(y, x)]) # the total of all 15 even sum dominoes is 4*(1+3+5) + 5*(0+2+4+6) = 96 t_even = 96 sols = set() # process all odd non-prime domino sums for odd_sum in range(1, 12, 2): if odd_sum in P: continue t = t_even + odd_sum # odd nums oe even nums # ABCDEF GH IJKLMNOPQ # we can't have all 9 dominoes with even spots otherwise both 2, 4 and 6 # would need to occur at least three times. Only with 2 of them this is # possible (using the H and the Q position) so position Q will be unused. missing_sums = [i for i in range(2, 13, 2) if (t - i) in P] for msum in missing_sums: # which even spots dominoes have sum <msum> ? # domino (x, x) in this case is not possible (x in {2, 4, 6}) as it forces # the two other numbers in {2, 4, 6} on positions H and P # so we can't make 3 dominoes with 0 anymore (position H or P is needed). for m in set(stup(d, msum - d) for d in range(0, 7, 2) if 0 <= msum - d <= 6 and 2 * d != msum): # domino <m> is not used for G in (1, 3, 5): H = odd_sum - G if not (0 <= H <= 6): continue # add dominoes with even spots and an even sum es = list(solve(len(e_evens) - 1, set(e_evens).difference([m]), [(G, H)])) # add dominoes with odd spots and an even sum os = list(solve(len(o_evens), set(o_evens), [(H, G)])) # combine them into ... for e, o in product(es, os): # ... a line of 15 dominoes ds = [x[::-1] for x in o[1:][::-1]] + e t = sum(sum(x) for x in ds) # check penultimate domino if all((t - sum(ds[i])) not in P for i in [-1, 0]): continue # check whether 2nd domino (at right-hand) is not prime if (odd_sum + sum(e[1])) not in P: sols.add(tuple(ds[:6])) if (odd_sum + sum(o[1])) not in P: dsrev = [x[::-1] for x in ds[::-1]] sols.add(tuple(dsrev[:6])) for sol in sols: print(f"answer: {', '.join(f'{x}-{y}' for x, y in sol)}")LikeLike