Sunday Times Teaser 3294 – Four by Four

by BRG on November 9, 2025

by Howard Williams

Published Sunday November 09 2025 (link)

Illustration of a 4x4 grid of empty cells. With the school inspector scheduled to visit her school, Tina is taking extra care in preparing her lesson plan. The lesson deals with areas, shapes and symmetries. She has produced soft cards on which have been printed a four by four grid, and will ask the pupils to cut the grid into two shapes of equal area, but by only cutting along the lines. She wanted them to create as many different possible shapes in this way, explaining that two shapes are different only if you can’t make one the same as the other by rotating it, turning it over, or both. It turned out that the maximum number of different shapes was the same as the number of pupils in the class.

How many pupils are there in the class?

From → Uncategorized

5 Comments Leave one →

BRG permalink

With some changes and speedups suggested by Frits.


from itertools import combinations

# the side length and the cells
s_len = 4
cells = set(range(s_len * s_len))

# list adjacent cells for each cell in a rectangular m x n grid
def adjacent(m, n):
  adj = []
  for xy in range(m * n):
    x, y = divmod(xy, s_len)
    s = set()
    for xx in (x - 1, x + 1):
      if 0 <= xx < s_len and xx * m + y < m * n:
        s.add(xx * m + y)
    for yy in (y - 1, y + 1):
      if 0 <= yy < n and x * m + yy < m * n:
        s.add(x * m + yy)
    adj.append(s)
  return adj

adj = adjacent(s_len, s_len)

# rotate the grid 90 degrees clockwise
rot = [3, 7, 11, 15, 2, 6, 10, 14, 1, 5, 9, 13, 0, 4, 8, 12]
def rotate(cs): return set(rot[c] for c in cs)
# mirror the grid left/right
mir = [3, 2, 1, 0, 7, 6, 5, 4, 11, 10, 9, 8, 15, 14, 13, 12]
def mirror(cs): return set(mir[c] for c in cs)

# find the canonical form for a set of cells
def canonical(cs):
  mn = 0
  ss = cs
  # rotate into four positions
  for _ in range(s_len):
    # the position and its left/right mirror
    for xs in [ss, mirror(ss)]:
      # move the shape to make min(x) and min(y) zero
      xm = min(divmod(x, s_len)[0] for x in xs)
      ym = min(divmod(x, s_len)[1] for x in xs)
      xs_ = tuple(sorted(((t[0] - xm) * s_len + t[1] - ym
             for xy in xs if (t := divmod(xy, s_len)))))
      if not mn or xs_ < mn:
        mn = xs_
    ss = rotate(ss)
  return mn

# return True if all cells in <cs> form a connected shape
def connected(cs, adj):
  cs_ = cs.copy() if type(cs) is set else set(cs)
  connected = {cs_.pop()}
  ongoing = True
  while ongoing:
    ongoing = False
    for c in tuple(cs_):
      if not connected.isdisjoint(adj[c]):
        connected.add(c)
        cs_.remove(c)
        ongoing = True
  return not cs_

ss = set()
# choose half the cells
for c in combinations(cells, 8):
  # are these cells and those remaining each connected
  if connected(c, adj) and connected(cells.difference(c), adj):
    ss.update({canonical(c)})

# output canonical shapes
gs = ['|', '|', '|', '|']
for cs in sorted(ss):
  cells = [[' ', ' ', ' ', ' '] for i in range(s_len)]
  for c in cs:
    x, y = divmod(c, s_len)
    cells[y][x] = 'X'
  for i in range(s_len):
    gs[i] += ''.join(cells[i]) + '|'
for i in range(s_len):
  print(f"{gs[i]}")
print(f"{''.join(f'{i:<5}' for i in range(1,len(ss) + 1))}")
print(f"{len(ss)} different shapes.")

from itertools import combinations

# the side length and the cells

s_len = 4

cells = set(range(s_len * s_len))

# list adjacent cells for each cell in a rectangular m x n grid

def adjacent(m, n):

adj = []

for xy in range(m * n):

x, y = divmod(xy, s_len)

s = set()

for xx in (x - 1, x + 1):

if 0 <= xx < s_len and xx * m + y < m * n:

s.add(xx * m + y)

for yy in (y - 1, y + 1):

if 0 <= yy < n and x * m + yy < m * n:

s.add(x * m + yy)

adj.append(s)

return adj

adj = adjacent(s_len, s_len)

