pseudoku/grid/cell.py

   1 from operator import attrgetter
   2 from weakref import ref
   3
   4 class Cell(object):
   5     """Represents a single cell/value within a sudoku grid."""
   6
   7     ### Accessors
   8
   9     def _get_solved(self):
  10         """True iff this cell has been solved."""
  11         return len(self._values) == 1
  12     solved = property(_get_solved)
  13
  14     def _get_value(self):
  15         """Returns this cell's value, if it has one known."""
  16         if self.solved:
  17             return self._values[0]
  18         return None
  19     value = property(_get_value)
  20
  21     grid = property(lambda self: self._grid())
  22     constraints = property(attrgetter('_constraints'))
  23
  24     def __init__(self, grid, row, column):
  25         self._grid = ref(grid)
  26         self._row = row
  27         self._col = column
  28         self._values = range(self.grid.size)
  29         self._constraints = []
  30         self._normalized = False
  31
  32     def add_constraint(self, constraint):
  33         self._constraints.append(constraint)
  34
  35     def set(self, value, normalize=True):
  36         """Sets the value of this cell.  If `normalize` is True or omitted, the
  37         grid will be updated accordingly.
  38
  39         Returns the number of cell changes.
  40         """
  41         self._values = [value]
  42         if normalize:
  43             self._normalized = False
  44             return self.normalize() + 1
  45
  46         return 1
  47
  48
  49     def normalize(self):
  50         """Checks to see if this cell has only one possible value left.  If
  51         so, sets that as its value and eliminates it from every related cell.
  52         This method is exhaustive; repeated calls should have no effect.
  53
  54         Returns the number of cell changes.
  55         """
  56
  57         if self._normalized:
  58             # Already done
  59             return 0
  60
  61         # Set this now just in case of infinite looping
  62         self._normalized = True
  63
  64         if not self.solved:
  65             # Don't know the value yet
  66             return 0
  67
  68         # Elimination time
  69         cell_changes = 0
  70         for constraint in self.constraints:
  71             for cell in constraint.cells:
  72                 if cell == self:
  73                     continue
  74                 cell_changes += cell.eliminate(self.value)
  75
  76         return cell_changes
  77
  78     def eliminate(self, value):
  79         """Eliminates the given value as a possibility for this cell.
  80
  81         Returns the number of cell changes."""
  82         if value not in self._values:
  83             return 0
  84
  85         self._values.remove(value)
  86
  87         if len(self._values) == 0:
  88             # XXX give me a real exception here
  89             raise Exception
  90
  91         self._normalized = False
  92         return self.normalize() + 1