#!/usr/bin/python
import cell_class
import sys
import string

# Constants
YEA = 1
NAY = None

# Rather than using "ord()" all over the place, do this:
MyAlphabet = '-123456789'

# becomes YEA if "-v" specified.  
verbose = NAY

# We have to define this somewhere.
Inconsistent = "formerly 'Unknown_with_no_hope'"

cells = []

# step 1
def loadit(input):
   global cells
   for i in range(0,81): cells.insert(i,cell_class.Cell(i))          # 1.1

   # Here, any cell's set_of_possibles should be full

   which_cell = 0
   for one_input_line in input.readlines():
      for char in one_input_line:
         if char in '\t\n ': continue
         if char in '-.': 
            which_cell = which_cell + 1
         elif char in MyAlphabet:
            cells[which_cell].setvalue(string.index(MyAlphabet,char))
            which_cell = which_cell + 1
         if which_cell > 81:
            raise too_much_input
   pass   # so the debugger can break here
   input.close()


def solve_simply():
   global cells
   something_was_set = 1
   while something_was_set:
      something_was_set = 0
      unknown_cells = filter(lambda a: not a.known(), cells)

      # 2.3 quit when all cells are known
      if len(unknown_cells) == 0: break         ## Done!  All known.

      for acell in unknown_cells:

         # 2.1 only one member in set_of_possibles?
         possible_digits = acell.possibles()
         if len(possible_digits) == 1:
            acell.setvalue(possible_digits[0])
            something_was_set = 1
            continue
         
         # 2.4 unknown but no possibilities?
         if len(possible_digits) == 0:
            raise Inconsistent

         # 2.2 any digit in only one cell in a row, column, or submatrix?
         global dig
         for dig in possible_digits:
            whohas = filter(lambda a: a.could_be(dig), acell.getrow())
            if len(whohas) == 1: break # unique in row
            whohas = filter(lambda a: a.could_be(dig), acell.getcolumn())
            if len(whohas) == 1: break # unique in col
            whohas = filter(lambda a: a.could_be(dig), acell.getsubmatrix())
            if len(whohas) == 1: break # unique in sub
         else: # "acell" has no unique digit (no "break" hit)
            continue  

         # Unique!  Set that value
         acell.setvalue(dig)
         something_was_set = 1
         pass # end of "for acell in unknown_cells"
      pass # end of "while something_was_set"
   
   # print len(unknown_cells), "unknown cells"
   return unknown_cells


# Code for step 3
def dumpit():
   for bor in range(0,81,9):
      for i in range(bor,bor+9):
         print MyAlphabet[cells[i].getvalue()], # '-' if unknown
      print                                     # end of this row
   pass # end of dumpit()


# return YEA iff solved.  Stop at first solution.
def solve_completely(level):
   try:
      unknown_cells = solve_simply()
   except Inconsistent:                 # part of 2.6.4
      return NAY

   if len(unknown_cells) == 0: return YEA  # declare victory

   # 2.6, create a guess
   if verbose:
      print "level =", level, ";", len(unknown_cells), "cells unknown"
      dumpit()

   # 2.6.1: Make a copy: a list of objects returned from cell_class.getbackup()
   mycopy = []
   for acell in cells:
      mycopy.append(acell.getbackup())

#  unknown_cells.sort(
#     lambda c1, c2: cmp(len(c1.possibles()), len(c2.possibles())))
   mycell = unknown_cells[0]                    # ... shortest set_of_possibles
   myset = mycell.possibles()
   if verbose: print "L=", level, "cell", mycell.getpos(), myset
   for myval in myset:
      if verbose: print "L=", level, "; cell[", mycell.getpos(), "] =", myval
      mycell.setvalue(myval)            # 2.6.2
      if solve_completely(level + 1):   # 2.6.3: call myself
         return YEA                     # 2.6.5: It worked; we're done!

      # 2.6.4: It didn't work.  Restore my backup copy.
      for i in range(81):
         cells[i].restore(mycopy[i])

      pass # Now try the next value in myset
   return NAY                   # None of the values worked; tell caller

   
def doit(argv):
   global verbose               # 'cause we're going to modify it
   if len(argv) > 1 and argv[1] and argv[1] == '-v':
      verbose = YEA
      del argv[1]

   if len(argv) > 1 and argv[1]:
      input = open(argv[1], 'r')
   else:
      input = sys.stdin

   loadit(input)                # step 1
   solve_completely(0)          # step 2
   dumpit()                     # step 3


# main begins here
if __name__ == '__main__': doit(sys.argv)