pseudoku/grid/constraints.py

   1 from __future__ import division
   2
   3 from weakref import ref
   4
   5 class Constraint(object):
   6     """Represents any group of cells in a grid that cannot repeat a digit."""
   7
   8     ### Accessors
   9
  10     # True iff a constraint consists of a straight line of cells.  Used to
  11     # quickly skip over pairs of constraints that cannot possibly have more
  12     # than one cell in common.
  13     is_linear = False
  14
  15     # NOTE: _cells is a list of refs; _grid is a ref
  16     # XXX document this
  17     cells = property(lambda self: [ x() for x in self._cells ])
  18     grid = property(lambda self: self._grid())
  19
  20     ### Methods
  21     # XXX inherited __init__ to init _grid/_cells
  22
  23     def find_value(self, value):
  24         """Returns the cells that can be a specific value."""
  25         possible_cells = []
  26         for cell in self.cells:
  27             if value in cell._values:
  28                 possible_cells.append(cell)
  29
  30         if len(possible_cells) == 0:
  31             raise Exception  # XXX
  32
  33         return possible_cells
  34
  35     def resolve_uniques(self):
  36         """Searches for values that can only appear in one cell, and sets them
  37         appropriately.
  38
  39         Returns the number of cell changes.
  40         """
  41
  42         cell_changes = 0
  43
  44         for value in xrange(self.grid.size):
  45             # XXX cache values that are taken care of
  46             possible_cells = self.find_value(value)
  47
  48             if len(possible_cells) > 1:
  49                 # Not unique
  50                 continue
  51
  52             target_cell = possible_cells[0]
  53             if target_cell.solved:
  54                 # Already seen this
  55                 # XXX this is what cache is for
  56                 continue
  57
  58             # Only cell in the group that can be value
  59             cell_changes += target_cell.set(value)
  60
  61         return cell_changes
  62
  63
  64 class Box(Constraint):
  65     def _get_box_row(self):
  66         return self._pos // self.grid.box_width
  67     box_row = property(_get_box_row)
  68
  69     def _get_box_column(self):
  70         return self._pos % self.grid.box_height
  71     box_column = property(_get_box_column)
  72
  73     def __init__(self, grid, position):
  74         self._grid = ref(grid)
  75         self._pos = position
  76
  77         self._cells = []
  78         for row in xrange(self.grid.box_height):
  79             for col in xrange(self.grid.box_width):
  80                 cell_row = row + self.box_row * self.grid.box_height
  81                 cell_col = col + self.box_column * self.grid.box_width
  82                 self._cells.append(ref(self.grid.cell(cell_row, cell_col)))
  83
  84
  85 class Row(Constraint):
  86     is_linear = True
  87
  88     def __init__(self, grid, position):
  89         self._grid = ref(grid)
  90         self._pos = position
  91
  92         self._cells = []
  93         for col in xrange(self.grid.size):
  94             self._cells.append(ref(self.grid.cell(self._pos, col)))
  95
  96 class Column(Constraint):
  97     is_linear = True
  98
  99     def __init__(self, grid, position):
 100         self._grid = ref(grid)
 101         self._pos = position
 102
 103         self._cells = []
 104         for row in xrange(self.grid.size):
 105             self._cells.append(ref(self.grid.cell(row, self._pos)))
 106
 107 class Diagonal(Constraint):
 108     is_linear = True
 109
 110     def __init__(self, grid, direction='down', offset=0):
 111         self._grid = ref(grid)
 112         self._direction = direction
 113         self._offset = offset
 114
 115         if direction == 'down':
 116             coords = {'row': 0, 'column': 0}
 117             increment = 1
 118         elif direction == 'up':
 119             coords = {'row': 0, 'column': grid.size - 1}
 120             increment = -1
 121         else:
 122             raise Exception # XXX
 123
 124         # XXX
 125         if offset != 0:
 126             raise NotImplementedError
 127
 128         self._cells = []
 129         for i in xrange(self.grid.size):
 130             self._cells.append(ref(self.grid.cell(coords['row'], coords['column'])))
 131             coords['row'] += 1
 132             coords['column'] += increment