# rotate the grid 90 degrees clockwise

rot = [3, 7, 11, 15, 2, 6, 10, 14, 1, 5, 9, 13, 0, 4, 8, 12]

def rotate(cs): return set(rot[c] for c in cs)

# mirror the grid left/right

mir = [3, 2, 1, 0, 7, 6, 5, 4, 11, 10, 9, 8, 15, 14, 13, 12]

def mirror(cs): return set(mir[c] for c in cs)

# find the canonical form for a set of cells

def canonical(cs):

mn = 0

ss = cs

# rotate into four positions

for _ in range(s_len):

# the position and its left/right mirror

for xs in [ss, mirror(ss)]:

# move the shape to make min(x) and min(y) zero

xm = min(divmod(x, s_len)[0] for x in xs)

ym = min(divmod(x, s_len)[1] for x in xs)

xs_ = tuple(sorted(((t[0] - xm) * s_len + t[1] - ym

for xy in xs if (t := divmod(xy, s_len)))))

if not mn or xs_ < mn:

mn = xs_

ss = rotate(ss)

return mn

# return True if all cells in <cs> form a connected shape

def connected(cs, adj):

cs_ = cs.copy() if type(cs) is set else set(cs)

connected = {cs_.pop()}

ongoing = True

while ongoing:

ongoing = False

for c in tuple(cs_):

if not connected.isdisjoint(adj[c]):

connected.add(c)

cs_.remove(c)

ongoing = True

return not cs_

ss = set()

# choose half the cells

for c in combinations(cells, 8):

# are these cells and those remaining each connected

if connected(c, adj) and connected(cells.difference(c), adj):

ss.update({canonical(c)})

# output canonical shapes

gs = ['|', '|', '|', '|']

for cs in sorted(ss):

cells = [[' ', ' ', ' ', ' '] for i in range(s_len)]

for c in cs:

x, y = divmod(c, s_len)

cells[y][x] = 'X'

for i in range(s_len):

gs[i] += ''.join(cells[i]) + '|'

for i in range(s_len):

print(f"{gs[i]}")

print(f"{''.join(f'{i:<5}' for i in range(1,len(ss) + 1))}")

print(f"{len(ss)} different shapes.")

Frits permalink

Nice output.

Reply

John Z permalink

Using ideas from Brian’s code and my initial incorrect version. This was done on my phone so there will be lapses in style. It can be speeded up but I will leave it for now.


# recursive part of contiguity verification
def contigr(val, array, seq):
  for (x, y) in ((0,1),(1,0),(0,-1),(-1,0)):
    if 3 >= (a:= seq[-1][0] + x) >= 0 and 3>= (b := seq[-1][1] + y) >= 0:
      if (a, b) not in seq and array[a][b] == val:
        yield from contigr(val, array, seq + [(a,b)])
  yield seq  
# contiguity verification 
def contig(val, array):
  # find coordinates of first cell = val
  p, q = divmod(sum(array, ()).index(val), 4)
  # res = set of cells contiguous with (p, q)
  res = set().union(*contigr(val, array, [(p, q)]))
  return len(res) == 8
    
# remove all-zero top rows and all-zero left columns
def normalize(b):
  a = list(x for x in b)
  for i in range(2):
    while sum(a[i]) == 0:
      for j in range(3):
        a[j] = a[j + 1]
      a[3] = (0, 0, 0, 0)
    while all(a[j][i] ==0 for j in range(4)):
      for k in range(4):
        a[k]= a[k][1:] + a[k][:1]
  return a
            
#rotate left
rol = lambda a: list(zip(*a))[::-1]
# horizontal flip
hfl = lambda a: a[::-1]
# rotate right
ror = lambda a: list(zip(*a[::-1]))
# vertical flip
vfl = lambda a: list(z[::-1] for z in a)
# rotate 180
r180 = lambda a: rol(rol(a))
# vertical flip then rotate left
vfrl = lambda a: rol(vfl(a))

transforms = (vfl, vfrl, rol, hfl, ror, r180)

sols, solsi = [], []
# generate shapes with 8 contiguous 1s and 8 0s
for i in range(2**16):
  if (b :=bin(i + 2**16)).count('1') == 9:
    xy =[tuple(int(b[j * 4 + i + 3]) for i in range(4)) for j in range(4)]
    if contig(1, xy) and contig(0, xy):
      sols.append(normalize(xy))
      solsi.append(i)
