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     def __str__(self):
 121         """Stringification for pretty-printing."""
 122         if self.value != None:
 123             return symbols[self.value]
 124
 125         return '.'
 126
 127
 128 class Grid(object):
 129     """Represents a Sudoku grid."""
 130
 131     ### Utilities
 132
 133     def _cellidx(self, row, col):
 134         """Hashes a row and column into a flat array index."""
 135         return row * self._size + col
 136
 137     @classmethod
 138     def _infer_box_size(cls, dimension):
 139         """Attempts to infer the size of a box, given some dimension of the
 140         entire grid, i.e. the number of cells per box/row/column.
 141
 142         Returns a tuple of height, width."""
 143
 144         # Most obvious: probably n * n.
 145         root = int(sqrt(dimension))
 146         if root ** 2 == dimension:
 147             return root, root
 148
 149         # Otherwise, probably n * (n - 1) or n * (n - 2).
 150         # These puzzles generally have the wide side (n) as the width.
 151         # This is of course entirely unreliable, but better than nothing..
 152         #   n^2 - (1|2)n - dimension = 0
 153         #   Determinant is (1|2)^2 + 4 * dimension and has to be square
 154         for difference in 1, 2:
 155             determinant = difference ** 2 + 4 * dimension
 156             root = int(sqrt(determinant))
 157             if root ** 2 != determinant:
 158                 continue
 159
 160             n = (-difference + root) / 2
 161             if n != int(n):
 162                 continue
 163
 164             # Success!
 165             return n - difference, n
 166
 167         # Okay, I don't have a clue.
 168         raise GridSizeError("Can't infer box height and width for grid size "
 169                             "%d; please specify them manually" % dimension)
 170
 171     ### Accessors
 172
 173     def _get_box_height(self):
 174         return self._box_height
 175     box_height = property(_get_box_height)
 176
 177     def _get_box_width(self):
 178         return self._box_width
 179     box_width = property(_get_box_width)
 180
 181     def _get_size(self):
 182         return self._size
 183     size = property(_get_size)
 184
 185     def _get_cell_groups(self):
 186         return self._rows + self._columns + self._boxes
 187     cell_groups = property(_get_cell_groups)
 188
 189     ### Constructors
 190
 191     def __init__(self, box_height=3, box_width=None):
 192         if not box_width:
 193             box_width = box_height
 194
 195         self._box_height = box_height
 196         self._box_width = box_width
 197         self._size = box_height * box_width
 198
 199         self._rows = [Row(self, i) for i in xrange(self._size)]
 200         self._columns = [Column(self, i) for i in xrange(self._size)]
 201         self._boxes = [Box(self, i) for i in xrange(self._size)]
 202
 203         self._cells = range(self._size ** 2)
 204         for row in xrange(self._size):
 205             for col in xrange(self._size):
 206                 self._cells[self._cellidx(row, col)] \
 207                     = Cell(self, row, col)
 208
 209     @classmethod
 210     def from_matrix(cls, rows, box_height=None, box_width=None):
 211         """Creates and returns a grid read from a list of lists."""
 212
 213         if not box_height:
 214             box_height, box_width = cls._infer_box_size(len(rows))
 215         elif not box_width:
 216             box_width = box_height
 217
 218         self = cls(box_width=box_width, box_height=box_height)
 219
 220         for row in xrange(self._size):
 221             for col in xrange(self._size):
 222                 value = rows[row][col]
 223                 if not value:
 224                     continue
 225                 self.cell(row, col).set_naively(value - 1)
 226
 227         return self
 228
 229     @classmethod
 230     def from_string(cls, grid, box_height=None, box_width=None):
 231         # XXX sanity check dimensions
 232         """Creates and returns a grid from a string of symbols.
 233
 234         Symbols are the digits 1 to 9 followed by the letters of the alphabet.
 235         Zeroes and periods are assumed to be empty cells.  All other characters
 236         are ignored.
 237
 238         Since whitespace is ignored, the string could be all in one line or
 239         laid out visually in a square, one row per line."""
 240
 241         # Collapse the string down to just characters we want
 242         grid = grid.lower()
 243         grid = re.sub('\\.', '0', grid)
 244         grid = re.sub('[^0-9a-z]', '', grid)
 245
 246         # Figure out the length of one side/box
 247         size = int(sqrt(len(grid)))
 248         if size ** 2 != len(grid):
 249             raise GridSizeError("Provided string does not form a square")
 250
 251         # Set height/width..
 252         if not box_height:
 253             box_height, box_width = cls._infer_box_size(size)
 254         elif not box_width:
 255             box_width = box_height
 256
 257         self = cls(box_width=box_width, box_height=box_height)
 258
 259         for row in xrange(self._size):
 260             for col in xrange(self._size):
 261                 ch = grid[ self._cellidx(row, col) ]
 262                 if ch == '0':
 263                     continue
 264                 self.cell(row, col).set_naively(symbols.index(ch))
 265
 266         return self
 267
 268     ### Inspectors
 269
 270     def cell(self, row, column):
 271         return self._cells[self._cellidx(row, column)]
 272
 273     def is_filled(self):
 274         for cell in self._cells:
 275             if cell.value == None:
 276                 return False
 277         return True
 278
 279     ### Solving
 280
 281     def check(self):
 282         """Returns True iff the grid is solved.  Raises an exception if an
 283         integrity problem is found, such as a value appearing twice in a row.
 284         """
 285         # TODO remove this; name sucks and concept also sucks
 286         return None
 287
 288
 289     def solve(self):
 290         """Attempts to solve the grid."""
 291         # XXX track how many cells are changed and repeat as appropriate
 292
 293         # Step 0: Normalize cells, i.e. find any that can only be one value
 294         self.normalize_cells()
 295
 296         # Step 1: Find values that can only go in one cell in a group
 297         for group in self.cell_groups:
 298             group.resolve_uniques()
 299
 300
 301     def normalize_cells(self):
 302         """Normalizes every cell in the grid."""
 303         for cell in self._cells:
 304             cell.normalize()
 305
 306
 307     def __str__(self):
 308         """Pretty-printing."""
 309         divider = '+'
 310         for box in xrange(self._box_height):
 311             for col in xrange(self._box_width):
 312                 divider += '-'
 313             divider += '+'
 314
 315         res = ''
 316         for row in xrange(self._size):
 317             if row % self._box_height == 0:
 318                 res += divider
 319                 res += "\n"
 320
 321             for col in xrange(self._size):
 322                 if col % self._box_width == 0:
 323                     res += '|'
 324                 res += str(self.cell(row, col))
 325
 326             res += '|'
 327             res += "\n"
 328
 329         res += divider
 330         res += "\n"
 331
 332         return res