pseudoku/grid/__init__.py

   1 from __future__ import division
   2
   3 from math import sqrt
   4 import re
   5 from weakref import proxy
   6
   7 from cellgroup import Row, Column, Box
   8
   9 symbols = [str(x + 1) for x in range(9)] + [chr(x + 97) for x in xrange(26)]
  10
  11 class GridSizeError(Exception):
  12     """Exception thrown when an impossible grid size is encountered."""
  13     pass
  14
  15 class GridIntegrityError(Exception):
  16     """Exception thrown when a grid's state violates its own constraints.  This
  17     should only happen if there are bugs in the code itself.
  18     """
  19     pass
  20
  21 class Cell(object):
  22     """Represents a single cell/value within a sudoku grid."""
  23
  24     ### Accessors
  25
  26     def _get_solved(self):
  27         """True iff this cell has been solved."""
  28         return len(self._values) == 1
  29     solved = property(_get_solved)
  30
  31     def _get_value(self):
  32         """Returns this cell's value, if it has one known."""
  33         if self.solved:
  34             return self._values[0]
  35         return None
  36     value = property(_get_value)
  37
  38     def _get_constraints(self):
  39         return self._constraints
  40     constraints = property(_get_constraints)
  41
  42     def __init__(self, grid, row, column):
  43         self._grid = proxy(grid)
  44         self._row = row
  45         self._col = column
  46         self._values = range(self._grid.size)
  47         self._constraints = []
  48         self._normalized = False
  49
  50     def add_constraint(self, constraint):
  51         self._constraints.append(constraint)
  52
  53     def set(self, value, normalize=True):
  54         """Sets the value of this cell.  If `normalize` is True or omitted, the
  55         grid will be updated accordingly.
  56         """
  57         self._values = [value]
  58         if normalize:
  59             self._normalized = False
  60             self.normalize()
  61
  62
  63
  64     def normalize(self):
  65         """Checks to see if this cell has only one possible value left.  If
  66         so, sets that as its value and eliminates it from every related cell.
  67         This method is exhaustive; that repeated calls should have no effect.
  68         """
  69
  70         if self._normalized:
  71             # Already done
  72             return
  73
  74         # Set this now just in case of infinite looping
  75         self._normalized = True
  76
  77         if not self.solved:
  78             # Don't know the value yet
  79             return
  80
  81         # Elimination time
  82         for constraint in self.constraints:
  83             for cell in constraint.cells:
  84                 if cell == self:
  85                     continue
  86                 cell.eliminate(self.value)
  87
  88
  89     def eliminate(self, value):
  90         """Eliminates the given value as a possibility for this cell."""
  91         if value in self._values:
  92             self._values.remove(value)
  93
  94             if len(self._values) == 0:
  95                 # XXX give me a real exception here
  96                 raise Exception
  97
  98             self._normalized = False
  99             self.normalize()
 100
 101
 102 class Grid(object):
 103     """Represents a Sudoku grid."""
 104
 105     ### Utilities
 106
 107     def _cellidx(self, row, col):
 108         """Hashes a row and column into a flat array index."""
 109         return row * self._size + col
 110
 111     @classmethod
 112     def _infer_box_size(cls, dimension):
 113         """Attempts to infer the size of a box, given some dimension of the
 114         entire grid, i.e. the number of cells per box/row/column.
 115
 116         Returns a tuple of height, width."""
 117
 118         # Most obvious: probably n * n.
 119         root = int(sqrt(dimension))
 120         if root ** 2 == dimension:
 121             return root, root
 122
 123         # Otherwise, probably n * (n - 1) or n * (n - 2).
 124         # These puzzles generally have the wide side (n) as the width.
 125         # This is of course entirely unreliable, but better than nothing..
 126         #   n^2 - (1|2)n - dimension = 0
 127         #   Determinant is (1|2)^2 + 4 * dimension and has to be square
 128         for difference in 1, 2:
 129             determinant = difference ** 2 + 4 * dimension
 130             root = int(sqrt(determinant))
 131             if root ** 2 != determinant:
 132                 continue
 133
 134             n = (-difference + root) / 2
 135             if n != int(n):
 136                 continue
 137
 138             # Success!
 139             return n - difference, n
 140
 141         # Okay, I don't have a clue.
 142         raise GridSizeError("Can't infer box height and width for grid size "
 143                             "%d; please specify them manually" % dimension)
 144
 145     ### Accessors
 146
 147     def _get_box_height(self):
 148         return self._box_height
 149     box_height = property(_get_box_height)
 150
 151     def _get_box_width(self):
 152         return self._box_width
 153     box_width = property(_get_box_width)
 154
 155     def _get_size(self):
 156         return self._size
 157     size = property(_get_size)
 158
 159     def _get_constraints(self):
 160         return self._constraints
 161     constraints = property(_get_constraints)
 162
 163     ### Constructors
 164
 165     def __init__(self, box_height=3, box_width=None):
 166         if not box_width:
 167             box_width = box_height
 168
 169         self._box_height = box_height
 170         self._box_width = box_width
 171         self._size = box_height * box_width
 172
 173         self._cells = range(self._size ** 2)
 174         for row in xrange(self._size):
 175             for col in xrange(self._size):
 176                 self._cells[self._cellidx(row, col)] \
 177                     = Cell(self, row, col)
 178
 179         self._constraints = []
 180         self.add_default_constraints()
 181
 182     @classmethod
 183     def from_matrix(cls, rows, box_height=None, box_width=None):
 184         """Creates and returns a grid read from a list of lists."""
 185
 186         if not box_height:
 187             box_height, box_width = cls._infer_box_size(len(rows))
 188         elif not box_width:
 189             box_width = box_height
 190
 191         self = cls(box_width=box_width, box_height=box_height)
 192
 193         for row in xrange(self._size):
 194             for col in xrange(self._size):
 195                 value = rows[row][col]
 196                 if not value:
 197                     continue
 198                 self.cell(row, col).set(value - 1, normalize=False)
 199
 200         return self
 201
 202     @classmethod
 203     def from_string(cls, grid, box_height=None, box_width=None):
 204         # XXX sanity check dimensions
 205         """Creates and returns a grid from a string of symbols.
 206
 207         Symbols are the digits 1 to 9 followed by the letters of the alphabet.
 208         Zeroes and periods are assumed to be empty cells.  All other characters
 209         are ignored.
 210
 211         Since whitespace is ignored, the string could be all in one line or
 212         laid out visually in a square, one row per line."""
 213
 214         # Collapse the string down to just characters we want
 215         grid = grid.lower()
 216         grid = re.sub('\\.', '0', grid)
 217         grid = re.sub('[^0-9a-z]', '', grid)
 218
 219         # Figure out the length of one side/box
 220         size = int(sqrt(len(grid)))
 221         if size ** 2 != len(grid):
 222             raise GridSizeError("Provided string does not form a square")
 223
 224         # Set height/width..
 225         if not box_height:
 226             box_height, box_width = cls._infer_box_size(size)
 227         elif not box_width:
 228             box_width = box_height
 229
 230         self = cls(box_width=box_width, box_height=box_height)
 231
 232         for row in xrange(self._size):
 233             for col in xrange(self._size):
 234                 ch = grid[ self._cellidx(row, col) ]
 235                 if ch == '0':
 236                     continue
 237                 self.cell(row, col).set(symbols.index(ch), normalize=False)
 238
 239         return self
 240
 241     ### Constraints
 242
 243     def add_constraint(self, constraint):
 244         self._constraints.append(constraint)
 245         for cell in constraint.cells:
 246             cell.add_constraint(constraint)
 247
 248     def add_default_constraints(self):
 249         for i in xrange(self._size):
 250             self.add_constraint(Row(self, i))
 251             self.add_constraint(Column(self, i))
 252             self.add_constraint(Box(self, i))
 253
 254         return
 255
 256     ### Inspectors
 257
 258     def cell(self, row, column):
 259         return self._cells[self._cellidx(row, column)]
 260
 261     def is_filled(self):
 262         for cell in self._cells:
 263             if cell.value == None:
 264                 return False
 265         return True
 266
 267     ### Solving
 268
 269     def check(self):
 270         """Returns True iff the grid is solved.  Raises an exception if an
 271         integrity problem is found, such as a value appearing twice in a row.
 272         """
 273         # TODO remove this; name sucks and concept also sucks
 274         return None
 275
 276
 277     def solve(self):
 278         """Attempts to solve the grid."""
 279         # XXX track how many cells are changed and repeat as appropriate
 280
 281         # Step 0: Normalize cells, i.e. find any that can only be one value
 282         self.normalize_cells()
 283
 284         # Step 1: Find values that can only go in one cell in a group
 285         for group in self.constraints:
 286             group.resolve_uniques()
 287
 288
 289     def normalize_cells(self):
 290         """Normalizes every cell in the grid."""
 291         for cell in self._cells:
 292             cell.normalize()