Enigmatic Code

Programming Enigma Puzzles

Enigma 1416: Filling in the squares

From New Scientist #2576, 4th November 2006

Enigma 1416Susan and Paul have a new game which is played on a 4×4 array of small squares.

Two dark lines though the centre of the array, one horizontal and one vertical, divide the array into four 2×2 “regions”. If you select a square in the array, then its “environment” is the seven squares which are in the same row, column or region as the selected square.

Susan begins a game by writing 1, 2, 3 or 4 in some of the squares in the array. Paul then takes over. If he can find an empty square whose environment contains three of the four numbers then he writes the fourth number in that empty square. Paul repeats this operation on the resulting array and he does that as many times as he can. If, when Paul has finished, they find that every square of the array is full then they say that Susan made a “wise” beginning.

On Monday they played a game for which Susan made a wise beginning. On Tuesday they decided she would begin by filling one fewer squares than on Monday. After exhaustive searching they found that, with that restriction, Susan was unable to make a wise beginning.

How many squares did Susan fill on Monday?

[enigma1416]

Advertisements

One response to “Enigma 1416: Filling in the squares

  1. Jim Randell 1 July 2013 at 10:55 am

    This Python program runs in 76ms.

    # we need to find the smallest number of starting squares
    # such that the puzzle cannot be completed.
    
    # it needs to be 3 or greater
    
    from itertools import combinations, count
    from enigma import irange, printf
    
    # numbers used to fill out the grid
    numbers = set(irange(1, 4))
    
    # indices of squares in the grid
    squares = set(irange(0, 15))
    
    # environment of each square
    environment = (
      (1, 2, 3, 4, 5, 8, 12), # 0
      (0, 2, 3, 4, 5, 9, 13), # 1
      (0, 1, 3, 6, 7, 10, 14), # 2
      (0, 1, 2, 6, 7, 11, 15), # 3
      (0, 1, 5, 6, 7, 8, 12), # 4
      (0, 1, 4, 6, 7, 9, 13), # 5
      (2, 3, 4, 5, 7, 10, 14), # 6
      (2, 3, 4, 5, 6, 11, 15), # 7
      (0, 4, 9, 10, 11, 12, 13), # 8
      (1, 5, 8, 10, 11, 12, 13), # 9
      (2, 6, 8, 9, 11, 14, 15), # 10
      (3, 7, 8, 9, 10, 14, 15), # 11
      (0, 4, 8, 9, 13, 14, 15), # 12
      (1, 5, 8, 9, 12, 14, 15), # 13
      (2, 6, 10, 11, 12, 13, 15), # 14
      (3, 7, 10, 11, 12, 13, 14), # 15
    )
    
    # solve a grid by filling out empty squares with one
    # number missing from their environment
    def solve(g):
      while (0 in g):
        # look at empty squares
        for i in squares:
          if g[i] != 0: continue
          # find the values not in the environment
          s = numbers.difference(g[j] for j in environment[i])
          if len(s) == 0: return False
          if len(s) == 1:
            g[i] = s.pop()
            break
        else:
          # no progress, exit the while loop
          break
      return (0 not in g)
    
    # decompose n into acceptable "colourings"
    # n - number of elements in decomposition
    # m - number of digits in decomposition
    # d - current digit
    # u - largest possible element count
    # mn - smallest possible element counts
    def decompose(n, m, d, u, mn):
      if m == 1:
        if not(n > u): yield [d] * n
      else:
        for n1 in irange(mn[0], min(u, n - sum(mn[1:]))):
          for ns in decompose(n - n1, m - 1, d + 1, n1, mn[1:]):
            yield [d] * n1 + ns
    
    # check grids filled out with n numbers
    def check(n):
      # for each 4-colouring
      for ds in decompose(n, 4, 1, n, [1, 1, 1, 0]):
        # choose n placements
        for ps in combinations(squares, n):
          # fill out the grid
          g = [0] * 16
          for (i, d) in zip(ps, ds):
            g[i] = d
          # try to find a solution
          if solve(g): return True
      # no solutions found
      return False
    
    # start checking from 3 (there must be 3 numbers in one environment
    # to get going) and look for n where grids with n numbers cannot be
    # completed, but some grid with n+1 numbers can be
    for n in count(3):
      if not check(n) and check(n + 1):
        printf("Monday: {n1} squares,  Tuesday: {n} squares", n1=n+1)
        break
    

    Solution: Susan filled in 4 squares on Monday.

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: