Sunday Times Teaser 3214 – Squaring the Square

by BRG on 26 April 2024

by Peter Good

Published Friday April 26 2024 (link)

Clark took a sheet of A4 paper (8.27 × 11.69 inches) and cut out a large square with dimensions a whole number of inches. He cut this into an odd number of smaller squares, each with dimensions a whole number of inches. These were of several different sizes and there was a different number of squares of each size; in fact, the number of different sizes was the largest possible, given the above.

It turns out that there is more than one way that the above dissection can be made, but Clark chose the method that gave the smallest number of smaller squares.

How many smaller squares were there?

From → Uncategorized

10 Comments Leave one →

BRG permalink

My thanks to Frits for analysing my rectangle packing code and discovering a major improvement when duplicate rectangles are being packed. In short, if we have several squares of the same size, each level of recursion will fit the square in every possible position but, although we will have fitted the squares in a different order, the end result will be the same. In effect we have fitted a permutation of these squares when we only need to fit them once. Also, if the first square cannot be fitted in any position, we don’t need to consider duplicate squares since they won’t fit either. Hence for each recursion level we only need to consider one square of each different size.

Here is a download link for jiigsaw.py.


from jigsaw import create_rpiece, print_rect, solve_rect

def pack(ds):
  pcs = dict()
  for i, (p, q) in enumerate([(x, x) for x in ds[::-1]]):
    pcs[chr(ord('A') + i)] = create_rpiece(p, q)
  for g in solve_rect(pcs.keys(), n, n, pcs):
    return g
  return None
  
# return a list of integers (and their multiset) with
# different multiplicities that, when squared, sum to <n>
def sum_sqs(n, ds=[]):
  if n == 0:
    c = {d:ds.count(d) for d in set(ds)}
    if len(t := c.values()) == len(set(t)):
      yield ds, c
  else:
    for i in range(1, int(n ** (1 / 2)) + 1):
      if not ds or i >= ds[-1]:
        yield from sum_sqs(n - i * i, ds + [i])

max_ds = 0
min_sq = 100
sol = None
# consider the initial square size
for n in range(3, 9):
  # find smaller squares that could cover it
  for s, c in sum_sqs(n * n):
    # the number of squares is odd and there
    # are several possible covers
    if len(set(s)) < 2 or not len(s) % 2:
      continue
    if(g := pack(s)):
    # do the squares actually cover the initial square?
      # find the maximum number of different square sizes
      if (t := len(set(s))) >= max_ds:
        if t > max_ds:
          max_ds = t
          min_sq = 100
          sol = None
        # now find the minimum total number of squares
        if (t := sum(s)) <= min_sq:
          min_sq = t
          sol = (g, n, n)
          print(n, c, sum(c.values()))
          
if sol:      
  print_rect(*sol)

from jigsaw import create_rpiece, print_rect, solve_rect

def pack(ds):

pcs = dict()

for i, (p, q) in enumerate([(x, x) for x in ds[::-1]]):

pcs[chr(ord('A') + i)] = create_rpiece(p, q)

for g in solve_rect(pcs.keys(), n, n, pcs):

return g

return None

# return a list of integers (and their multiset) with

# different multiplicities that, when squared, sum to <n>

def sum_sqs(n, ds=[]):

if n == 0:

c = {d:ds.count(d) for d in set(ds)}

if len(t := c.values()) == len(set(t)):

yield ds, c

else:

for i in range(1, int(n ** (1 / 2)) + 1):

if not ds or i >= ds[-1]:

yield from sum_sqs(n - i * i, ds + [i])

max_ds = 0

min_sq = 100

sol = None

# consider the initial square size

for n in range(3, 9):

# find smaller squares that could cover it

for s, c in sum_sqs(n * n):

# the number of squares is odd and there

# are several possible covers

if len(set(s)) < 2 or not len(s) % 2:

continue

if(g := pack(s)):

# do the squares actually cover the initial square?

# find the maximum number of different square sizes

if (t := len(set(s))) >= max_ds:

if t > max_ds:

max_ds = t

min_sq = 100

sol = None

# now find the minimum total number of squares

if (t := sum(s)) <= min_sq:

min_sq = t

sol = (g, n, n)

print(n, c, sum(c.values()))

if sol:

print_rect(*sol)

Frits permalink

I reused some of my code for Teaser 3069.


from itertools import product

# "these were of several different sizes" (let's say more than three)
min_sizes = 4

# decompose <t> into <k> numbers from <ns> so that sum(<k> numbers) equals <t>
def decompose(t, k=1, ns=[], s=[], mn=min_sizes):
  if k == 1:
    if t in ns and t >= s[-1]:
      s_ = s + [t]
      cnts = [s_.count(x) for x in set(s_)]
      # there was a different number of squares of each size
      if len(cnts) >= mn and len(cnts) == len(set(cnts)):
        yield (s_, cnts)
  else:
    for n in ns:
      if k * n > t: break
      if s and n < s[-1]: continue   # sequence is non-decreasing
      yield from decompose(t - n,  k - 1, ns, s + [n])
 
# return grid coordinates (top left, bottom right) where piece w x w will fit
def grid_coords(grid, w):
  res = []
  for i in range(M, X + M):
    for j in range(M, X + M):
      if grid[i][j] == 0:
        if all(grid[x][y] == 0 for x in range(i, i + w) 
                               for y in range(j, j + w)):
         res.append([(i - M, j - M), (i - M + w - 1, j - M + w - 1)])
  return res        

# print grid without borders
def grid_print(grid, M):
  X = len(grid[0]) - 2 * M
  for i, g in enumerate(grid):
    if M <= i < X + M:
      print(*[f'{x:>2}' for x in g[M:-M]])
  print()    

