pseudoku/grid/__init__.py

   1 from __future__ import division
   2
   3 from math import sqrt
   4 from operator import attrgetter
   5 import re
   6
   7 from cell import Cell
   8 from constraints import Constraint, Row, Column, Box
   9
  10 symbols = [str(x + 1) for x in range(9)] + [chr(x + 97) for x in xrange(26)]
  11
  12 class GridSizeError(Exception):
  13     """Exception thrown when an impossible grid size is encountered."""
  14     pass
  15
  16 class GridIntegrityError(Exception):
  17     """Exception thrown when a grid's state violates its own constraints.  This
  18     should only happen if there are bugs in the code itself.
  19     """
  20     pass
  21
  22
  23 class Grid(object):
  24     """Represents a Sudoku grid."""
  25
  26     ### Utilities
  27
  28     def _cellidx(self, row, col):
  29         """Hashes a row and column into a flat array index."""
  30         return row * self.size + col
  31
  32     @classmethod
  33     def _infer_box_size(cls, dimension):
  34         """Attempts to infer the size of a box, given some dimension of the
  35         entire grid, i.e. the number of cells per box/row/column.
  36
  37         Returns a tuple of height, width."""
  38
  39         # Most obvious: probably n * n.
  40         root = int(sqrt(dimension))
  41         if root ** 2 == dimension:
  42             return root, root
  43
  44         # Otherwise, probably n * (n - 1) or n * (n - 2).
  45         # These puzzles generally have the wide side (n) as the width.
  46         # This is of course entirely unreliable, but better than nothing..
  47         #   n^2 - (1|2)n - dimension = 0
  48         #   Determinant is (1|2)^2 + 4 * dimension and has to be square
  49         for difference in 1, 2:
  50             determinant = difference ** 2 + 4 * dimension
  51             root = int(sqrt(determinant))
  52             if root ** 2 != determinant:
  53                 continue
  54
  55             n = (-difference + root) / 2
  56             if n != int(n):
  57                 continue
  58
  59             # Success!
  60             return n - difference, n
  61
  62         # Okay, I don't have a clue.
  63         raise GridSizeError("Can't infer box height and width for grid size "
  64                             "%d; please specify them manually" % dimension)
  65
  66     ### Accessors
  67
  68     def get_constraints(self, constraint_class=Constraint):
  69         """Returns constraints of a certain type.  Returns all of them by
  70         default.
  71         """
  72
  73         condition = lambda constraint: isinstance(constraint, constraint_class)
  74         return filter(condition, self._constraints)
  75
  76     rows = property(lambda self: self.get_constraints(Row))
  77     columns = property(lambda self: self.get_constraints(Column))
  78     boxes = property(lambda self: self.get_constraints(Box))
  79
  80     box_height = property(attrgetter('_box_height'))
  81     box_width = property(attrgetter('_box_width'))
  82     size = property(attrgetter('_size'))
  83     constraints = property(attrgetter('_constraints'))
  84
  85     def _is_filled(self):
  86         for cell in self._cells:
  87             if cell.value == None:
  88                 return False
  89         return True
  90     filled = property(_is_filled)
  91
  92     ### Constructors
  93
  94     def __init__(self, box_height=3, box_width=None):
  95         if not box_width:
  96             box_width = box_height
  97
  98         self._box_height = box_height
  99         self._box_width = box_width
 100         self._size = box_height * box_width
 101
 102         self._cells = range(self.size ** 2)
 103         for row in xrange(self.size):
 104             for col in xrange(self.size):
 105                 self._cells[self._cellidx(row, col)] \
 106                     = Cell(self, row, col)
 107
 108         self._constraints = []
 109         self.add_default_constraints()
 110
 111     @classmethod
 112     def from_matrix(cls, rows, box_height=None, box_width=None):
 113         """Creates and returns a grid read from a list of lists."""
 114
 115         if not box_height:
 116             box_height, box_width = cls._infer_box_size(len(rows))
 117         elif not box_width:
 118             box_width = box_height
 119
 120         self = cls(box_width=box_width, box_height=box_height)
 121
 122         for row in xrange(self.size):
 123             for col in xrange(self.size):
 124                 value = rows[row][col]
 125                 if not value:
 126                     continue
 127                 self.cell(row, col).set(value - 1, normalize=False)
 128
 129         return self
 130
 131     @classmethod
 132     def from_string(cls, grid, box_height=None, box_width=None):
 133         # XXX sanity check dimensions
 134         """Creates and returns a grid from a string of symbols.
 135
 136         Symbols are the digits 1 to 9 followed by the letters of the alphabet.
 137         Zeroes and periods are assumed to be empty cells.  All other characters
 138         are ignored.
 139
 140         Since whitespace is ignored, the string could be all in one line or
 141         laid out visually in a square, one row per line."""
 142
 143         # Collapse the string down to just characters we want
 144         grid = grid.lower()
 145         grid = re.sub('\\.', '0', grid)
 146         grid = re.sub('[^0-9a-z]', '', grid)
 147
 148         # Figure out the length of one side/box
 149         size = int(sqrt(len(grid)))
 150         if size ** 2 != len(grid):
 151             raise GridSizeError("Provided string does not form a square")
 152
 153         # Set height/width..
 154         if not box_height:
 155             box_height, box_width = cls._infer_box_size(size)
 156         elif not box_width:
 157             box_width = box_height
 158
 159         self = cls(box_width=box_width, box_height=box_height)
 160
 161         for row in xrange(self.size):
 162             for col in xrange(self.size):
 163                 ch = grid[ self._cellidx(row, col) ]
 164                 if ch == '0':
 165                     continue
 166                 self.cell(row, col).set(symbols.index(ch), normalize=False)
 167
 168         return self
 169
 170     ### Constraints
 171
 172     def add_constraint(self, constraint):
 173         self._constraints.append(constraint)
 174         for cell in constraint.cells:
 175             cell.add_constraint(constraint)
 176
 177     def add_default_constraints(self):
 178         for i in xrange(self.size):
 179             self.add_constraint(Row(self, i))
 180             self.add_constraint(Column(self, i))
 181             self.add_constraint(Box(self, i))
 182
 183         return
 184
 185     ### Inspectors
 186
 187     def cell(self, row, column):
 188         return self._cells[self._cellidx(row, column)]
 189
 190     ### Solving
 191
 192     def normalize_cells(self):
 193         """Normalizes every cell in the grid.
 194
 195         Returns the number of cell changes."""
 196
 197         cell_changes = 0
 198         for cell in self._cells:
 199             cell_changes += cell.normalize()
 200
 201         return cell_changes
 202
 203     def resolve_uniques(self):
 204         """Searches each group of cells for a value that can only appear in a
 205         single cell.
 206
 207         Returns the number of cell changes."""
 208
 209         cell_changes = 0
 210         for constraint in self.constraints:
 211             cell_changes += constraint.resolve_uniques()
 212
 213         return cell_changes
 214
 215     _solution_steps = [
 216         normalize_cells,
 217         resolve_uniques,
 218     ]
 219
 220     def solve(self):
 221         """Attempts to solve the grid by running through various methods of
 222         elimination one at a time, from simplest to most complex."""
 223
 224         while True:
 225             for method in self._solution_steps:
 226                 cell_changes = method(self)
 227
 228                 # If we changed something, start over with simple steps again
 229                 if cell_changes:
 230                     break
 231
 232             # If we didn't do anything this round, we're done
 233             if not cell_changes:
 234                 break