# eliminate equivalent shapes using 'same flag'
sf = list([] for i in range(len(sols)))
for i, sol in enumerate(sols[:-1]):
  for j in range(i + 1, len(sols)):
    if not sf[j] and any(sol == normalize(tr(sols[j])) for tr in transforms):
      sf[j] = 1
      
print(sf.count([]), 'shapes\n')

for i, sol in enumerate(sols):
  if not sf[i]:
    print(solsi[i], '\n')
    for row in sol:
      print(''.join('X' if c == 1 else ' ' for c in row))
    print('\n----------------\n')

# recursive part of contiguity verification

def contigr(val, array, seq):

for (x, y) in ((0,1),(1,0),(0,-1),(-1,0)):

if 3 >= (a:= seq[-1][0] + x) >= 0 and 3>= (b := seq[-1][1] + y) >= 0:

if (a, b) not in seq and array[a][b] == val:

yield from contigr(val, array, seq + [(a,b)])

yield seq

# contiguity verification

def contig(val, array):

# find coordinates of first cell = val

p, q = divmod(sum(array, ()).index(val), 4)

# res = set of cells contiguous with (p, q)

res = set().union(*contigr(val, array, [(p, q)]))

return len(res) == 8

# remove all-zero top rows and all-zero left columns

def normalize(b):

a = list(x for x in b)

for i in range(2):

while sum(a[i]) == 0:

for j in range(3):

a[j] = a[j + 1]

a[3] = (0, 0, 0, 0)

while all(a[j][i] ==0 for j in range(4)):

for k in range(4):

a[k]= a[k][1:] + a[k][:1]

return a

#rotate left

rol = lambda a: list(zip(*a))[::-1]

# horizontal flip

hfl = lambda a: a[::-1]

# rotate right

ror = lambda a: list(zip(*a[::-1]))

# vertical flip

vfl = lambda a: list(z[::-1] for z in a)

# rotate 180

r180 = lambda a: rol(rol(a))

# vertical flip then rotate left

vfrl = lambda a: rol(vfl(a))

transforms = (vfl, vfrl, rol, hfl, ror, r180)

sols, solsi = [], []

# generate shapes with 8 contiguous 1s and 8 0s

for i in range(2**16):

if (b :=bin(i + 2**16)).count('1') == 9:

xy =[tuple(int(b[j * 4 + i + 3]) for i in range(4)) for j in range(4)]

if contig(1, xy) and contig(0, xy):

sols.append(normalize(xy))

solsi.append(i)

# eliminate equivalent shapes using 'same flag'

sf = list([] for i in range(len(sols)))

for i, sol in enumerate(sols[:-1]):

for j in range(i + 1, len(sols)):

if not sf[j] and any(sol == normalize(tr(sols[j])) for tr in transforms):

sf[j] = 1

print(sf.count([]), 'shapes\n')

for i, sol in enumerate(sols):

if not sf[i]:

print(solsi[i], '\n')

for row in sol:

print(''.join('X' if c == 1 else ' ' for c in row))

print('\n----------------\n')

John Z permalink

Manual analysis shows that the most spread out or extensive shape possible is:

Python

XXXX X. X X X

1
2
3
4
5
6

XXXX
X. X
X
X

This and all other shapes can be made without using the three leftmost squares on the bottom row. So these squares can be removed from consideration. We can rewrite line 47 accordingly:

Python

for i in range(2 ** 13):

1
2
3

for i in range(2 ** 13):

Execution time is divided by 8. The same principle can applied to line 66 of Brian’s code

Reply

John Z permalink

Here is a faster more concise version with inspiration from Brian’s code: there are exactly 7 shape transformations plus the original shape; use of the min or max function to select one of the shapes.


# recursive part of contiguity verification
def contigr(val, array, seq):
  for (x, y) in ((0, 1),(1, 0),(0, -1),(-1, 0)):
    # stay within bounds of matrix
    if 3 >= (a:= seq[-1][0] + x) >= 0 and 3 >= (b := seq[-1][1] + y) >= 0:
      if (a, b) not in seq and array[a][b] == val:
        yield from contigr(val, array, seq + [(a,b)])
  yield seq
  
# contiguity verification 
def contig(val, array):
  # find coordinates of first cell = val
  p, q = divmod(sum(array, ()).index(val), 4)
  # res = set of cells contiguous with (p, q) and including (p, q)
  res = set().union(*contigr(val, array, [(p, q)]))
  return len(res) == 8
    
