Enigmatic Code

Programming Enigma Puzzles

Enigma 10: Squared near-squares

From New Scientist #1152, 26th April 1979 [link]

A “near-square” is a rectangle of n × (n+1) units, and the problem is to fill it completely with as few “squarelets” — that is, smaller integral-sided squares — as possible. For a 5 × 4 you cannot do better than 5 squarelets, as the figure shows.

With how few squarelets can you fill:

(a) an 18 × 19 near-square?

(b) a 22 × 23 near-square?

[enigma10]

Advertisements

4 responses to “Enigma 10: Squared near-squares

  1. jimrandell 10 December 2011 at 8:12 am

    The following Python program works by deconstructing the product of n x m in to as few squares as possible, then tries to fit those squares into an n x m grid.

    Runtime (using PyPy) is 1.3s for the 18 x 19 case and 56.9s for the 22 x 23 case.

    from itertools import count
    from enigma import printf
     
    # decompose n into l numbers in ns
    def decompose(n, l, ns):
      if l == 1:
        return [[n]] if n in ns else []
      ds = []
      for (i, m) in enumerate(ns):
        if m > n: continue
        for j in decompose(n - m, l - 1, ns[i:]):
          ds.append([m] + j)
      return ds
     
    def solve(n, m):
      assert not(m < n)
      # what squares can it be decomposed into?
      root = dict((i * i, i) for i in range(1, n + 1))
      squares = sorted(root.keys(), reverse=True)
      for l in count(1):
        ds = decompose(n * m, l, squares)
     
        # try to fit the squares into a grid
        for d in ds:
          printf("trying {d}...")
          if fit(n, m, [root[x] for x in d]):
            printf("{n} x {m} => {l} {d}")
            return l
     
    def fit(n, m, l):
      # fit the squares in l into an n x m grid
      g = [[0 for j in range(m)] for i in range(n)]
      return _fit(n, m, g, l, ord('a'), n * m, 0)
     
    # fit the squarelets in l into the n x m grid g (with e empty places), label with c
    def _fit(n, m, g, l, c, e, p):
      if len(l) == 0:
        output(n, m, g)
        return True
     
      s = l[0]
      # try to fit an s x s squarelet in
      for j in range(0, m - s + 1):
        for i in range(0, n - s + 1):
          if g[i][j] or i + j * n < p: continue
          if empty(g, i, j, s, s):
            # fill the square
            fill(g, i, j, s, s, c)
            # try to fit the rest of the squarelets in
            q = i + j * n + s if len(l) > 1 and l[1] == l[0] else 0
            if _fit(n, m, g, l[1:], c + 1, e - s * s, q): return True
            # remove the square
            fill(g, i, j, s, s, 0)
     
      return False
     
    def empty(g, i, j, a, b):
      # is the a x b rectangle at (i, j) empty
      for y in range(j, j + b):
        for x in range(i, i + a):
          if g[x][y]: return False
      return True
     
    def fill(g, i, j, a, b, c):
      for y in range(j, j + b):
        for x in range(i, i + a):
          g[x][y] = c
     
    def output(n, m, g):
      for i in range(n):
        print(''.join(map(chr, g[i])))
     
     
    p = (18, 19, 22, 23)
     
    import sys
    if len(sys.argv) > 1: p = list(map(int, sys.argv[1:]))
     
    for (n, m) in zip(p[::2], p[1::2]):
      solve(n, m)
    

    Solution: (a) An 18 x 19 near-square can be filled with 7 squarelets. (b) A 22 x 23 near-square can be filled with 8 squarelets.

    • Hugh Casement 26 August 2014 at 8:26 am

      I don’t have a Python compiler and am too stupid to work out a back-tracking (and/or recursive) method in Basic. Juggling the squares by hand always seems to need more of them — perhaps I’m too impatient as well. Can anyone provide solutions for those 7 and 8 squarelets respectively?

      • Jim Randell 27 August 2014 at 1:25 pm

        If you want to try Python it is freely available for many platforms (and installed by default on some). I would recommend it if you want to explore programming beyond BASIC. See http://www.python.org for details.

        Here are diagrams of the solutions my program finds for the 18×19 and 22×23 squares:

        Enigma 10 - Solution 18x19

        Enigma 10 - Solution 22x23

        The smallest “near square” that requires 9 squarelets is 19×20.

        • Hugh Casement 27 August 2014 at 5:04 pm

          That’s great: thanks a lot, Jim.

          Oh, and I do appreciate your insights, methods, references to sources, and other comments. It was a great weakness of the Enigmas (enigmata?) that usually all we got was a bald solution — often just a single numerical value — and were none the wiser as to how it was derived. My own sledgehammer or ‘British Museum’ approach was not usually very educational. Some puzzles were later explained on the NS web site, but only a small proportion of the total.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: