Enigmatic Code

Programming Enigma Puzzles

Enigma 1163: Clean up the square

From New Scientist #2319, 1st December 2001 [link]

Enigma 1163

Delete two of the three occurrences of each letter in the square (above), so that you leave one letter in each row and in each column.

Look at the square you obtain. What is the letter in the top row, the letter in the second row, …, the letter in the bottom row, in that order?

[enigma1163]

Advertisements

3 responses to “Enigma 1163: Clean up the square

  1. Jim Randell 13 June 2016 at 8:29 am

    This Python 3 program runs in 41ms.

    from enigma import irange, chunk, join
    
    # dimensions of the grid
    N = 9
    
    # related squares
    related = []
    for i in irange(0, N * N - 1):
      rs = set()
      # related squares are in the same row and same column
      (r, c) = divmod(i, N)
      rs.update(j + r * N for j in irange(0, N - 1))
      rs.update(j * N + c for j in irange(0, N - 1))
      # but not the square itself
      rs.discard(i)
      related.append(rs)
    
    # remove elements from the grid
    def remove(grid, rs):
      g = list(grid)
      for i in rs:
        g[i] = '_'
      return g
    
    def solve(grid, s):
      # are we done?
      if not s:
        yield grid
      else:
        # find occurrences of the next letter
        ps = list(p for (p, x) in enumerate(grid) if x == s[0])
        # choose one of the occurrences to keep
        for (i, p) in enumerate(ps):
          # remove the other occurrences
          # and any letters in related squares
          rs = related[p].union(ps[:i], ps[i + 1:])
          # provided we are not removing any earlier letters
          if any(grid[j] < grid[p] for j in rs): continue
          yield from solve(remove(grid, rs), s[1:])
    
    # we choose _ to represent empty squares, so that it compares as
    # greater than any of the letters
    grid = list(
      '_C___G__B' +
      '___B__EG_' +
      'D_I___A__' +
      '___F_I__E' +
      '_A__FH___' +
      '__C___F_D' +
      'H_B____C_' +
      '_I_HE____' +
      'G___A__D_'
    )
    
    # find solutions for the given grid
    for g in solve(grid, 'ABCDEFGHI'):
      for r in chunk(g, N):
        print(join(r))
      print()
    

    Solution: The remaining letters in each row, from top to bottom, are: G, B, A, E, F, C, H, I, D.

    There is only one solution for the grid, shown below:

    Enigma 1163 - Solution

  2. arthurvause 13 June 2016 at 10:37 am

    For 9 letters each occuring 3 times, it is feasible to do a brute force search of the 3**9 = 19683 possible options of distinct letters, but this solution wouldn’t be scalable.

    from itertools import product
    from collections import defaultdict
    
    square =  [list( x ) for x in 
      ['.C...G..B' ,
       '...B..EG.' ,
       'D.I...A..' ,
       '...F.I..E' ,
       '.A..FH...' ,
       '..C...F.D' ,
       'H.B....C.' ,
       '.I.HE....' ,
       'G...A..D.']]
    
    positions = defaultdict(list)
    for i in xrange(9):
      for j in xrange(9):
        if square[i][j] != '.':
          positions[square[i][j]].append((i,j))
    
    for p in  product(*[positions[x] for x in positions]) :
      if len(set( x for (x,y) in p))==9:
        if len(set( y for (x,y) in p))==9:
          print ''.join([ square[x][y] for (x,y) in sorted(p)])
    
  3. Brian Gladman 13 June 2016 at 5:35 pm
    # the size of the grid
    M = 9
    
    def solve(s, lev):
      if lev == 9:
        # all letters have been processed
        yield s
      else:
        # select the next letter and find its positions
        ch = 'ABCDEFGHI'[lev]
        ixs = (i for i, c in enumerate(s) if c == ch)
        # try each letter position as that remaining
        for ix in ixs:
          # compile a new grid with other copies of this letter removed
          ss = [c if c != ch or i == ix else '-' for i, c in enumerate(s)]
          
          # since there is only one letter in each row and column, we
          # can now remove other letters from them for this position
          rr, cc = divmod(ss.index(ch), M)
          for i in range(M):
            if ss[M * rr + i] not in (ch, '-'):
              ss[M * rr + i] = '-'
            if ss[M * i + cc] not in (ch, '-'):
              ss[M * i + cc] = '-'
      
          # check that all rows and columns have at least one letter 
          if (all(s[i : i + M].count('-') != M for i in range(0, M * M, M)) and
              all(s[i : M * M : M].count('-') != M for i in range(M))):
            yield from solve(ss, lev + 1)
    
    # the initial grid
    sq = list( '-C---G--B'  '---B--EG-'  'D-I---A--'
               '---F-I--E'  '-A--FH---'  '--C---F-D'
               'H-B----C-'  '-I-HE----'  'G---A--D-' )
    
    # find solutions with one letter in each row and column
    for s in solve(sq, 0):
      ss = ''.join(s)
      for r in range(0, M * M, M):
        print(ss[r : r + 9])
      print()
    

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: