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