Enigmatic Code
Programming Enigma Puzzles
Enigma 1163: Clean up the square
Posted by on 13 June 2016
From New Scientist #2319, 1st December 2001 [link]
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]
Enigmatic Code 
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:
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)])# 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()