# fit <k> pieces into empty spots in the grid    
def fit(r, k, s, M=0):
  if k == 1:
    # check if last piece fits
    if coords := grid_coords(s, r[0]):
      (tl, rb) = (coords[0][0], coords[0][1])
      for (i, j) in product(range(tl[0], rb[0] + 1), range(tl[1], rb[1] + 1)): 
        s[i + M][j + M] = k  
      yield s       
  else:
    w = r[0]   # pick first remaining piece from list
    for tl, rb in grid_coords(s, w):
      if k == N: 
        if tl != (0, 0): continue # biggest piece in NW corner
      # update piece in the grid s
      for (i, j) in product(range(tl[0], rb[0] + 1), range(tl[1], rb[1] + 1)): 
        s[i + M][j + M] = k    
      
      # try to fit other pieces in the grid
      yield from fit(r[1:], k - 1, s, M)   
      # backtrack
      for (i, j) in product(range(tl[0], rb[0] + 1), range(tl[1], rb[1] + 1)):
        s[i + M][j + M] = 0 
      
# return first grid that fits
def first_valid_grid(rs, grid, M):   
  for sol in fit(rs, len(rs), grid, M):
    return sol
  return []

# initialize grid X + 2M by X + 2M
# (with dummy borders of size M so we can check outside of a X by X matrix)
def init_grid(X, M):
  g = [[99 for i in range(X + 2 * M)] for j in range(X + 2 * M)]
  # initialize inner grid to 0 
  for i in range(X):
    for j in range(X):
      g[i + M][j + M] = 0
  return g    

sqs = [i * i for i in range(1, 9)]

# determine sum of <min_sizes> lowest squares
mand = sum(x * x for x in range(1, min_sizes + 1))

max_diff_sizes = 0
sols = []
# process sizes of the large square (at least 5x5)
for sq in sqs[::-1][:-4]:
  X = int(sq**.5)            # width and height of the large square
  sqs_ = [x for x in sqs if x < sq]
  max_pieces = sq - mand
  # start with a high number of pieces
  for np in range(max_pieces - (max_pieces % 2 == 0), 3, -2):
    # break if triangular root of <np> get's too low
    if int(0.5 * ((8 * np + 1)**.5 - 1.0)) < max_diff_sizes: break
    # make total <sq> from small squares
    for p, cnts in decompose(sq, np, sqs_):
      # ignore decompositions with a few different sizes
      if (ln := len(cnts)) >= max_diff_sizes:
        pieces = [int(x**.5) for x in p[::-1]]
        M, N = max(pieces), len(pieces)
        # find a grid so that all pieces fit into the grid
        if (sol := first_valid_grid(pieces, init_grid(X, M) , M)):
          if ln > max_diff_sizes:
            sols = []
          # store data, count of smallest piece first
          sols.append((p.count(min(p)), sol, np, M, pieces))
        max_diff_sizes = len(cnts)

if len(sols) < 2:
  print("no multiple dissections have been found")
else: 
  # print the solution with the the smallest number of smaller squares
  for n_smallest, sol, m, M, pieces in sorted(sols):
    print("answer:", m, "\n")
    print("pieces:", *[(x, x) for x in pieces], "\n")
    grid_print(sol, M)
    break

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

from itertools import product

# "these were of several different sizes" (let's say more than three)

min_sizes = 4

# decompose <t> into <k> numbers from <ns> so that sum(<k> numbers) equals <t>

def decompose(t, k=1, ns=[], s=[], mn=min_sizes):

if k == 1:

if t in ns and t >= s[-1]:

s_ = s + [t]

cnts = [s_.count(x) for x in set(s_)]

# there was a different number of squares of each size

if len(cnts) >= mn and len(cnts) == len(set(cnts)):

yield (s_, cnts)

else:

for n in ns:

if k * n > t: break

if s and n < s[-1]: continue # sequence is non-decreasing

yield from decompose(t - n, k - 1, ns, s + [n])

# return grid coordinates (top left, bottom right) where piece w x w will fit

def grid_coords(grid, w):

res = []

for i in range(M, X + M):

for j in range(M, X + M):

if grid[i][j] == 0:

if all(grid[x][y] == 0 for x in range(i, i + w)

for y in range(j, j + w)):

res.append([(i - M, j - M), (i - M + w - 1, j - M + w - 1)])

return res

# print grid without borders

def grid_print(grid, M):

X = len(grid[0]) - 2 * M

for i, g in enumerate(grid):

if M <= i < X + M:

print(*[f'{x:>2}' for x in g[M:-M]])

print()

# fit <k> pieces into empty spots in the grid

def fit(r, k, s, M=0):

if k == 1:

# check if last piece fits

if coords := grid_coords(s, r[0]):

(tl, rb) = (coords[0][0], coords[0][1])

for (i, j) in product(range(tl[0], rb[0] + 1), range(tl[1], rb[1] + 1)):

s[i + M][j + M] = k

yield s

else:

w = r[0] # pick first remaining piece from list

for tl, rb in grid_coords(s, w):

if k == N:

if tl != (0, 0): continue # biggest piece in NW corner

# update piece in the grid s

for (i, j) in product(range(tl[0], rb[0] + 1), range(tl[1], rb[1] + 1)):

s[i + M][j + M] = k

# try to fit other pieces in the grid

yield from fit(r[1:], k - 1, s, M)

# backtrack

for (i, j) in product(range(tl[0], rb[0] + 1), range(tl[1], rb[1] + 1)):

s[i + M][j + M] = 0

# return first grid that fits

def first_valid_grid(rs, grid, M):

for sol in fit(rs, len(rs), grid, M):

return sol

return []

# initialize grid X + 2M by X + 2M

# (with dummy borders of size M so we can check outside of a X by X matrix)

def init_grid(X, M):

g = [[99 for i in range(X + 2 * M)] for j in range(X + 2 * M)]

# initialize inner grid to 0

for i in range(X):

for j in range(X):

g[i + M][j + M] = 0

return g

sqs = [i * i for i in range(1, 9)]

# determine sum of <min_sizes> lowest squares

mand = sum(x * x for x in range(1, min_sizes + 1))

max_diff_sizes = 0

sols = []

# process sizes of the large square (at least 5x5)

for sq in sqs[::-1][:-4]:

X = int(sq**.5) # width and height of the large square

sqs_ = [x for x in sqs if x < sq]

max_pieces = sq - mand

# start with a high number of pieces

for np in range(max_pieces - (max_pieces % 2 == 0), 3, -2):

