Teaser 3214: Squaring the square
From The Sunday Times, 28th April 2024 [link] [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?
[teaser3214]
Frits and 
GeoffR, 
Lise Andreasen, 
S2T2 
Jim Randell 5:55 pm on 26 April 2024 Permalink |
The largest (integral sized) square that can cut from a sheet of A4 is 8 inches × 8 inches. And in order to get multiple different sizes of smaller square we need at least a 3 × 3 square.
I am assuming that when the puzzle refers to “more than one way that the dissection can be made”, it means there are multiple different possible sets of smaller squares. (Not the same set just assembled in a different way to form the larger square).
By using the [[
express()]] function from the enigma.py library to find candidate dissections, and the rectpack.py library to fit the smaller squares into the larger square, I was able to quickly write a program that runs in a reasonable time.However, the rectpack.py library wasn’t designed to handle multiple rectangles of the same shape, and was not as efficient as it could be in this case. So I have updated it to cope better with this situation, and the program now runs even faster.
The following Python program runs in 95ms. (Internal runtime is 28ms).
from enigma import (Accumulator, irange, express, multiset, seq_all_different, group, item, printf) import rectpack # can we pack the squares? def pack(n, ms): rs = list((x, x) for x in ms.elements()) for ps in rectpack.pack(n, n, rs): return ps # a single packing will do # find the largest number of different sizes of smaller square [at least 3] acc = Accumulator(fn=max, value=3, collect=1) # consider the size of the larger square for n in irange(8, 3, step=-1): # consider the areas of smaller squares ss = list(irange(1, n - 1)) # decompose n^2 into smaller squares for qs in express(n * n, (i * i for i in ss)): # there was an odd number of smaller squares if sum(qs) % 2 != 1: continue # and there were "several" sizes k = len(qs) - qs.count(0) if k < acc.value: continue ms = multiset.from_pairs(zip(ss, qs)) # and a different number of each size if not seq_all_different(ms.values()): continue # attempt to pack the squares ps = pack(n, ms) if ps: # record (<size of large square>, <number of smaller squares>, <packing>) acc.accumulate_data(k, (n, ms.size(), ps)) if acc.data: printf("{acc.value} different sizes of smaller squares") # consider possible sizes of larger square g = group(acc.data, by=item(0)) for (k, vs) in g.items(): # we need multiple ways to dissect the square if len(vs) < 2: continue printf("{k} x {k} square -> {n} dissections", n=len(vs)) # find the minimal number of smaller squares sm = min(s for (n, s, ps) in vs) printf("min {sm} smaller squares") for (n, s, ps) in vs: if s == sm: rectpack.output_grid(n, n, ps, end="--")Solution: There were 13 smaller squares.
The maximum number of different sizes of smaller squares is 4. It is possible to dissect 5×5, 6×6, 7×7, 8×8 using 3 different sizes of smaller squares, but only 8×8 can be dissected into 4 different sizes. So this must be the size of square chosen by Clark.
An 8×8 square can be dissected into 5 different sets of smaller squares of 4 different sizes, and the smallest of these uses 13 smaller squares.
A minimal dissection is shown below:
Had the puzzle allowed Clark to start with a 9×9 square this can also be dissected into 4 different sizes of smaller squares (but not 5), and so this would give a further answer to the puzzle:
A 9×9 square can be dissected into 23 different sets of smaller squares of 4 different size, and the smallest of these uses 15 smaller squares.
The program can be used to investigate extensions to the puzzle for squares up to 12 × 12, after which it gets a bit bogged down.
LikeLike
Frits 5:40 pm on 27 April 2024 Permalink |
Using SubstitutedExpression to fit pieces into a grid.
The programs runs in 1.25 seconds (8 or 9 times longer than my similar Python-only program on Brian’s site).
from enigma import SubstitutedExpression symbols = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" symbols += "ÀÁÂÃÄÅÆÇÈÉÊËÌÍÎÏÐÑÒÓÔÕÖØÙÚÛÜÝÞßàáâãäåæçèéêëìíîïð" # "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]) 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 entries with too few different sizes if (ln := len(cnts)) >= max_diff_sizes: pieces = [int(x**.5) for x in p[::-1]] topleft = [symbols[2 * i:2 * i + 2] for i in range(np)] sizes = [symbols[2 * np + i] for i in range(np)] s2d = dict(zip(sizes, pieces)) answer = ', '.join(str('(({' + x[0] + '}, {' + x[1] + '}), \ {' + sizes[i] + '})') \ for i, x in enumerate(topleft) if s2d[sizes[i]] > 1) answer = f"{answer}" # invalid digit / symbol assignments d2i = {i: set() for i in range(len(pieces))} for i, p in enumerate(pieces): # make sure we don't cross the boundaries for d in range(X - p + 1, 10): vs = set() vs.update(topleft[i][0]) vs.update(topleft[i][1]) d2i[d] |= vs placed = [(topleft[0], sizes[0])] # build expressions exprs = [] for i in range(1, np): piece = symbols[2 * i:2 * i + 2] sz = sizes[i] if s2d[sz] == 1: break # pieces of dimensions 1 always fit for tl, s in placed: # squares may not overlap exprs.append(f"({{{tl[0]}}} + {{{s}}} <= {{{piece[0]}}} or " f"{{{piece[0]}}} <= {{{tl[0]}}} - {{{sz}}}) or " f"({{{tl[1]}}} + {{{s}}} <= {{{piece[1]}}} or " f"{{{piece[1]}}} <= {{{tl[1]}}} - {{{sz}}})") placed.append((piece, sz)) #for e in exprs: print(e); #print() # the alphametic puzzle p = SubstitutedExpression( exprs, base=X, answer=answer, d2i=d2i, s2d=s2d, distinct="", verbose=0, # use 256 to see the generated code ) # print answers for ans in p.answers(): if ln > max_diff_sizes: sols = [] # store data, count of smallest piece first sols.append((pieces.count(min(pieces)), np, pieces)) break # we need only one solution 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, m, pieces in sorted(sols): print("answer:", m, "\n") print("pieces:", *[(x, x) for x in pieces], "\n") breakLikeLike
Jim Randell 10:45 am on 3 May 2024 Permalink |
@Frits: An inventive use of the [[
SubstitutedExpression]] solver.But I think the puzzle is asking for a dissection that uses the minimum number of pieces in total, rather than a dissection that has the minimum number of smallest pieces. (Although it turns out these are the same for the given constraints).
LikeLike
Frits 8:24 pm on 3 May 2024 Permalink |
Yes, I got confused with the phrase “smallest number of smaller squares”.
I also have a Python only version that first performs the express calls for all “n” using the Boecker-Liptak Money Changing [https://enigmaticcode.wordpress.com/2020/09/21/enigma-946-patterns-of-fruit/#comment-9773] and then reorders this list on the number of different pieces and number of pieces before packing.
The A1 format (n=23) can be done in 165 seconds:
There are combinations of pieces that are hard to for the pack routine.
LikeLike