Enigmatic Code

Programming Enigma Puzzles

Enigma 544a: Merry Christmas

From New Scientist #1696, 23rd December 1989 [link]

Arranging and displaying the Christmas cards is always a problem. This year all our cards are either 10cm × 20cm or 20cm × 10cm. We managed to arrange them together like a jigsaw, just covering (without overlapping) a square piece of paper.

Then we found that there was no convenient place to display the square so we decided to cut it either horizontally or vertically into two rectangles. But no matter how we tried it was impossible to do this without cutting through at least one of the cards. So we cut the square into two rectangles in such a way that we had to cut through the minimum number of cards, but it still meant that we cut over five per cent of our cards.

How many cards did we receive this year, and how many did we cut?

Enigma 192 was also called “Merry Christmas”.

[enigma544a] [enigma544]

One response to “Enigma 544a: Merry Christmas

  1. Jim Randell 6 April 2020 at 8:37 am

    (See also: Enigma 1653).

    The setter has managed to find a “fault-free” tiling of his square.

    We know (see my notes on Enigma 1653) that the following conditions must hold for an n × n square:

    1. n² is divisible by 2 (i.e. n is even)
    2. n ≥ 5.
    3. n ≠ 6.

    So n is an even number greater than 6. (i.e. n = 8, 10, 12, …).

    For an 8×8 grid we would need to cut (at least) 2 tiles. For a 10×10 grid, (at least) 3 tiles, etc.

    Can we create a fault free tiling for an 8×8 grid, that requires us to cut (at least) 2 tiles?

    An 8×8 grid has 64 squares, each tile covers 2 squares so there are 32 tiles in all.

    There are 7 horizontal fault lines, and 7 vertical fault lines, making 14 fault lines in all.

    Each fault line must be bridged by the centre of 2 tiles, so 28 tiles are used to ensure that all fault lines are all bridged twice, and this leave 4 tiles to place (each of which will bridge some fault line).

    Can we create a fault free tiling for an 8×8 grid, that requires us to cut (at least) 3 tiles?

    Each fault line would have to be bridged by the centre of 3 tiles, so this would require 42 tiles, but there are only 32 tiles available.

    And is it possible to create a fault free tiling for 10×10 grid that requires us to cut (at least) 3 tiles?

    A 10×10 grid has 100 squares, and so requires 50 tiles.

    There are 9 + 9 = 18 fault lines.

    To place 3 tiles across each fault line would require 18×3 = 54 tiles, and there are only 50 tiles available.

    So this is impossible, as are any larger grids. The only possible solution is with an 8×8 grid, and a minimum of 2 tiles cut.

    Solution: 32 cards were received. 2 of the cards were cut.

    This numbers argument tells us that if there is a solution to the puzzle, it must be using an 8×8 grid, and the minimum number of tiles cut by a fault line is 2.

    But is it possible to construct such a grid?

    The following Python 3 program runs in 107ms.

    Run: [ @repl.it ]

    from enigma import irange, join, printf
    
    # update grid <g>, place value <n> at positions <xys>
    def update(g, n, *xys):
      g = list(list(r) for r in g)
      for (x, y) in xys:
        g[x][y] = n
      return g
    
    # remove value <v> from <s>
    def remove(s, v):
      s.remove(v)
      return s
    
    # complete grid <g> using empty squares <ss>, using label <n>
    def fit(g, ss, n):
      if not ss:
        yield g
      else:
        (x, y) = ss[0]
        if x < 7 and g[x + 1][y] == 0:
          # try to fit a tile horizontally
          yield from fit(update(g, n, (x, y), (x + 1, y)), remove(ss[1:], (x + 1, y)), n + 1)
        if y < 7 and g[x][y + 1] == 0:
          # try to fit a tile vertically
          yield from fit(update(g, n, (x, y), (x, y + 1)), remove(ss[1:], (x, y + 1)), n + 1)
    
    # bridge the faults in <fs> in grid <g>, using label <n>
    def faults(g, fs, n):
      if not fs:
        ss = list((x, y) for x in irange(0, 7) for y in irange(0, 7) if g[x][y] == 0)
        yield from fit(g, ss, n)
      else:
        (d, k) = fs[0]
        if d == 'H':
          # bridge the horizontal fault
          for x in irange(0, 7):
            if g[x][k] == 0 and g[x][k + 1] == 0:
              yield from faults(update(g, n, (x, k), (x, k + 1)), fs[1:], n + 1)
        else:
          # bridge the vertical fault
          for y in irange(0, 7):
            if g[k][y] == 0 and g[k + 1][y] == 0:
              yield from faults(update(g, n, (k, y), (k + 1, y)), fs[1:], n + 1)
    
    # make the initial grid
    g = list([0] * 8 for _ in irange(1, 8))
    # and the list of faults (each appears twice)
    fs = list()
    for i in irange(0, 6): fs.extend((('H', i), ('V', i)) * 2)
    # complete the grid
    for g in faults(g, fs, 1):
      # output the solution
      for r in g:
        printf("[ {r} ]", r=join((str(x or 0).zfill(2) for x in r), sep=' '))
      printf()
      break # we only need one grid
    

    Here is an example 8×8 grid where each fault line is bridged by at least 2 tiles.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: