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