# break if triangular root of <np> get's too low

if int(0.5 * ((8 * np + 1)**.5 - 1.0)) < max_diff_sizes: break

# make total <sq> from small squares

for p, cnts in decompose(sq, np, sqs_):

# ignore decompositions with a few different sizes

if (ln := len(cnts)) >= max_diff_sizes:

pieces = [int(x**.5) for x in p[::-1]]

M, N = max(pieces), len(pieces)

# find a grid so that all pieces fit into the grid

if (sol := first_valid_grid(pieces, init_grid(X, M) , M)):

if ln > max_diff_sizes:

sols = []

# store data, count of smallest piece first

sols.append((p.count(min(p)), sol, np, M, pieces))

max_diff_sizes = len(cnts)

if len(sols) < 2:

print("no multiple dissections have been found")

else:

# print the solution with the the smallest number of smaller squares

for n_smallest, sol, m, M, pieces in sorted(sols):

print("answer:", m, "\n")

print("pieces:", *[(x, x) for x in pieces], "\n")

grid_print(sol, M)

break

Frits permalink

A new version:

– allowing for at least three different sizes (instead of four)
– no dummy border anymore
– not placing the largest square in the top left corner (without proof)
– attempting to increase min_sizes as soon as possible
– not trying to fit 1×1 squares into the grid
– skipping variations where larger squares (as of 2×2) are one position of an edge
– alternate searching (between up and down)


from itertools import product

# "these were of several different sizes"
min_sizes = 3

# decompose <t> into <k> numbers from <ns> so that sum(<k> numbers) equals <t>
def decompose(t, k=1, ns=[], mn=min_sizes, s=[]):
  if k == 1:
    if t in ns and t >= s[-1]:
      s_ = s + [t]
      cnts = [s_.count(x) for x in set(s_)]
      # there was a different number of squares of each size
      if len(cnts) >= mn and len(cnts) == len(set(cnts)):
        yield (s_, cnts)
  else:
    for n in ns:
      if k * n > t: break
      if s and n < s[-1]: continue   # sequence is non-decreasing
      yield from decompose(t - n,  k - 1, ns, mn, s + [n])

# return grid coordinates (top left, bottom right) where piece w x w will fit
def grid_coords(g, w, dim):
  res = []
  for i in range(dim + 1 - w):
    for j in range(dim + 1 - w):
      if g[i][j] == 0:
        if all(g[x][y] == 0 for x in range(i, i + w)
                            for y in range(j, j + w)):
          res.append([(i, j), (i + w - 1, j + w - 1)])
  return res

# return grid coordinates (top left, bottom right) where piece w x w will fit
def grid_coords_rev(g, w, dim):
  res = []
  for i in range(dim - w, -1, -1):    # reverse order
    for j in range(dim - w, -1, -1):
      if g[i][j] == 0:
        if all(g[x][y] == 0 for x in range(i, i + w)
                            for y in range(j, j + w)):
         res.append([(i, j), (i + w - 1, j + w - 1)])
  return res