# remove all-zero top rows and all-zero left columns
def normalize(a):
  while sum(a[0]) == 0:
    a = a[1:] + a[:1]
  while all(a[j][0] == 0 for j in range(4)):
    for k in range(4):
      a[k]= a[k][1:] + a[k][:1]
  return a

#            the eight transforms (including no transform: same)        
#rotate left
rol = lambda a: list(zip(*a))[::-1]
# horizontal flip
hfl = lambda a: a[::-1]
# rotate right
ror = lambda a: list(zip(*a[::-1]))
# vertical flip
vfl = lambda a: list(z[::-1] for z in a)
# rotate 180
r180 = lambda a: rol(rol(a))
# vertical flip and rotate left
vfrol = lambda a : list(zip(*a))
# rotate left and vertical flip
rolvf = lambda a: list(zip(*a[::-1]))[::-1]
# no transformation
same = lambda a: a

transforms = (same, rol, hfl, ror, vfl, r180, vfrol, rolvf)

sols, solsi = [], []
# generate shapes with 8 contiguous 1s and 8 contiguous 0s
for i in range(2 ** 13):
  if (b := bin(i + 2 ** 16)).count('1') == 9:
    xy =[tuple(int(b[j * 4 + i + 3]) for i in range(4)) for j in range(4)]
    if contig(1, xy) and contig(0, xy):
      # keep one unique transform of shape (Credit Brian; could also use min)
      sol = max(normalize(tr(xy)) for tr in transforms)
      if sol not in sols:
        sols.append(sol)
        solsi.append(i)
      
print(len(sols), 'shapes\n')

for i, sol in enumerate(sols):
  print(solsi[i], '\n')
  for row in sol:
    print(''.join('X' if c == 1 else ' ' for c in row))
  print('\n----------------\n')

# recursive part of contiguity verification

def contigr(val, array, seq):

for (x, y) in ((0, 1),(1, 0),(0, -1),(-1, 0)):

# stay within bounds of matrix

if 3 >= (a:= seq[-1][0] + x) >= 0 and 3 >= (b := seq[-1][1] + y) >= 0:

if (a, b) not in seq and array[a][b] == val:

yield from contigr(val, array, seq + [(a,b)])

yield seq

# contiguity verification

def contig(val, array):

# find coordinates of first cell = val

p, q = divmod(sum(array, ()).index(val), 4)

# res = set of cells contiguous with (p, q) and including (p, q)

res = set().union(*contigr(val, array, [(p, q)]))

return len(res) == 8

# remove all-zero top rows and all-zero left columns

def normalize(a):

while sum(a[0]) == 0:

a = a[1:] + a[:1]

while all(a[j][0] == 0 for j in range(4)):

for k in range(4):

a[k]= a[k][1:] + a[k][:1]

return a

# the eight transforms (including no transform: same)

#rotate left

rol = lambda a: list(zip(*a))[::-1]

# horizontal flip

hfl = lambda a: a[::-1]

# rotate right

ror = lambda a: list(zip(*a[::-1]))

# vertical flip

vfl = lambda a: list(z[::-1] for z in a)

# rotate 180

r180 = lambda a: rol(rol(a))

# vertical flip and rotate left

vfrol = lambda a : list(zip(*a))

# rotate left and vertical flip

rolvf = lambda a: list(zip(*a[::-1]))[::-1]

# no transformation

same = lambda a: a

transforms = (same, rol, hfl, ror, vfl, r180, vfrol, rolvf)

sols, solsi = [], []

# generate shapes with 8 contiguous 1s and 8 contiguous 0s

for i in range(2 ** 13):

if (b := bin(i + 2 ** 16)).count('1') == 9:

xy =[tuple(int(b[j * 4 + i + 3]) for i in range(4)) for j in range(4)]

if contig(1, xy) and contig(0, xy):

# keep one unique transform of shape (Credit Brian; could also use min)

sol = max(normalize(tr(xy)) for tr in transforms)

if sol not in sols:

sols.append(sol)

solsi.append(i)

print(len(sols), 'shapes\n')

for i, sol in enumerate(sols):

print(solsi[i], '\n')

for row in sol:

print(''.join('X' if c == 1 else ' ' for c in row))

print('\n----------------\n')

Sunday Times Teaser 3294 – Four by Four

by Howard Williams

Published Sunday November 09 2025 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta