Teaser 3341: Sum of squares
From The Sunday Times, 4th October 2026 [link]
A seamstress is making a patchwork blanket from knitted squares of two colours, red and orange, forming a rectangular pattern. She has already sewn eight rows of seven squares each.
For each row, the columns with red squares are:
A: 1, 2, 4, 6, 7;
B: 2, 3, 6, 7;
C: 3, 4, 5, 7;
D: 1, 2, 3, 5;
E: 1, 2, 3, 5, 6;
F: 1, 3, 4, 7;
G: 2, 4, 6, 7;
H: 4, 5, 6.All other squares are orange.
She wants to assemble the rows (without reversing any left to right) into a rectangle, but choosing the order so that each column has exactly one run of exactly three consecutive reds, with all other reds having no red neighbours in the column, and with more reds in the top half than in the bottom half.
What should be the order of rows from top to bottom?
[teaser3341]
Ruud van der Ham, 
Frits, and 
NigelR are discussing. 
Alex.T.Sutherland, 
Hugo, 
Jim Randell 7:02 am on 4 October 2026 Permalink |
It is straightforward to try all possible orderings of the rows, and then for orders with more reds in the top half we can look for those that give valid columns.
The following Python program runs in 208ms (using PyPy3 8.0.0). (Internal runtime is 104ms).
(I think this is fast enough, but for a larger problem (or a faster runtime) we could use a more complex solver that does early rejection of columns that become invalid as they are constructed).
from enigma import (subsets, unzip, join, printf) rows = dict( A="XX X XX", B=" XX XX", C=" XXX X", D="XXX X ", E="XXX XX ", F="X XX X", G=" X X XX", H=" XXX ", ) # check a given order def check(ks): # construct the rows rs = list(rows[k] for k in ks) # check there are more reds in the first half if not (join(rs[:4]).count('X') > join(rs[4:]).count('X')): return # check each column has exactly 1 run of 3, and not other consecutive runs cs = map(join, unzip(rs)) for col in cs: # count runs of reds m = list(len(x) for x in str.split(col)) # there should be exactly one 3, no 2's, and no >3 if not (m.count(3) == 1 and m.count(2) == 0 and max(m) == 3): return # looks OK return True # choose an ordering for the rows for ks in subsets(rows.keys(), size=len, select='P', fn=join): if check(ks): printf("order = {ks}")Solution: [To Be Revealed]
LikeLike
Frits 11:00 am on 4 October 2026 Permalink |
isdisjoint() apparently also accepts a generator as argument.
from itertools import permutations labels = "ABCDEFGH" g = ((1, 1, 0, 1, 0, 1, 1), (0, 1, 1, 0, 0, 1, 1), (0, 0, 1, 1, 1, 0, 1), (1, 1, 1, 0, 1, 0, 0), (1, 1, 1, 0, 1, 1, 0), (1, 0, 1, 1, 0, 0, 1), (0, 1, 0, 1, 0, 1, 1), (0, 0, 0, 1, 1, 1, 0)) # solve by adding new rows def solve(k, g, ss): if k == 0: # check columns again for c in zip(*ss): if c[-3:] == (0, 1, 1): return # each column has exactly one run of exactly three consecutive reds if sum(c[i:i+3] == (1, 1, 1) for i in range(6)) != 1: return yield ss else: for r in g: # check columns for the last four rows if {(0, 1, 1, 0), (1, 1, 1, 1)}.isdisjoint(zip(*(ss[-3:] + (r, )))): yield from solve(k - 1, tuple(x for x in g if x != r), ss + (r, )) # minimal number of reds needed in top half mn_reds_th = (sum(sum(r) for r in g) + 1) // 2 # forbidden columns for first four rows fb = {(1, 1, 0, 1), (1, 1, 0, 0), (0, 1, 1, 0), (1, 1, 1, 1)} # first select the first 4 rows for r4 in permutations(g, 4): # top half must have more reds than bottom half if sum(sum(r) for r in r4) < mn_reds_th: continue # check the columns if not fb.isdisjoint(zip(*r4)): continue # add 4 more rows for s in solve(4, tuple(r for r in g if r not in r4), r4): print("answer:", ''.join(labels[g.index(r)] for r in s))LikeLike
Ruud van der Ham 11:06 am on 4 October 2026 Permalink |
Brute force.
import itertools rows = dict(A=[1, 2, 4, 6, 7], B=[2, 3, 6, 7], C=[3, 4, 5, 7], D=[1, 2, 3, 5], E=[1, 2, 3, 5, 6], F=[1, 3, 4, 7], G=[2, 4, 6, 7], H=[4, 5, 6]) for order in itertools.permutations(rows.keys()): columns = ["".join([" R"[c in rows[x]] for x in order]) for c in range(1, 8)] for column in columns: runs = list(map(len, column.split())) if runs.count(3) != 1 or any(n not in (1, 3) for n in runs): break else: r_in_top = "".join(column[:4] for column in columns).count("R") r_in_bottom = "".join(column[4:] for column in columns).count("R") if r_in_top > r_in_bottom: print(''.join(order))LikeLike