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