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     ### Constructors
  86
  87     def __init__(self, box_height=3, box_width=None):
  88         if not box_width:
  89             box_width = box_height
  90
  91         self._box_height = box_height
  92         self._box_width = box_width
  93         self._size = box_height * box_width
  94
  95         self._cells = range(self.size ** 2)
  96         for row in xrange(self.size):
  97             for col in xrange(self.size):
  98                 self._cells[self._cellidx(row, col)] \
  99                     = Cell(self, row, col)
 100
 101         self._constraints = []
 102         self.add_default_constraints()
 103
 104     @classmethod
 105     def from_matrix(cls, rows, box_height=None, box_width=None):
 106         """Creates and returns a grid read from a list of lists."""
 107
 108         if not box_height:
 109             box_height, box_width = cls._infer_box_size(len(rows))
 110         elif not box_width:
 111             box_width = box_height
 112
 113         self = cls(box_width=box_width, box_height=box_height)
 114
 115         for row in xrange(self.size):
 116             for col in xrange(self.size):
 117                 value = rows[row][col]
 118                 if not value:
 119                     continue
 120                 self.cell(row, col).set(value - 1, normalize=False)
 121
 122         return self
 123
 124     @classmethod
 125     def from_string(cls, grid, box_height=None, box_width=None):
 126         # XXX sanity check dimensions
 127         """Creates and returns a grid from a string of symbols.
 128
 129         Symbols are the digits 1 to 9 followed by the letters of the alphabet.
 130         Zeroes and periods are assumed to be empty cells.  All other characters
 131         are ignored.
 132
 133         Since whitespace is ignored, the string could be all in one line or
 134         laid out visually in a square, one row per line."""
 135
 136         # Collapse the string down to just characters we want
 137         grid = grid.lower()
 138         grid = re.sub('\\.', '0', grid)
 139         grid = re.sub('[^0-9a-z]', '', grid)
 140
 141         # Figure out the length of one side/box
 142         size = int(sqrt(len(grid)))
 143         if size ** 2 != len(grid):
 144             raise GridSizeError("Provided string does not form a square")
 145
 146         # Set height/width..
 147         if not box_height:
 148             box_height, box_width = cls._infer_box_size(size)
 149         elif not box_width:
 150             box_width = box_height
 151
 152         self = cls(box_width=box_width, box_height=box_height)
 153
 154         for row in xrange(self.size):
 155             for col in xrange(self.size):
 156                 ch = grid[ self._cellidx(row, col) ]
 157                 if ch == '0':
 158                     continue
 159                 self.cell(row, col).set(symbols.index(ch), normalize=False)
 160
 161         return self
 162
 163     ### Constraints
 164
 165     def add_constraint(self, constraint):
 166         self._constraints.append(constraint)
 167         for cell in constraint.cells:
 168             cell.add_constraint(constraint)
 169
 170     def add_default_constraints(self):
 171         for i in xrange(self.size):
 172             self.add_constraint(Row(self, i))
 173             self.add_constraint(Column(self, i))
 174             self.add_constraint(Box(self, i))
 175
 176         return
 177
 178     ### Inspectors
 179
 180     def cell(self, row, column):
 181         return self._cells[self._cellidx(row, column)]
 182
 183     def is_filled(self):
 184         for cell in self._cells:
 185             if cell.value == None:
 186                 return False
 187         return True
 188
 189     ### Solving
 190
 191     def check(self):
 192         """Returns True iff the grid is solved.  Raises an exception if an
 193         integrity problem is found, such as a value appearing twice in a row.
 194         """
 195         # TODO remove this; name sucks and concept also sucks
 196         return None
 197
 198
 199     def normalize_cells(self):
 200         """Normalizes every cell in the grid.
 201
 202         Returns the number of cell changes."""
 203
 204         cell_changes = 0
 205
 206         for cell in self._cells:
 207             cell_changes += cell.normalize()
 208
 209         return cell_changes
 210
 211     def resolve_uniques(self):
 212         """Searches each group of cells for a value that can only appear in a
 213         single cell.
 214
 215         Returns the number of cell changes."""
 216
 217         cell_changes = 0
 218
 219         for constraint in self.constraints:
 220             cell_changes += constraint.resolve_uniques()
 221
 222         return cell_changes
 223
 224     _solution_steps = [
 225         normalize_cells,
 226         resolve_uniques,
 227     ]
 228
 229     def solve(self):
 230         """Attempts to solve the grid by running through various methods of
 231         elimination one at a time, from simplest to most complex."""
 232         # XXX track how many cells are changed and repeat as appropriate
 233
 234         while not self.is_filled():
 235             cell_changes = 0
 236
 237             for method in self._solution_steps:
 238                 cell_changes += method(self)
 239
 240                 # If we changed something, start over with simple steps again
 241                 if x != 0:
 242                     break
 243
 244             # If we didn't do anything this round, we're stuck
 245             if cell_changes == 0:
 246                 break