pseudoku/grid/__init__.py

   1 from __future__ import division
   2
   3 from math import sqrt
   4 from operator import attrgetter
   5 import re
   6 from weakref import ref
   7
   8 from constraints import Constraint, Row, Column, Box
   9
  10 symbols = [str(x + 1) for x in range(9)] + [chr(x + 97) for x in xrange(26)]
  11
  12 class GridSizeError(Exception):
  13     """Exception thrown when an impossible grid size is encountered."""
  14     pass
  15
  16 class GridIntegrityError(Exception):
  17     """Exception thrown when a grid's state violates its own constraints.  This
  18     should only happen if there are bugs in the code itself.
  19     """
  20     pass
  21
  22 class Cell(object):
  23     """Represents a single cell/value within a sudoku grid."""
  24
  25     ### Accessors
  26
  27     def _get_solved(self):
  28         """True iff this cell has been solved."""
  29         return len(self._values) == 1
  30     solved = property(_get_solved)
  31
  32     def _get_value(self):
  33         """Returns this cell's value, if it has one known."""
  34         if self.solved:
  35             return self._values[0]
  36         return None
  37     value = property(_get_value)
  38
  39     grid = property(lambda self: self._grid())
  40     constraints = property(attrgetter('_constraints'))
  41
  42     def __init__(self, grid, row, column):
  43         self._grid = ref(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_constraints(self, constraint_class=Constraint):
 148         """Returns constraints of a certain type.  Returns all of them by
 149         default.
 150         """
 151
 152         condition = lambda constraint: isinstance(constraint, constraint_class)
 153         return filter(condition, self._constraints)
 154
 155     rows = property(lambda self: self.get_constraints(Row))
 156     box_height = property(attrgetter('_box_height'))
 157     box_width = property(attrgetter('_box_width'))
 158     size = property(attrgetter('_size'))
 159     constraints = property(attrgetter('_constraints'))
 160
 161     ### Constructors
 162
 163     def __init__(self, box_height=3, box_width=None):
 164         if not box_width:
 165             box_width = box_height
 166
 167         self._box_height = box_height
 168         self._box_width = box_width
 169         self._size = box_height * box_width
 170
 171         self._cells = range(self.size ** 2)
 172         for row in xrange(self.size):
 173             for col in xrange(self.size):
 174                 self._cells[self._cellidx(row, col)] \
 175                     = Cell(self, row, col)
 176
 177         self._constraints = []
 178         self.add_default_constraints()
 179
 180     @classmethod
 181     def from_matrix(cls, rows, box_height=None, box_width=None):
 182         """Creates and returns a grid read from a list of lists."""
 183
 184         if not box_height:
 185             box_height, box_width = cls._infer_box_size(len(rows))
 186         elif not box_width:
 187             box_width = box_height
 188
 189         self = cls(box_width=box_width, box_height=box_height)
 190
 191         for row in xrange(self.size):
 192             for col in xrange(self.size):
 193                 value = rows[row][col]
 194                 if not value:
 195                     continue
 196                 self.cell(row, col).set(value - 1, normalize=False)
 197
 198         return self
 199
 200     @classmethod
 201     def from_string(cls, grid, box_height=None, box_width=None):
 202         # XXX sanity check dimensions
 203         """Creates and returns a grid from a string of symbols.
 204
 205         Symbols are the digits 1 to 9 followed by the letters of the alphabet.
 206         Zeroes and periods are assumed to be empty cells.  All other characters
 207         are ignored.
 208
 209         Since whitespace is ignored, the string could be all in one line or
 210         laid out visually in a square, one row per line."""
 211
 212         # Collapse the string down to just characters we want
 213         grid = grid.lower()
 214         grid = re.sub('\\.', '0', grid)
 215         grid = re.sub('[^0-9a-z]', '', grid)
 216
 217         # Figure out the length of one side/box
 218         size = int(sqrt(len(grid)))
 219         if size ** 2 != len(grid):
 220             raise GridSizeError("Provided string does not form a square")
 221
 222         # Set height/width..
 223         if not box_height:
 224             box_height, box_width = cls._infer_box_size(size)
 225         elif not box_width:
 226             box_width = box_height
 227
 228         self = cls(box_width=box_width, box_height=box_height)
 229
 230         for row in xrange(self.size):
 231             for col in xrange(self.size):
 232                 ch = grid[ self._cellidx(row, col) ]
 233                 if ch == '0':
 234                     continue
 235                 self.cell(row, col).set(symbols.index(ch), normalize=False)
 236
 237         return self
 238
 239     ### Constraints
 240
 241     def add_constraint(self, constraint):
 242         self._constraints.append(constraint)
 243         for cell in constraint.cells:
 244             cell.add_constraint(constraint)
 245
 246     def add_default_constraints(self):
 247         for i in xrange(self.size):
 248             self.add_constraint(Row(self, i))
 249             self.add_constraint(Column(self, i))
 250             self.add_constraint(Box(self, i))
 251
 252         return
 253
 254     ### Inspectors
 255
 256     def cell(self, row, column):
 257         return self._cells[self._cellidx(row, column)]
 258
 259     def is_filled(self):
 260         for cell in self._cells:
 261             if cell.value == None:
 262                 return False
 263         return True
 264
 265     ### Solving
 266
 267     def check(self):
 268         """Returns True iff the grid is solved.  Raises an exception if an
 269         integrity problem is found, such as a value appearing twice in a row.
 270         """
 271         # TODO remove this; name sucks and concept also sucks
 272         return None
 273
 274
 275     def solve(self):
 276         """Attempts to solve the grid."""
 277         # XXX track how many cells are changed and repeat as appropriate
 278
 279         # Step 0: Normalize cells, i.e. find any that can only be one value
 280         self.normalize_cells()
 281
 282         # Step 1: Find values that can only go in one cell in a group
 283         for group in self.constraints:
 284             group.resolve_uniques()
 285
 286
 287     def normalize_cells(self):
 288         """Normalizes every cell in the grid."""
 289         for cell in self._cells:
 290             cell.normalize()