Enigmatic Code

Programming Enigma Puzzles

Enigma 1520: Just pondering

From New Scientist #2682, 15th November 2008 [link]

Around the edge of the rectangular fish pond in Joe’s back garden is a path two-paving-slabs wide. The square slabs are coloured light brown, grey or light green. Joe has arranged them so that the pattern of colours of any square of four slabs is unique, however viewed. If Joe had needed to make the path any longer, then colour patterns would have had to be repeated.

How many slabs make up the path?

[enigma1520]

Advertisements

4 responses to “Enigma 1520: Just pondering

  1. Jim Randell 5 September 2012 at 9:10 am

    This was a fun puzzle to solve programatically. The following Python code first determines the number of possible 2×2 slab combinations, and then searches for maximal possible constructive solutions. It outputs a solution for each possible pond size. It runs in 670ms.

    from itertools import product
    from enigma import irange, join, printf
    
    # the three colours
    colours = tuple('123')
    
    # possible rotations of a 2x2 square
    def rotations(s):
      (a, b, c, d) = s
      return (s, (d, a, b, c), (c, d, a, b), (b, c, d, a))
    
    # find possible 2x2 slabs with 3 colours, unique under rotation
    slabs = set()
    for s in product(colours, repeat=4):
      # rotations of this slab
      rs = rotations(s)
      # is this a rotation of a slab we've already seen?
      if slabs.intersection(rs): continue
      # no, so add it
      slabs.add(rs[0])
    
    N = len(slabs)
    printf("There are {N} different 2x2 slab combinations")
    
    
    # an exception to raise if the puzzle is solved
    class Solved(Exception): pass
    
    # a class to solve an n x m grid
    class Puzzle:
    
      def __init__(self, n, m):
        self.size = (n, m)
        # make the empty grid
        self.grid = list([' '] * m for _ in irange(1, n))
    
      # attempt to solve the grid
      def solve(self):
        # let's assume (0, 0) is colour 1, and (0, 1) is colour 1 or 2
        self.grid[0][0] = '1'
        # try to place a slab
        self.place(0, 1, set(), colours[:2])
    
      # place a slab at (x, y)
      def place(self, x, y, seen, colours=colours):
    
        # are we done?
        (n, m) = self.size
        if y == m: (x, y) = (x + 1, 0)
        if x == n: raise Solved
    
        # don't place slabs in the pond
        if x > 1 and x < n - 2 and y > 1 and y < m - 2:
          self.place(x, m - 2, seen)
          return
    
        # place a slab at (x, y)
        for c in colours:
          seen1 = seen
          g = self.grid
          g[x][y] = c
          # does it complete a 2x2 square?
          if y > 0 and (x == 1 or x == n - 1) or x > 0 and (y == 1 or y == m - 1):
            # what is the square?
            s = (g[x - 1][y - 1], g[x][y - 1], c, g[x - 1][y])
            # have we seen it?
            if seen.intersection(rotations(s)): continue
            seen1 = seen.union([s])
          # try the next square
          self.place(x, y + 1, seen1)
    
      # display the grid
      def display(self):
        for r in self.grid:
          printf("[{r}]", r=join(r))
        printf()
    
    
    # for an a x b pond there are 2(a + 2) + 2(b + 2) 2x2 slabs that can be made
    # so let's consider all possible ponds starting with the longest perimeter
    done = False
    print()
    for p in irange((N - 8) // 2, 2, step=-1):
      for a in irange(1, p // 2):
        b = p - a
        x = Puzzle(a + 4, b + 4)
        try:
          x.solve()
        except Solved:
          # we've found a solution, so display it
          c = 2 * (a + b + 4)
          printf("{a}x{b} pond, {t} slabs, {c} 2x2 combinations", t=2 * c)
          x.display()
          done = True
      if done: break # remove this line to find non-maximal solutions
    

    Solution: The path is made up of 48 slabs.

  2. Hugh Casement 21 January 2016 at 7:23 am

    I can see that there are twenty-four 2×2 patterns that are different even under rotation.  Also that, because each overlaps its neighbours, that means 48 slabs to fit round a rectangular pond whose dimensions sum to 8.  Does it work for all such ponds: 7×1, 6×2, 5×3, and 4×4?  Would it also work for a degenerate 8×0 pond (i.e. with no water but something like an edging strip along the middle to prevent patterns overlapping there)?

    What layouts does your program generate?  My own attempt ran overnight but by morning had found nothing: all those nested loops are very time-consuming.

    • Jim Randell 21 January 2016 at 11:35 am

      My program starts looking for arrangements that consist of all of the possible 24 patterns, and it finds the following arrangements that use 48 slabs (corresponding to 1×7, 2×6, 3×5 and 4×4 ponds):

      Enigma 1520 - Solutions

      (The program only outputs the first arrangement it finds for a particular shape of pond, but there will be many other possible arrangements).

      If you remove line 95 it will continue to examine smaller numbers of slabs, and it finds solutions without repeated patterns for 44 slabs (1×6, 2×5 and 3× 4 ponds), 40 slabs (1×5, 2×4 and 3×3 ponds), 36 slabs (1×4 and 2×3 ponds), 32 slabs (1×3 and 2×2 ponds), 28 slabs (1×2 pond) and 24 slabs (1×1 pond).

      By changing the loop at line 84 to start from 0 (instead of 1), you can examine ponds with a dimension of 0. Here’s a diagram of a 48 slab path around a 0×8 pond:

      Enigma 1520 - Solution 0x8

  3. Hugh Casement 21 January 2016 at 11:59 am

    That’s great, Jim.  I was just about to cut out some “slabs” and try arranging them.  You’ve saved me a lot of trouble!

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: