Enigmatic Code

Programming Enigma Puzzles

Enigma 1491: Tile trials

From New Scientist #2653, 26th April 2008

Dick has a box of rectangular tiles. Each is a different size, the dimensions being 1 × 3, 2 × 4, 3 × 5, 4 × 6 and so on.

He takes some tiles out of the box, first the 1 × 3, then the 2 × 4, then the 3 × 5, and so on, with the aim of fitting together all those that he has taken into a rectangle that has no gaps and no overlaps.

Assuming he takes more than one tile out of the box, how many tiles must he take out to create (a) the smallest possible rectangle, and (b) the next smallest possible rectangle?

[enigma1491]

Advertisements

One response to “Enigma 1491: Tile trials

  1. Jim Randell 18 November 2012 at 4:14 pm

    This is a slightly different approach from my original Perl program that I wrote when the puzzle came out [link]. It’s shorter and faster and runs (under PyPy) in 9.2s. If I’d started off using this approach I probably wouldn’t have bothered writing the C version.

    from itertools import product
    from enigma import sqrt, irange, printf
    
    # fit a tile into the grid
    # a, b = dimensions of grid
    # g = grid
    # ts = tiles
    def fit(a, b, g, ts):
      # are we done?
      if len(ts) == 0: return True    
    
      # find the first empty square
      for (x, y) in product(range(b), range(a)):
        if not g[y][x]: break
      for t in ts:
        # try it in both orientations
        for (tx, ty) in (t, t[::-1]):
          # does the tile fit in the grid?
          (mx, my) = (x + tx, y + ty)
          if mx > b or my > a: continue
          # is anything in the way of the tile?
          if any(g[i][j] for (i, j) in product(range(y, my), range(x, mx))): continue
          # place the tile
          for (i, j) in product(range(y, my), range(x, mx)): g[i][j] = t[0]
          # and try to place the remaining tiles
          if fit(a, b, g, list(s for s in ts if s != t)): return True
          # remove the tile
          for (i, j) in product(range(y, my), range(x, mx)): g[i][j] = 0
      # no tile fits in this gap
      return False
    
    # output the grid
    def output(g):
      label = '.123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
      for r in g:
        printf("[{r}]", r=''.join(label[x] for x in r))
    
    # n = number of tiles
    # t = total area of the tiles
    # ts = tiles
    # s = number of solutions
    (n, t, ts, s) = (1, 3, [(1, 3)], 0)
    
    # we want to find the first two solutions
    while s < 2:
      n += 1
      t += n * (n + 2)
      ts.insert(0, (n, n + 2))
    
      # try factors of t = a x b, not(a > b)
      # and not(a < n), else the largest tile can't fit
      for a in irange(n, int(sqrt(t) + 0.5)):
        (b, r) = divmod(t, a)
        if r > 0: continue
        printf("[n={n} t={t} = {a}x{b}]")
    
        # make an empty grid
        g = [[0] * b for i in range(a)]
        # and try to fit the tiles into it
        if fit(a, b, g, ts):
          printf("solution for {n} tiles, {a} x {b} grid")
          output(g)
          s += 1
    

    Solution: (a) 9 tiles; (b) 11 tiles.

    The solution for 9 tiles is a 15×25 grid (for example):

    And for 11 tiles it is a 22×29 grid (for example):

    If you stop the program from returning as soon as it has found a solution the program finds 336 possible tilings for the 15×25 grid and 64 possible tilings for the 22×29 grid (although this takes no account of symmetrical solutions, so you can divide these numbers by 4 to get the number of essentially different solutions – 84 for the 15×25 grid and 16 for the 22×29 grid).

    The next smallest two possible tilings are both with 14 tiles and are for a 25×49 grid and a 35×35 grid.

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: