class Cell:
   rows = [ [], [], [], [], [], [], [], [], [] ]    # nine each...
   columns = [ [], [], [], [], [], [], [], [], [] ]
   submatrices = [ [], [], [], [], [], [], [], [], [] ]

   # for step 1.1, do "cells[i]=Cell(i)" for i in range(0,81)
   def __init__(self,pos):
      # "pos" = position in the puzzle.  Valid values: range (0,81)
      global rows, columns, submatrices
      if pos not in range(0,81):
         raise Illegal_pos_in_Cells_initializer
      self.XYZpos = pos
      self.XYZvalue = 0
      self.XYZset_of_possibles = range(1, 10)  # 1-9 INclusive

      # For step 1.2.2b, track which row, col, sub that I belong to.
      myrow = int(pos / 9)
      mycol = pos % 9
      mysub = int(myrow/3) * 3 + int(mycol/3)

      self.XYZrow = Cell.rows[myrow]
      self.XYZcol = Cell.columns[mycol]
      self.XYZsub = Cell.submatrices[mysub]

      self.XYZrow.append(self)
      self.XYZcol.append(self)
      self.XYZsub.append(self)

   def known(self):
      return (self.XYZvalue != 0)

   # setvalue is used for 1.2.2
   def setvalue(self, val):
      # a couple of sanity checks
      if val not in range(1,9+1):
         raise val_must_be_between_1_and_9
      if val not in self.XYZset_of_possibles:
         raise setting_impossible_value
      if self.known():
         raise setvalue_called_but_already_known

      self.XYZvalue = val              # 1.2.2a
      self.XYZset_of_possibles = []    # make life easier in step2.6

      # Now do 1.2.2b
      for other in self.XYZrow + self.XYZcol + self.XYZsub:
         if other is self: continue
         if other.known(): continue
         if val in other.XYZset_of_possibles:
            # Though "remove" isn't in the book, it's not deprecated...
            other.XYZset_of_possibles.remove(val)

   def getvalue(self): return self.XYZvalue
   def getrow(self): return self.XYZrow
   def getcolumn(self): return self.XYZcol
   def getsubmatrix(self): return self.XYZsub
   def possibles(self): return self.XYZset_of_possibles[:]
   def could_be(self,val):
      if self.known(): return (val == self.XYZvalue)
      return (val in self.possibles())
   def getpos(self): return self.XYZpos
   def getbackup(self):
      return [ self.XYZvalue, self.XYZset_of_possibles[:] ]
   def restore(self,bkp):
      self.XYZvalue = bkp[0]
      self.XYZset_of_possibles = bkp[1][:]