def print_grid(g):
  dim = len(g[0])
  for i, r in enumerate(g):
    if i < dim:
      print(*[f'{x:>2}' for x in r],
            "" if i != dim // 2 else "        0 for 1x1 squares")
  print()

# fit <k> pieces into empty spots in the grid
def pack_squares(r, k, g, dim, np):
  # don't try to fit in 1x1 squares
  if k == 1 or (k > 1 and r[1] == 1):
    # check if last bigger piece fits
    if coords := grid_coords(g, r[0], dim):
      (tl, rb) = (coords[0][0], coords[0][1])
      for (i, j) in product(range(tl[0], rb[0] + 1), range(tl[1], rb[1] + 1)):
        g[i][j] = k
      yield g
      # no backtracking as only one solution is needed
  else:
    w = r[0]   # pick first remaining piece from list
    # alternate row searching (between down and up)
    for tl, rb in (grid_coords if k % 2 else grid_coords_rev)(g, w, dim):
      # skip blocks 2x2 or larger that are one from the edge as the gap must be
      # filled with 1's so we have 2 versions if we move the block to the edge
      if 1 in {tl[0], tl[1]} or (dim - w - 1) in {tl[0], tl[1]}: continue

      if k == np:   # first piece to be placed
        # remove rotations / reflections (first piece in W-NW section)
        if tl[0] < tl[1] or dim - (tl[0] + w) < tl[0]: continue

      # update piece in the grid <s>
      for (i, j) in product(range(tl[0], rb[0] + 1), range(tl[1], rb[1] + 1)):
        g[i][j] = k

      # try to fit other pieces in the grid
      yield from pack_squares(r[1:], k - 1, g, dim, np)

      # backtrack
      for (i, j) in product(range(tl[0], rb[0] + 1), range(tl[1], rb[1] + 1)):
        g[i][j] = 0

# return first grid that fits
def first_valid_grid(rs, g, dim, np):
  for sol in pack_squares(rs, np, g, dim, np):
    return sol
  return []

init_grid = lambda dim: [[0 for _ in range(dim)] for _ in range(dim)]

sqs = [i * i for i in range(1, 9)]

# determine sum of <min_sizes> lowest squares
mand = sum(i * i for i in range(1, min_sizes + 1))

max_diff_sizes = 0
sols = []
# process sizes of the large square (at least 5x5)
for sq in sqs[::-1][:-4]:
  N = int(sq**.5)            # width and height of the large square
  sqs_ = [x for x in sqs if x < sq]
  max_pieces = sq - mand

  lst = []
  # determine all combinations of smaller squares that sum to square <sq>
  for np in range(max_pieces - (max_pieces % 2 == 0), 3, -2):
    for p, cnts in decompose(sq, np, sqs_, min_sizes):
      lst.append((p, cnts))

  # start with the combinations with the most smaller squares
  for p, cnts in sorted(lst, key = lambda x: len(x[1]), reverse=1):
    if (ln := len(cnts)) < min_sizes: break

    # ignore combinations with not enough different sizes
    if ln >= max_diff_sizes:
      pieces = [int(x**.5) for x in p[::-1]]
      # find a grid so that all pieces fit into the grid
      if (sol := first_valid_grid(pieces, init_grid(N), N, len(pieces))):
        if ln > max_diff_sizes:
          max_diff_sizes, min_sizes = ln, ln
          mand = sum(x * x for x in range(1, min_sizes + 1))
          max_pieces = sq - mand
          sols = []
        # store solution
        sols.append((sol, pieces))

if len(sols) < 2:
  print("no multiple dissections have been found")
else:
  # print the solution with the the smallest number of smaller squares
  for sol, pieces in sorted(sols, key = lambda x: len(x[1])):
    print("answer:", len(pieces), "squares\n")
    print("pieces:", *[(x, x) for x in pieces], "\n")
    print_grid(sol)
    break

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

from itertools import product

# "these were of several different sizes"

min_sizes = 3

# decompose <t> into <k> numbers from <ns> so that sum(<k> numbers) equals <t>

def decompose(t, k=1, ns=[], mn=min_sizes, s=[]):

if k == 1:

if t in ns and t >= s[-1]:

s_ = s + [t]

cnts = [s_.count(x) for x in set(s_)]

# there was a different number of squares of each size

if len(cnts) >= mn and len(cnts) == len(set(cnts)):

yield (s_, cnts)

else:

for n in ns:

if k * n > t: break

if s and n < s[-1]: continue # sequence is non-decreasing

yield from decompose(t - n, k - 1, ns, mn, s + [n])

# return grid coordinates (top left, bottom right) where piece w x w will fit

def grid_coords(g, w, dim):

res = []

for i in range(dim + 1 - w):

for j in range(dim + 1 - w):

if g[i][j] == 0:

if all(g[x][y] == 0 for x in range(i, i + w)

for y in range(j, j + w)):

res.append([(i, j), (i + w - 1, j + w - 1)])

return res

# return grid coordinates (top left, bottom right) where piece w x w will fit

def grid_coords_rev(g, w, dim):

res = []

for i in range(dim - w, -1, -1): # reverse order

for j in range(dim - w, -1, -1):

if g[i][j] == 0:

if all(g[x][y] == 0 for x in range(i, i + w)

for y in range(j, j + w)):

res.append([(i, j), (i + w - 1, j + w - 1)])

return res

def print_grid(g):

dim = len(g[0])

for i, r in enumerate(g):

if i < dim:

print(*[f'{x:>2}' for x in r],

"" if i != dim // 2 else " 0 for 1x1 squares")

print()

# fit <k> pieces into empty spots in the grid

def pack_squares(r, k, g, dim, np):

# don't try to fit in 1x1 squares

if k == 1 or (k > 1 and r[1] == 1):

# check if last bigger piece fits

if coords := grid_coords(g, r[0], dim):

(tl, rb) = (coords[0][0], coords[0][1])

for (i, j) in product(range(tl[0], rb[0] + 1), range(tl[1], rb[1] + 1)):

g[i][j] = k

yield g

# no backtracking as only one solution is needed

else:

w = r[0] # pick first remaining piece from list

# alternate row searching (between down and up)

for tl, rb in (grid_coords if k % 2 else grid_coords_rev)(g, w, dim):

# skip blocks 2x2 or larger that are one from the edge as the gap must be

# filled with 1's so we have 2 versions if we move the block to the edge

if 1 in {tl[0], tl[1]} or (dim - w - 1) in {tl[0], tl[1]}: continue

if k == np: # first piece to be placed

# remove rotations / reflections (first piece in W-NW section)

if tl[0] < tl[1] or dim - (tl[0] + w) < tl[0]: continue

# update piece in the grid <s>

for (i, j) in product(range(tl[0], rb[0] + 1), range(tl[1], rb[1] + 1)):

g[i][j] = k

# try to fit other pieces in the grid

yield from pack_squares(r[1:], k - 1, g, dim, np)

# backtrack

for (i, j) in product(range(tl[0], rb[0] + 1), range(tl[1], rb[1] + 1)):

g[i][j] = 0

# return first grid that fits

def first_valid_grid(rs, g, dim, np):

for sol in pack_squares(rs, np, g, dim, np):

return sol

return []

init_grid = lambda dim: [[0 for _ in range(dim)] for _ in range(dim)]

sqs = [i * i for i in range(1, 9)]

# determine sum of <min_sizes> lowest squares

mand = sum(i * i for i in range(1, min_sizes + 1))

max_diff_sizes = 0

sols = []

# process sizes of the large square (at least 5x5)

for sq in sqs[::-1][:-4]:

N = int(sq**.5) # width and height of the large square

sqs_ = [x for x in sqs if x < sq]

max_pieces = sq - mand

lst = []

# determine all combinations of smaller squares that sum to square <sq>

for np in range(max_pieces - (max_pieces % 2 == 0), 3, -2):

for p, cnts in decompose(sq, np, sqs_, min_sizes):

lst.append((p, cnts))

# start with the combinations with the most smaller squares

for p, cnts in sorted(lst, key = lambda x: len(x[1]), reverse=1):

if (ln := len(cnts)) < min_sizes: break

# ignore combinations with not enough different sizes

if ln >= max_diff_sizes:

pieces = [int(x**.5) for x in p[::-1]]

# find a grid so that all pieces fit into the grid

if (sol := first_valid_grid(pieces, init_grid(N), N, len(pieces))):

if ln > max_diff_sizes:

max_diff_sizes, min_sizes = ln, ln

mand = sum(x * x for x in range(1, min_sizes + 1))

max_pieces = sq - mand

sols = []

# store solution

sols.append((sol, pieces))

if len(sols) < 2:

print("no multiple dissections have been found")

else:

# print the solution with the the smallest number of smaller squares

for sol, pieces in sorted(sols, key = lambda x: len(x[1])):

print("answer:", len(pieces), "squares\n")

print("pieces:", *[(x, x) for x in pieces], "\n")

print_grid(sol)

break

John Z permalink


from itertools import product

# assume big square = 8 x 8

# recursive square placing function
def placesq(grid, sqs, ltrs = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'): 
  if sum(sqs) == 0:
    yield grid
  else:
    
    # find largest remaining square to place
    for k, s in enumerate(sqs[::-1]):
      if s != 0:
        break
    # attempt to place square in grid

    # find empty hole
    for i in range(8):
      for j in range(8):
        if grid[i][j] == '1' and i - k <= 1 and j - k <= 1:
          if all(grid[m][n] == '1' for m in range(i, i + (7 - k))
                 for n in range(j, j + (7 - k))):
            # fill hole with letters    
            for m in range(i, i + (7 - k)):
              for n in range(j, j + (7 - k)):
                grid[m][n] = ltrs[0] # place square in grid

            sqs[5 - k] -= 1 # remove one square
  
            yield from placesq(grid, sqs, ltrs[1:])

            # restore grid to previous values
            for m in range(i, i + (7 - k)):
              for n in range(j, j + (7 - k)):
                grid[m][n] = '1' 
            sqs[5 - k] += 1 # restore square


#---------------------- Main program -------------------
d = [] #list of potential solutions

# number of squares of each dimension: 2, 3, 4, 5, 6, 7
for b in product(*(range(64 // n ** 2 + 1) for n in range(2, 8))):
  
  c = sum(i ** 2 * b1 for i, b1 in enumerate(b, 2)) # total area except 1" sqs
  
  bp = [b1 for b1 in b if b1]  + [64 - c] # remove zeroes; add 1" squares
  
  if len(set(bp)) == len(bp): # different number of squares of each size
    e = sum(x for x in bp) # get total number of squares
    if (e & 1) and (c < 64): # total number of squares is odd 
      d += [(sum(x > 0 for x in b) + 1, c, b)] # add potential solution to list
   

d = sorted(d, reverse = True) # sort on number of square sizes

for d1 in d:
  if d1[0] == d[0][0]: # only consider poss sols with max # of square sizes 
    # place different squares in 8 X 8 grid
    for ng in placesq([['1' for i in range(8)] for j in range(8)], list(d1[2])):
      print(64 - d1[1], d1)
      for gn in ng:
        
        print(' '.join(gn))
      print('_____________________________________________________')
      break # print only one grid placement

from itertools import product

# assume big square = 8 x 8

# recursive square placing function

def placesq(grid, sqs, ltrs = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'):

if sum(sqs) == 0:

yield grid

else:

# find largest remaining square to place

for k, s in enumerate(sqs[::-1]):

if s != 0:

break

# attempt to place square in grid

# find empty hole

for i in range(8):

for j in range(8):

if grid[i][j] == '1' and i - k <= 1 and j - k <= 1:

if all(grid[m][n] == '1' for m in range(i, i + (7 - k))

for n in range(j, j + (7 - k))):

# fill hole with letters

for m in range(i, i + (7 - k)):

for n in range(j, j + (7 - k)):

grid[m][n] = ltrs[0] # place square in grid

sqs[5 - k] -= 1 # remove one square

yield from placesq(grid, sqs, ltrs[1:])

# restore grid to previous values

for m in range(i, i + (7 - k)):

for n in range(j, j + (7 - k)):

grid[m][n] = '1'

sqs[5 - k] += 1 # restore square

#---------------------- Main program -------------------

d = [] #list of potential solutions

# number of squares of each dimension: 2, 3, 4, 5, 6, 7

for b in product(*(range(64 // n ** 2 + 1) for n in range(2, 8))):

c = sum(i ** 2 * b1 for i, b1 in enumerate(b, 2)) # total area except 1" sqs

bp = [b1 for b1 in b if b1] + [64 - c] # remove zeroes; add 1" squares

if len(set(bp)) == len(bp): # different number of squares of each size

e = sum(x for x in bp) # get total number of squares

if (e & 1) and (c < 64): # total number of squares is odd

d += [(sum(x > 0 for x in b) + 1, c, b)] # add potential solution to list

d = sorted(d, reverse = True) # sort on number of square sizes

for d1 in d:

if d1[0] == d[0][0]: # only consider poss sols with max # of square sizes

# place different squares in 8 X 8 grid

for ng in placesq([['1' for i in range(8)] for j in range(8)], list(d1[2])):

print(64 - d1[1], d1)

for gn in ng:

print(' '.join(gn))

print('_____________________________________________________')

break # print only one grid placement

John Z permalink

Reading Brian’s comment “In short, if an attempt to fit a rectangle at a particular point fails, we can then skip the checking of all its duplicates since they will also fail. This results in an impressive speed improvement.” I realized I could do the same by adding two lines of code at line 38:

Python

if sqs[5 - k] > 1: return

1
2
3
4

if sqs[5 - k] > 1:
return

The output looks OK but I’m in a slight rush as traveling tomorrow so haven’t been able to thoroughly verify.

Reply
- John Z permalink
  
  I don’t understand how these two lines get the desired speedup; just that they do. Any ideas Brian or Frits?
  
  Reply
  - BRG permalink
    
    Hi John,
    
    Without this addition, your loop will fit the current sized square
    in all positions in the grid where it fits before moving to the next
    recursion level. When we proceed to this next level, it there
    are still more of this sized square, it will again be fitted in all
    remaining positions, and so on until all of this size of squares
    have been fitted.
    
    But, while all the squares have been fitted in different recursion
    levels, the end result will be the same! In effect we have fitted
    all permutations of these squares when we only needed to fit
    them once.
    
    The fix avoids this by only fitting a duplicated square in the first
    grid position found in each recursion level.
    
    My earlier explanation was incomplete in not covering this.
    
    Reply

Frits permalink

See my description just before this check.


from itertools import product
from sys import argv

# assume big square = M x M
M = 8 if len(argv) != 2 else int(argv[1]) 
M2 = M * M
 
# recursive square placing function
def placesq(grid, sqs, ltrs = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'): 
  if sum(sqs) == 0:
    yield grid
  else:
    
    # find largest remaining square to place
    for k, s in enumerate(sqs[::-1]):
      if s != 0:
        break
    # attempt to place square in grid
  
    # find empty hole
    for i in range(k + 2):      #  i - k <= 1
      for j in range(k + 2):    #  j - k <= 1
        if grid[i][j] == '1':
          rng = [(m, n) for m in range(i, i + (M - k - 1))
                        for n in range(j, j + (M - k - 1))]
          if all(grid[m][n] == '1' for m, n in rng):
            # fill hole with letters    
            for m, n in rng:
              grid[m][n] = ltrs[0] # place square in grid
 
            sqs[M - k - 3] -= 1 # remove one square
  
            yield from placesq(grid, sqs, ltrs[1:])
 
            # restore grid to previous values
            for m, n in rng:
              grid[m][n] = '1' 
                
            sqs[M - k - 3] += 1 # restore square
            
            # we now have fully processed this number M - k - 3 (processing
            # all empty holes for the 2nd M - k - 3 entry) so we don't need
            # to check other empty holes anymore for this number M - k - 3
            if sqs[M - k - 3] > 1:
              return
 
 
#---------------------- Main program -------------------
d = [] #list of potential solutions
 
# number of squares of each dimension: 2, 3, 4, ..., M - 1
for b in product(*(range(M2 // n ** 2 + 1) for n in range(2, M))):
  
  c = sum(i ** 2 * b1 for i, b1 in enumerate(b, 2)) # total area except 1" sqs
  if c >= M2: continue
  
  bp = [b1 for b1 in b if b1]  + [M2 - c] # remove zeroes; add 1" squares
  
  if len(set(bp)) == len(bp): # different number of squares of each size
    if sum(x for x in bp) & 1:                 # total number of squares is odd 
      d += [(sum(x > 0 for x in b) + 1, c, b)] # add potential solution to list
   
 
d = sorted(d, reverse = True) # sort on number of square sizes

for d1 in d:
  if d1[0] == d[0][0]: # only consider poss sols with max # of square sizes 
    # place different squares in M X M grid
    for ng in placesq([['1' for i in range(M)] for j in range(M)], list(d1[2])):
      print(M2 - d1[1], d1)
      for gn in ng:
        
        print(' '.join(gn))
      print('_____________________________________________________')
      break # print only one grid placement

from itertools import product

from sys import argv

# assume big square = M x M

M = 8 if len(argv) != 2 else int(argv[1])

M2 = M * M

# recursive square placing function

def placesq(grid, sqs, ltrs = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'):

if sum(sqs) == 0:

yield grid

else:

# find largest remaining square to place

for k, s in enumerate(sqs[::-1]):

if s != 0:

break

# attempt to place square in grid

# find empty hole

for i in range(k + 2): # i - k <= 1

for j in range(k + 2): # j - k <= 1

if grid[i][j] == '1':

rng = [(m, n) for m in range(i, i + (M - k - 1))

for n in range(j, j + (M - k - 1))]

if all(grid[m][n] == '1' for m, n in rng):

# fill hole with letters

for m, n in rng:

grid[m][n] = ltrs[0] # place square in grid

sqs[M - k - 3] -= 1 # remove one square

yield from placesq(grid, sqs, ltrs[1:])

# restore grid to previous values

for m, n in rng:

grid[m][n] = '1'

sqs[M - k - 3] += 1 # restore square

# we now have fully processed this number M - k - 3 (processing

# all empty holes for the 2nd M - k - 3 entry) so we don't need

# to check other empty holes anymore for this number M - k - 3

if sqs[M - k - 3] > 1:

return

#---------------------- Main program -------------------

d = [] #list of potential solutions

# number of squares of each dimension: 2, 3, 4, ..., M - 1

for b in product(*(range(M2 // n ** 2 + 1) for n in range(2, M))):

c = sum(i ** 2 * b1 for i, b1 in enumerate(b, 2)) # total area except 1" sqs

if c >= M2: continue

bp = [b1 for b1 in b if b1] + [M2 - c] # remove zeroes; add 1" squares

if len(set(bp)) == len(bp): # different number of squares of each size

if sum(x for x in bp) & 1: # total number of squares is odd

d += [(sum(x > 0 for x in b) + 1, c, b)] # add potential solution to list

d = sorted(d, reverse = True) # sort on number of square sizes

for d1 in d:

if d1[0] == d[0][0]: # only consider poss sols with max # of square sizes

# place different squares in M X M grid

for ng in placesq([['1' for i in range(M)] for j in range(M)], list(d1[2])):

print(M2 - d1[1], d1)

for gn in ng:

print(' '.join(gn))

print('_____________________________________________________')

break # print only one grid placement

Frits permalink

When trying different larger squares than 8×8 I noticed my program was getting very slow. The recursion I used isn’t efficient if the list contains many pieces of the same size.

With the new recursion (similar to Brian’s and Jim’s set up) the internal run time now is 4ms.


from itertools import product

# "these were of several different sizes" 
min_sizes = 3

# decompose <t> into <k> numbers from <ns> so that sum(<k> numbers) equals <t>
def decompose(t, k=1, ns=[], mn=min_sizes, s=[]):
  if k == 1:
    if t in ns and t >= s[-1]:
      s_ = s + [t]
      cnts = [s_.count(x) for x in set(s_)]
      # there was a different number of squares of each size
      if len(cnts) >= mn and len(cnts) == len(set(cnts)):
        yield (s_, cnts)
  else:
    for n in ns:
      if k * n > t: break
      if s and n < s[-1]: continue   # sequence is non-decreasing
      yield from decompose(t - n,  k - 1, ns, mn, s + [n])
    
init_grid = lambda dim: [[0 for _ in range(dim)] for _ in range(dim)]    

def print_grid(g):
  dim = len(g[0])
  for i, r in enumerate(g):
    if i < dim:
      print(*[f'{x:>2}' for x in r], 
            "" if i != dim // 2 else "        0 for 1x1 squares")
  print()    

# look for an empty cell starting from row <r>  
def next_empty(g, dim, r=0):
  for i in range(r, dim):
    for j in range(dim):
      if not g[i][j]:
        return [i, j]

# fit <k> squares into empty spots in the dim x dim grid    
def pack_squares(pieces, k, g, dim, previ=0):
  if not pieces: 
    yield g                             # the grid is full
  else:
    # look for the next empty cell in the grid starting from row <previ>  
    if not (ij := next_empty(g, dim, previ)):  return
    (i, j), previ = ij, ij[0]
   
    # try each remaining piece in this position
    for p in sorted(set(pieces), reverse=True):
      # check that the piece lies within the square
      if not (i + p <= dim and j + p <= dim): continue
      
      # skip squares (except 1x1) that are one from the edge as the gap must be
      # filled with 1's so we have 2 versions if we move the block to the edge
      if p > 1 and {i, j}.intersection({1, dim - p - 1}): continue
    
      # all coordinates that the piece occupies
      rng = [(x, y) for x in range(i, i + p) for y in range(j, j + p)]
      
      # check that there is space for the piece
      if not all(g[x][y] == 0 for x, y in rng): continue
      
      for x, y in rng: g[x][y] = k      # add the piece
 
      pieces_ = pieces.copy()
      pieces_.remove(p)                 # remove first occurence of this piece
      # and continue to add more if possible
      yield from pack_squares(pieces_, k - 1, g, dim, previ)
      
      for x, y in rng: g[x][y] = 0      # backtrack

# return first grid that fits
def first_valid_grid(ps, g, dim, np):
  for sol in pack_squares(ps, np, g, dim):
    return sol

M = 8

sqs = [i * i for i in range(1, M + 1)]

# determine sum of <min_sizes> lowest squares
mand = sum(i * i for i in range(1, min_sizes + 1))

sols = []
# process sizes of the large square (at least 5x5)
for sq in sqs[::-1][:4 - M]:
  N = int(sq**.5)            # width and height of the large square
  sqs_ = [x for x in sqs if x < sq]
  max_pieces = sq - mand

  lst = []
  # determine all combinations of smaller squares that sum to square <sq>
  for np in range(max_pieces - (max_pieces % 2 == 0), 3, -2):
    for p, cnts in decompose(sq, np, sqs_, min_sizes):
      lst.append((p, cnts))
  
  # start with the combinations with the most smaller squares
  for p, cnts in sorted(lst, key = lambda x: len(x[1]), reverse=1):
    if (ln := len(cnts)) < min_sizes: break

    # ignore combinations with not enough different sizes
    if ln >= min_sizes:
      pieces = [int(x**.5) for x in p[::-1]]
      # find a grid so that all pieces fit into the grid
      if (sol := first_valid_grid(pieces, init_grid(N), N, len(pieces))):
        if ln > min_sizes:
          min_sizes = ln
          mand = sum(x * x for x in range(1, min_sizes + 1))
          max_pieces = sq - mand
          sols = []
        # store solution
        sols.append((sol, pieces))
     
if len(sols) < 2:
  print("no multiple dissections have been found")
else: 
  # print the solution with the the smallest number of smaller squares
  for sol, pieces in sorted(sols, key = lambda x: len(x[1])):
    print("answer:", len(pieces), "squares\n")
    print("pieces:", *[(x, x) for x in pieces], "\n")
    print_grid(sol)
    break

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

from itertools import product

# "these were of several different sizes"

min_sizes = 3

# decompose <t> into <k> numbers from <ns> so that sum(<k> numbers) equals <t>

def decompose(t, k=1, ns=[], mn=min_sizes, s=[]):

if k == 1:

if t in ns and t >= s[-1]:

s_ = s + [t]

cnts = [s_.count(x) for x in set(s_)]

# there was a different number of squares of each size

if len(cnts) >= mn and len(cnts) == len(set(cnts)):

yield (s_, cnts)

else:

for n in ns:

if k * n > t: break

if s and n < s[-1]: continue # sequence is non-decreasing

yield from decompose(t - n, k - 1, ns, mn, s + [n])

init_grid = lambda dim: [[0 for _ in range(dim)] for _ in range(dim)]

def print_grid(g):

dim = len(g[0])

for i, r in enumerate(g):

if i < dim:

print(*[f'{x:>2}' for x in r],

"" if i != dim // 2 else " 0 for 1x1 squares")

print()

# look for an empty cell starting from row <r>

def next_empty(g, dim, r=0):

for i in range(r, dim):

for j in range(dim):

if not g[i][j]:

return [i, j]

# fit <k> squares into empty spots in the dim x dim grid

def pack_squares(pieces, k, g, dim, previ=0):

if not pieces:

yield g # the grid is full

else:

# look for the next empty cell in the grid starting from row <previ>

if not (ij := next_empty(g, dim, previ)): return

(i, j), previ = ij, ij[0]

# try each remaining piece in this position

for p in sorted(set(pieces), reverse=True):

# check that the piece lies within the square

if not (i + p <= dim and j + p <= dim): continue

# skip squares (except 1x1) that are one from the edge as the gap must be

# filled with 1's so we have 2 versions if we move the block to the edge

if p > 1 and {i, j}.intersection({1, dim - p - 1}): continue

# all coordinates that the piece occupies

rng = [(x, y) for x in range(i, i + p) for y in range(j, j + p)]

# check that there is space for the piece

if not all(g[x][y] == 0 for x, y in rng): continue

for x, y in rng: g[x][y] = k # add the piece

pieces_ = pieces.copy()

pieces_.remove(p) # remove first occurence of this piece

# and continue to add more if possible

yield from pack_squares(pieces_, k - 1, g, dim, previ)

for x, y in rng: g[x][y] = 0 # backtrack

# return first grid that fits

def first_valid_grid(ps, g, dim, np):

for sol in pack_squares(ps, np, g, dim):

return sol

M = 8

sqs = [i * i for i in range(1, M + 1)]

# determine sum of <min_sizes> lowest squares

mand = sum(i * i for i in range(1, min_sizes + 1))

sols = []

# process sizes of the large square (at least 5x5)

for sq in sqs[::-1][:4 - M]:

N = int(sq**.5) # width and height of the large square

sqs_ = [x for x in sqs if x < sq]

max_pieces = sq - mand

lst = []

# determine all combinations of smaller squares that sum to square <sq>

for np in range(max_pieces - (max_pieces % 2 == 0), 3, -2):

for p, cnts in decompose(sq, np, sqs_, min_sizes):

lst.append((p, cnts))

# start with the combinations with the most smaller squares

for p, cnts in sorted(lst, key = lambda x: len(x[1]), reverse=1):

if (ln := len(cnts)) < min_sizes: break

# ignore combinations with not enough different sizes

if ln >= min_sizes:

pieces = [int(x**.5) for x in p[::-1]]

# find a grid so that all pieces fit into the grid

if (sol := first_valid_grid(pieces, init_grid(N), N, len(pieces))):

if ln > min_sizes:

min_sizes = ln

mand = sum(x * x for x in range(1, min_sizes + 1))

max_pieces = sq - mand

sols = []

# store solution

sols.append((sol, pieces))

if len(sols) < 2:

print("no multiple dissections have been found")

else:

# print the solution with the the smallest number of smaller squares

for sol, pieces in sorted(sols, key = lambda x: len(x[1])):

print("answer:", len(pieces), "squares\n")

print("pieces:", *[(x, x) for x in pieces], "\n")

print_grid(sol)

break

John Z permalink

Here is a more elegant solution to the speed problem. Instead of starting the search from (0, 0) at each recursion, we start from where the search ended in the previous level if the square size of the current level and the previous level are the same. If they are different the search starts from (0, 0).
There are also some changes to avoid having to restore the modified grid by copying it and modifying the copy and by transmitting a new recomposed tuple of square sizes.


from itertools import product
# assume big square = 8 x 8

# recursive square placing function
# 
def placesq(grid, sqs, ps = 0, sp = 0, ltrs = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'): 
  if sum(sqs) == 0:
    yield grid
  else:
    
    # find largest remaining square to place
    for k, s in enumerate(sqs[::-1]):
      if s != 0:
        break
    # attempt to place square in grid

    # find empty hole starting from 0 if current != previous square size
    # otherwise start from where previous search ended <sp>
    for ij in range(0 if ps != k else sp, 64):
      i, j = divmod(ij, 8)
      if grid[i][j] == '1' and i - k <= 1 and j - k <= 1:
        if all(grid[m][n] == '1' for m in range(i, i + (7 - k))
               for n in range(j, j + (7 - k))):

          cgrid = [z.copy() for z in grid] # make copy of grid to modify
          # fill hole in copy of grid with letters    
          for m in range(i, i + (7 - k)):
            for n in range(j, j + (7 - k)):
              cgrid[m][n] = ltrs[0] # place square in grid

          yield from placesq(cgrid, sqs[:5 - k] + (sqs[5 - k]  - 1,) +
                             sqs[6 - k:],k, ij, ltrs[1:])


#---------------------- Main program -------------------
d = [] #list of potential solutions

# number of squares of each dimension: 2, 3, 4, 5, 6, 7
for b in product(*(range(64 // n ** 2 + 1) for n in range(2, 8))):
  
  c = sum(i ** 2 * b1 for i, b1 in enumerate(b, 2)) # total area except 1" sqs
  
  bp = [b1 for b1 in b if b1]  + [64 - c] # remove zeroes; add 1" squares
  
  if len(set(bp)) == len(bp): # different number of squares of each size
    e = sum(x for x in bp) # get total number of squares
    if (e & 1) and (c < 64): # total number of squares is odd 
      d += [(sum(x > 0 for x in b) + 1, c, b)] # add potential solution to list
   

d = sorted(d, reverse = True) # sort on number of square sizes

for d1 in d:
  if d1[0] == d[0][0]: # only consider poss sols with max # of square sizes 
    # place different squares in 8 X 8 grid
    for ng in placesq([['1' for i in range(8)] for j in range(8)], d1[2]):
      print(64 - d1[1], d1)
      for gn in ng:
        
        print(' '.join(gn))
      print('_____________________________________________________')
      break # print only one grid placement

from itertools import product

# assume big square = 8 x 8

# recursive square placing function

def placesq(grid, sqs, ps = 0, sp = 0, ltrs = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'):

if sum(sqs) == 0:

yield grid

else:

# find largest remaining square to place

for k, s in enumerate(sqs[::-1]):

if s != 0:

break

# attempt to place square in grid

# find empty hole starting from 0 if current != previous square size

# otherwise start from where previous search ended <sp>

for ij in range(0 if ps != k else sp, 64):

i, j = divmod(ij, 8)

if grid[i][j] == '1' and i - k <= 1 and j - k <= 1:

if all(grid[m][n] == '1' for m in range(i, i + (7 - k))

for n in range(j, j + (7 - k))):

cgrid = [z.copy() for z in grid] # make copy of grid to modify

# fill hole in copy of grid with letters

for m in range(i, i + (7 - k)):

for n in range(j, j + (7 - k)):

cgrid[m][n] = ltrs[0] # place square in grid

yield from placesq(cgrid, sqs[:5 - k] + (sqs[5 - k] - 1,) +

sqs[6 - k:],k, ij, ltrs[1:])

#---------------------- Main program -------------------

d = [] #list of potential solutions

# number of squares of each dimension: 2, 3, 4, 5, 6, 7

for b in product(*(range(64 // n ** 2 + 1) for n in range(2, 8))):

c = sum(i ** 2 * b1 for i, b1 in enumerate(b, 2)) # total area except 1" sqs

bp = [b1 for b1 in b if b1] + [64 - c] # remove zeroes; add 1" squares

if len(set(bp)) == len(bp): # different number of squares of each size

e = sum(x for x in bp) # get total number of squares

if (e & 1) and (c < 64): # total number of squares is odd

d += [(sum(x > 0 for x in b) + 1, c, b)] # add potential solution to list

d = sorted(d, reverse = True) # sort on number of square sizes

for d1 in d:

if d1[0] == d[0][0]: # only consider poss sols with max # of square sizes

# place different squares in 8 X 8 grid

for ng in placesq([['1' for i in range(8)] for j in range(8)], d1[2]):

print(64 - d1[1], d1)

for gn in ng:

print(' '.join(gn))

print('_____________________________________________________')

break # print only one grid placement

Sunday Times Teaser 3214 – Squaring the Square

by Peter Good

Published Friday April 26 2024 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta