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