Enigmatic Code

Programming Enigma Puzzles

Enigma 1466: Crossed words

From New Scientist #2627, 27th October 2007

I have just made up a small crossword for our local newspaper. It is a square grid of traditional style with fewer than a quarter of the small squares shaded and the rest to be filled by “across” and “down” answers. The pattern of shaded squares has “180° symmetry”, i.e. if you rotate it through 180° about its central point, the layout looks the same.

The lengths of the answers, in the usual crossword order, are:

Across: 3 5 3 3 3 3 3 5 3
Down: 6 3 7 7 6 3

and two of the answers are CROSSED and WORDS.

(a) What is the size of the grid (e.g. 11 by 11)?
(b) What are the clue numbers for ‘CROSSED’ and ‘WORDS’ (e.g. 6 Down and 12 Across)?

[enigma1466]

Advertisements

2 responses to “Enigma 1466: Crossed words

  1. Jim Randell 4 February 2013 at 7:58 am

    The following Python program runs in 1.5s (under PyPy) and produces partially filled out grid.

    from itertools import combinations, product
    from enigma import irange, printf
    
    ACROSS = [3, 5, 3, 3, 3, 3, 3, 5, 3]
    DOWN = [6, 3, 7, 7, 6, 3]
    
    # find spaces for crossword solutions
    # return a list of: (<clue-number>, <A or D>, <solution-length>, <grid-position>)
    def spaces(g, n, n2):
      (p, r, i) = (0, [], 1)
      # find a blank
      while p < n2:
        if g[p] == '_':
          (a, d) = (0, 0)
          # could it start an across solution?
          if p % n == 0 or g[p - 1] != '_':
            # find the end of it
            (q, qm) = (p + 1, n * (1 + p // n))
            while q < qm and g[q] == '_': q += 1
            a = q - p
            if a > 1: r.append((i, 'A', a, p))
          # could it start a down solution?
          if p < n or g[p - n] != '_':
            # find the end of it
            q = p + n
            while q < n2 and g[q] == '_': q += n
            d = (q - p) // n
            if d > 1: r.append((i, 'D', d, p))
          if a > 1 or d > 1: i += 1
        p += 1
      return r
    
    # attempt to fit the solutions into the grid
    def fit(g, n, *s):
      # copy the grid
      f = list(g)
      # attempt to fit the solutions in
      for (w, x) in s:
        if len(w) != x[2]: return None
        i = x[3]
        for c in w:
          if not(f[i] == c or f[i] == '_'): return None
          f[i] = c
          i += (1 if x[1] == 'A' else n)
      return f
    
    # there are 7 letter down clues, so we need at least a 7 x 7 grid
    # also there are an odd number of across clues, so the grid must have odd dimensions
    
    # there are 9 across clues with 31 letters, and they all must
    # intersect with at least one (down) clue, and there are 6 down clues
    # with 32 letters, so, the maximum number of letter squares on any
    # grid is: 31 + 32 - max(9, 6) = 54
    
    # on a 9x9 grid that means at least 27 squares need to be shaded, but the maximum
    # number of shaded squares allowed is 20 (9^2 / 4), hence the only possible grid
    # is 7x7.
    
    n = 7
    n2 = n * n
    # we need to fill out at most 1/4 of the squares
    # and as the grid is symmetrical we only need to position half of them
    for f in irange(0, n2 // 8):
      # so fill out some of the squares
      for s in combinations(irange(0, n2 // 2), f):
        # make a grid with those squares filled out
        g = ['_'] * n2
        for i in s:
          g[i] = g[n2 - i - 1] = '#'
        # find the solutions on the grid
        s = spaces(g, n, n2)
        # check they fit the required solutions
        if list(i[2] for i in s if i[1] == 'A') != ACROSS: continue
        if list(i[2] for i in s if i[1] == 'D') != DOWN: continue
        # attempt to fill out CROSSED and WORDS
        s7 = list(i for i in s if 7 in (i[1], i[2]))
        s5 = list(i for i in s if 5 in (i[1], i[2]))
        for (c, w) in product(s7, s5):
          f = fit(g, n, ('CROSSED', c), ('WORDS', w))
          if f:
            # print the solution
            printf("{n}x{n} grid, CROSSED={c[0]}{c[1]}, WORDS={w[0]}{w[1]}\n")
            # print the grid
            for i in range(0, n2, n):
              print(''.join(f[i:i + n]))
            print()
    

    Solution: (a) the grid is 7×7; (b) CROSSED is the solution to 3 Down, and WORDS is the solution to 5 Across.

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: