# Sudoku solver, by Rimon Barr <rimon@acm.org>
# Started:  Sat Sep  2 10:18:30 EDT 2006
# Finished: Sat Sep  2 11:44:58 EDT 2006 (1h26)

__doc__ = '''python sudoku.py [<file>]+
  where <file> contains a 9x9 csv board,
  using pieces 1-9, and either nothing or '0' as empty. '''
import sys, operator, traceback

def solve(cells, pieces, rgns, c2r=None):
  ra=[pieces-set([cells[c] for c in ri if cells[c] in pieces])
    for i,ri in zip(range(len(rgns)),rgns)] # available by region
  if c2r is None:
    c2r={} # region lookup
    for i,ri in zip(range(len(rgns)),rgns):
      for ci in ri: c2r.setdefault(ci,[]).append(i)
    # input check
    ru=[[cells[c] for c in ri if cells[c] in pieces]
      for i,ri in zip(range(len(rgns)),rgns)] # used by region
    if reduce(operator.or_,[len(v)!=len(set(v)) for v in ru], False): 
      return None # invalid start
  ca=[(ci,reduce(operator.and_,[ra[ri] for ri in c2r[ci]],pieces)) 
    for ci in cells if cells[ci] not in pieces] # available by open cell
  ca.sort(lambda x,y: cmp(len(x[1]),len(y[1])))
  if not ca: return dict(cells)
  ci,p=ca[0]; cv,n,soln=cells[ci],0,None
  for pi in p:
    try: cells[ci]=pi; r=solve(cells, pieces, rgns, c2r)
    finally: cells[ci]=cv
    if not r: continue
    n+=1; soln=r
    if n>1: raise ValueError, 'multiple solutions'
  return soln

def solve333(board):
  # define constraints
  R = [[(r,c) for c in range(9)] for r in range(9)] # rows
  C = [[(r,c) for r in range(9)] for c in range(9)] # cols
  S = sum([[sum([[(r+sr*3,c+sc*3) for r in range(3)] for c in range(3)],[]) 
    for sr in range(3)] for sc in range(3)],[]) # 3x3 sq
  # convert to sparse, and solve
  v0 = dict(sum([[((r,c),board[r][c]) for r in range(9)] for c in range(9)],[]))
  return solve(v0, set(range(1,10)), R+C+S)

def show333(cells):
  if cells is None: print 'no solution'; return
  for r in range(9): print ','.join([str(cells[(r,c)]) for c in range(9)])

for fname in sys.argv[1:]:
  print 'File:', fname
  try:
    board = [[int(c or '0') for c in l.strip().split(',')] for l in open(fname).readlines()]
    try: show333(solve333(board))
    except ValueError, e: print e
  except: print 'Unexpected error:'; traceback.print_exception(*sys.exc_info())
  print