Brain-Teaser 973: Square-rigger
From The Sunday Times, 15th March 1981 [link]
Young Mary, who is good at manipulating figures, was playing with her standard set of dominoes and seeing what numerical structures she could form with them, treating each half-domino as a digit according to its number of spots (“blank” being 0).
Starting with double-6/double-5/double-4 laid end-to-end in a row, she built forwards and downwards from that beginning, placing dominoes across and apparently at random, until she had completed a solid rectangle by slotting into the only remaining gaps, in its farther half, her last two dominoes which were 4-&-blank and 2-&-blank.
Whereupon she called out to me: “Uncle, do come and look! I’ve managed to arrange all my dominoes in a rectangle so that the numbers formed by the four halves in each column are all dissimilar 4-digit squares”.
“Are you quite sure about that?” I temporised.
“Certain,” she replied. “And they’re pretty well in correct order of magnitude too!”.
When I protested that this was quite impossible with dominoes, she said reproachfully: “But Uncle, I never said that ALL the squares appear in the right order, did I? Actually there are just two of them — both among the seven smallest present — which do not; but every single square except those two is definitely just where it would be if all those appearing were strictly in order of magnitude”.
She was perfectly correct. And you don’t need dominoes to figure out …
Which four of Mary’s together formed columns 7 and 8 of her rectangle? (Use figures, e.g. 4-0 = four-&-blank).
This was the final puzzle to use the title Brain-Teaser. The next puzzle was Brain teaser 974.
[teaser973]
S2T2 
Jim Randell 8:04 am on 6 June 2023 Permalink |
A standard set of dominoes has 28 dominoes, each with 2 numbers on, so there are 56 numbers in total, consisting of 8 copies of each of the digits from 0 to 6.
The program starts by constructing a list of square numbers that can be constructed using only the digits available on dominoes (i.e. the digits 0-6). It then constructs a viable sequence of squares that use the required 56 digits between them, and we consider swapping a pair of the numbers in the second half of the list to give Mary’s list of squares.
We then turn the numbers into a 14×4 grid and use the [[
DominoGrid()]] solver from the enigma.py library to find viable arrangements of dominoes.The program runs in 558ms. (Internal runtime is 412ms).
from enigma import ( DominoGrid, irange, subsets, multiset, flatten, unzip, union, group, update, seq_ordered as ordered, seq_get as get, join, printf ) # available digits on dominoes digits = set("0123456") # find 4-digit squares that can be represented by dominoes sqs = list() for i in irange(32, 81): s = str(i * i) if not digits.issuperset(s): continue sqs.insert(0, s) # construct viable sequences of squares (in descending order) # - each of the digits 0-6 must be used exactly 8 times # - the sequence must start: 6xxx, 6xxx, 5xxx, 5xxx, 4xxx, 4xxx def squares(sqs, ds=None, ss=[]): # ds counts the digits remaining to be used if ds is None: ds = multiset.from_seq('0123456', count=8) # are we done? n = len(ss) if n == 14: yield ss elif not (n + len(sqs) < 14): # choose the next square to include for (i, sq) in enumerate(sqs): # 0, 1 must be 6xxx if n < 2: if sq[0] < '6': break # 2, 3 must be 5xxx elif n < 4: if sq[0] > '5': continue if sq[0] < '5': break # 4, 5 must be 4xxx elif n < 6: if sq[0] > '4': continue if sq[0] < '4': break # can we add sq to the sequence? if ds.issuperset(sq): # solve for the remaining squares in the list yield from squares(sqs[i + 1:], ds.difference(sq), ss + [sq]) # domino ordering order = lambda xs: ordered(xs, reverse=1) # find dominoes used in specified columns (1-indexed) def dominoes(p, grid, cols): # indices of columns ks = union(irange(x - 1, 55, step=14) for x in cols) # find the dominoes at the specified indices g = group(ks, by=get(grid), f=get(p.grid)) # extract dominoes that are entirely in selected columns for v in g.values(): if len(v) == 2: yield order(v) # collect solutions rs = set() # consider possible sequences of squares for ss in squares(sqs): # choose two squares from index 7-13 to swap for (i, j) in subsets(irange(7, 13), size=2): ss_ = update(ss, [(i, ss[j]), (j, ss[i])]) # construct the grid p = DominoGrid(14, 4, list(int(x) for x in flatten(unzip(ss_)))) # and solve it for (grid, used) in p.solve(fixed=[(0, 1), (2, 3), (4, 5)]): # check that (4, 0) and (2, 0) occur in columns 8 - 14 ds = set(dominoes(p, grid, irange(8, 14))) if not ((4, 0) in ds and (2, 0) in ds): continue # find the 4 dominoes in columns 7 and 8 ds = order(dominoes(p, grid, [7, 8])) if len(ds) != 4: continue rs.add(ds) printf("squares = {ss_}", ss_=join(ss_, sep=" ")) printf() p.output_solution((grid, used)) printf("cols 7/8 = {ds}", ds=join(ds, sep=" ")) printf("--") # output solution for ds in rs: printf("answer = {ds}", ds=join(ds, sep=" "))Solution: The dominoes making up columns 7 and 8 are: [6-0] [5-0] [3-3] [2-0].
There is only one arrangement of square numbers that use each of the digits 0-6 exactly 8 times:
And there are 2 (slightly) different ways the required grid can be constructed from a set of dominoes, here is one way:
The [6-3] and [6-4] dominoes can be placed either horizontally or vertically to give the two layouts.
If the indicated columns were swapped the squares would be in strict descending numerical order.
The [2-0] and [4-0] dominoes (highlighted) were placed last in the right-hand half of the layout. If this condition is removed more arrangements are viable (16 in total), but the sequence of squares (and answer to the puzzle) remains the same.
LikeLike