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     # NOTE: _cells is a list of refs; _grid is a ref
  11     # XXX document this
  12     cells = property(lambda self: [ x() for x in self._cells ])
  13     grid = property(lambda self: self._grid())
  14
  15     ### Methods
  16     # XXX inherited __init__ to init _grid/_cells
  17
  18     def find_value(self, value):
  19         """Returns the cells that can be a specific value."""
  20         possible_cells = []
  21         for cell in self.cells:
  22             if value in cell._values:
  23                 possible_cells.append(cell)
  24
  25         if len(possible_cells) == 0:
  26             raise Exception  # XXX
  27
  28         return possible_cells
  29
  30     def resolve_uniques(self):
  31         for value in xrange(self.grid.size):
  32             # XXX cache values that are taken care of
  33             possible_cells = self.find_value(value)
  34
  35             if len(possible_cells) > 1:
  36                 # Not unique
  37                 continue
  38
  39             target_cell = possible_cells[0]
  40             if target_cell.solved:
  41                 # Already seen this
  42                 # XXX this is what cache is for
  43                 continue
  44
  45             # Only cell in the group that can be value
  46             target_cell.set(value)
  47
  48
  49 class Box(Constraint):
  50     def _get_box_row(self):
  51         return self._pos // self.grid.box_width
  52     box_row = property(_get_box_row)
  53
  54     def _get_box_column(self):
  55         return self._pos % self.grid.box_height
  56     box_column = property(_get_box_column)
  57
  58     def __init__(self, grid, position):
  59         self._grid = ref(grid)
  60         self._pos = position
  61
  62         self._cells = []
  63         for row in xrange(self.grid.box_height):
  64             for col in xrange(self.grid.box_width):
  65                 cell_row = row + self.box_row * self.grid.box_height
  66                 cell_col = col + self.box_column * self.grid.box_width
  67                 self._cells.append(ref(self.grid.cell(cell_row, cell_col)))
  68
  69
  70 class Row(Constraint):
  71     def __init__(self, grid, position):
  72         self._grid = ref(grid)
  73         self._pos = position
  74
  75         self._cells = []
  76         for col in xrange(self.grid.size):
  77             self._cells.append(ref(self.grid.cell(self._pos, col)))
  78
  79 class Column(Constraint):
  80     def __init__(self, grid, position):
  81         self._grid = ref(grid)
  82         self._pos = position
  83
  84         self._cells = []
  85         for row in xrange(self.grid.size):
  86             self._cells.append(ref(self.grid.cell(row, self._pos)))
  87
  88 class Diagonal(Constraint):
  89     def __init__(self, grid, direction='down', offset=0):
  90         self._grid = ref(grid)
  91         self._direction = direction
  92         self._offset = offset
  93
  94         if direction == 'down':
  95             coords = {'row': 0, 'column': 0}
  96             increment = 1
  97         elif direction == 'up':
  98             coords = {'row': 0, 'column': grid.size - 1}
  99             increment = -1
 100         else:
 101             raise Exception # XXX
 102
 103         # XXX
 104         if offset != 0:
 105             raise NotImplementedError
 106
 107         self._cells = []
 108         for i in xrange(self.grid.size):
 109             self._cells.append(ref(self.grid.cell(coords['row'], coords['column'])))
 110             coords['row'] += 1
 111             coords['column'] += increment