pseudoku.py

   1 from __future__ import division
   2
   3 from math import sqrt
   4 import re
   5 from weakref import proxy
   6
   7 symbols = [str(x + 1) for x in range(9)] + [chr(x + 97) for x in xrange(26)]
   8
   9
  10 class GridSizeError(Exception):
  11     pass
  12
  13 class CellGroup(object):
  14     """Represents any group of cells in a grid."""
  15
  16     ### Accessors
  17
  18     cells = []
  19
  20     ### Methods
  21     # XXX inherited __init__
  22
  23     def find_value(self, value):
  24         """Returns the cells that can be a specific value."""
  25         possible_cells = []
  26         for cell in self.cells:
  27             if value in cell._values:
  28                 possible_cells.append(cell)
  29
  30         if len(possible_cells) == 0:
  31             raise Exception  # XXX
  32
  33         return possible_cells
  34
  35     def resolve_uniques(self):
  36         for value in xrange(self._grid._size):
  37             # XXX cache values that are taken care of
  38             possible_cells = self.find_value(value)
  39
  40             if len(possible_cells) > 1:
  41                 # Not unique
  42                 continue
  43
  44             target_cell = possible_cells[0]
  45             if target_cell.solved:
  46                 # Already seen this
  47                 # XXX this is what cache is for
  48                 continue
  49
  50             # Only cell in the group that can be value
  51             target_cell.set(value)
  52
  53
  54 class Box(CellGroup):
  55     def _get_box_row(self):
  56         return self._pos // self._grid._box_width
  57     box_row = property(_get_box_row)
  58
  59     def _get_box_column(self):
  60         return self._pos % self._grid._box_height
  61     box_column = property(_get_box_column)
  62
  63     def _get_cells(self):
  64         # XXX generator + docstring
  65         cells = []
  66         for row in xrange(self._grid._box_height):
  67             for col in xrange(self._grid._box_width):
  68                 cell_row = row + self.box_row * self._grid._box_height
  69                 cell_col = col + self.box_column * self._grid._box_width
  70                 cells.append(self._grid.cell(cell_row, cell_col))
  71         return cells
  72     cells = property(_get_cells)
  73
  74     def __init__(self, grid, position):
  75         self._grid = proxy(grid)
  76         self._pos = position
  77
  78
  79 class Row(CellGroup):
  80     def _get_cells(self):
  81         # XXX generator + docstring
  82         cells = []
  83         for col in xrange(self._grid._size):
  84             cells.append(self._grid.cell(self._pos, col))
  85         return cells
  86     cells = property(_get_cells)
  87
  88     def __init__(self, grid, position):
  89         self._grid = proxy(grid)
  90         self._pos = position
  91
  92
  93 class Column(CellGroup):
  94     def _get_cells(self):
  95         # XXX generator + docstring
  96         cells = []
  97         for row in xrange(self._grid._size):
  98             cells.append(self._grid.cell(row, self._pos))
  99         return cells
 100     cells = property(_get_cells)
 101
 102     def __init__(self, grid, position):
 103         self._grid = proxy(grid)
 104         self._pos = position
 105
 106
 107 class Cell(object):
 108     """Represents a single cell/value within a sudoku grid."""
 109
 110     ### Accessors
 111
 112     def _get_solved(self):
 113         """True iff this cell has been solved."""
 114         return len(self._values) == 1
 115     solved = property(_get_solved)
 116
 117     def _get_value(self):
 118         """Returns this cell's value, if it has one known."""
 119         if self.solved:
 120             return self._values[0]
 121         return None
 122     value = property(_get_value)
 123
 124     def _get_row(self):
 125         """Returns the Row object associated with this cell."""
 126         return self._grid._rows[self._row]
 127     row = property(_get_row)
 128
 129     def _get_column(self):
 130         """Returns the Column object associated with this cell."""
 131         return self._grid._columns[self._col]
 132     column = property(_get_column)
 133
 134     def _get_box(self):
 135         """Returns the Box object associated with this cell."""
 136         # Some actual math required here!
 137         # Row 0..2 -> box 0..2
 138         # Col 0..2 -> box 0, 3, 6 (box col 0)
 139         box_row = self._row // self._grid._box_height
 140         box_col = self._col // self._grid._box_width
 141         box_idx = box_row * self._grid._box_height + box_col
 142         return self._grid._boxes[box_idx]
 143     box = property(_get_box)
 144
 145     def __init__(self, grid, row, column):
 146         self._grid = proxy(grid)
 147         self._row = row
 148         self._col = column
 149         self._values = range(self._grid.size)
 150         self._normalized = False
 151
 152     def set_naively(self, value):
 153         """Sets the value of this cell, WITHOUT eliminating the value from
 154         every other cell in its row/column/box.
 155         """
 156
 157         self._values = [value]
 158
 159     def set(self, value):
 160         """Sets the value of this cell and adjusts the grid accordingly."""
 161         self.set_naively(value)
 162         self._normalized = False
 163         self.normalize()
 164
 165
 166
 167     def normalize(self):
 168         """Checks to see if this cell has only one possible value left.  If
 169         so, sets that as its value and eliminates it from every related cell.
 170         This method is exhaustive; that repeated calls should have no effect.
 171         """
 172
 173         if self._normalized:
 174             # Already done
 175             return
 176
 177         # Set this now just in case of infinite looping
 178         self._normalized = True
 179
 180         if not self.solved:
 181             # Don't know the value yet
 182             return
 183
 184         # Elimination time
 185         for group_type in 'row', 'column', 'box':
 186             group = getattr(self, group_type)
 187             for cell in group.cells:
 188                 if cell == self:
 189                     continue
 190                 cell.eliminate(self.value)
 191
 192
 193     def eliminate(self, value):
 194         """Eliminates the given value as a possibility for this cell."""
 195         if value in self._values:
 196             self._values.remove(value)
 197
 198             if len(self._values) == 0:
 199                 # XXX give me a real exception here
 200                 raise Exception
 201
 202             self._normalized = False
 203             self.normalize()
 204
 205
 206     def __str__(self):
 207         """Stringification for pretty-printing."""
 208         if self.value != None:
 209             return symbols[self.value]
 210
 211         return '.'
 212
 213
 214
 215
 216 class Grid(object):
 217     """Represents a Sudoku grid."""
 218
 219     ### Utilities
 220
 221     def _cellidx(self, row, col):
 222         """Hashes a row and column into a flat array index."""
 223         return row * self._size + col
 224
 225     @classmethod
 226     def _infer_box_size(cls, dimension):
 227         """Attempts to infer the size of a box, given some dimension of the
 228         entire grid, i.e. the number of cells per box/row/column.
 229
 230         Returns a tuple of height, width."""
 231
 232         # Most obvious: probably n * n.
 233         root = int(sqrt(dimension))
 234         if root ** 2 == dimension:
 235             return root, root
 236
 237         # Otherwise, probably n * (n - 1) or n * (n - 2).
 238         # These puzzles generally have the wide side (n) as the width.
 239         # This is of course entirely unreliable, but better than nothing..
 240         #   n^2 - (1|2)n - dimension = 0
 241         #   Determinant is (1|2)^2 + 4 * dimension and has to be square
 242         for difference in 1, 2:
 243             determinant = difference ** 2 + 4 * dimension
 244             root = int(sqrt(determinant))
 245             if root ** 2 != determinant:
 246                 continue
 247
 248             n = (-difference + root) / 2
 249             if n != int(n):
 250                 continue
 251
 252             # Success!
 253             return n - difference, n
 254
 255         # Okay, I don't have a clue.
 256         raise GridSizeError("Can't infer box height and width for grid size "
 257                             "%d; please specify them manually" % dimension)
 258
 259     ### Accessors
 260
 261     def _get_box_height(self):
 262         return self._box_height
 263     box_height = property(_get_box_height)
 264
 265     def _get_box_width(self):
 266         return self._box_width
 267     box_width = property(_get_box_width)
 268
 269     def _get_size(self):
 270         return self._size
 271     size = property(_get_size)
 272
 273     def _get_cell_groups(self):
 274         return self._rows + self._columns + self._boxes
 275     cell_groups = property(_get_cell_groups)
 276
 277     ### Constructors
 278
 279     def __init__(self, box_height=3, box_width=None):
 280         if not box_width:
 281             box_width = box_height
 282
 283         self._box_height = box_height
 284         self._box_width = box_width
 285         self._size = box_height * box_width
 286
 287         self._rows = [Row(self, i) for i in xrange(self._size)]
 288         self._columns = [Column(self, i) for i in xrange(self._size)]
 289         self._boxes = [Box(self, i) for i in xrange(self._size)]
 290
 291         self._cells = range(self._size ** 2)
 292         for row in xrange(self._size):
 293             for col in xrange(self._size):
 294                 self._cells[self._cellidx(row, col)] \
 295                     = Cell(self, row, col)
 296
 297     @classmethod
 298     def from_matrix(cls, rows, box_height=None, box_width=None):
 299         """Creates and returns a grid read from a list of lists."""
 300
 301         if not box_height:
 302             box_height, box_width = cls._infer_box_size(len(rows))
 303         elif not box_width:
 304             box_width = box_height
 305
 306         self = cls(box_width=box_width, box_height=box_height)
 307
 308         for row in xrange(self._size):
 309             for col in xrange(self._size):
 310                 value = rows[row][col]
 311                 if not value:
 312                     continue
 313                 self.cell(row, col).set_naively(value - 1)
 314
 315         return self
 316
 317     @classmethod
 318     def from_string(cls, grid, box_height=None, box_width=None):
 319         # XXX sanity check dimensions
 320         """Creates and returns a grid from a string of symbols.
 321
 322         Symbols are the digits 1 to 9 followed by the letters of the alphabet.
 323         Zeroes and periods are assumed to be empty cells.  All other characters
 324         are ignored.
 325
 326         Since whitespace is ignored, the string could be all in one line or
 327         laid out visually in a square, one row per line."""
 328
 329         # Collapse the string down to just characters we want
 330         grid = grid.lower()
 331         grid = re.sub('\\.', '0', grid)
 332         grid = re.sub('[^0-9a-z]', '', grid)
 333
 334         # Figure out the length of one side/box
 335         size = int(sqrt(len(grid)))
 336         if size ** 2 != len(grid):
 337             # XXX
 338             raise GridSizeError("Provided string does not form a square")
 339
 340         # Set height/width..
 341         if not box_height:
 342             box_height, box_width = cls._infer_box_size(size)
 343         elif not box_width:
 344             box_width = box_height
 345
 346         self = cls(box_width=box_width, box_height=box_height)
 347
 348         for row in xrange(self._size):
 349             for col in xrange(self._size):
 350                 ch = grid[ self._cellidx(row, col) ]
 351                 if ch == '0':
 352                     continue
 353                 self.cell(row, col).set_naively(symbols.index(ch))
 354
 355         return self
 356
 357     ### Methods
 358
 359     def cell(self, row, column):
 360         return self._cells[self._cellidx(row, column)]
 361
 362
 363     ### Solving
 364
 365     def check(self):
 366         """Returns True iff the grid is solved.  Raises an exception if an
 367         integrity problem is found, such as a value appearing twice in a row.
 368         """
 369         # TODO
 370         return None
 371
 372     def solve(self):
 373         """Attempts to solve the grid."""
 374         # XXX track how many cells are changed and repeat as appropriate
 375
 376         # Step 0: Normalize cells, i.e. find any that can only be one value
 377         self.normalize_cells()
 378
 379         # Step 1: Find values that can only go in one cell in a group
 380         for group in self.cell_groups:
 381             group.resolve_uniques()
 382
 383
 384     def normalize_cells(self):
 385         """Normalizes every cell in the grid."""
 386         for cell in self._cells:
 387             cell.normalize()
 388
 389
 390     def __str__(self):
 391         """Pretty-printing."""
 392         divider = '+'
 393         for box in xrange(self._box_height):
 394             for col in xrange(self._box_width):
 395                 divider += '-'
 396             divider += '+'
 397
 398         res = ''
 399         for row in xrange(self._size):
 400             if row % self._box_height == 0:
 401                 res += divider
 402                 res += "\n"
 403
 404             for col in xrange(self._size):
 405                 if col % self._box_width == 0:
 406                     res += '|'
 407                 res += str(self.cell(row, col))
 408
 409             res += '|'
 410             res += "\n"
 411
 412         res += divider
 413         res += "\n"
 414
 415         return res
 416
 417
 418 grid = Grid.from_string("..... ..... ..... ..... ....")
 419 grid = Grid.from_string("""
 420     ...69....
 421     9.5..876.
 422     ..4..1.2.
 423     6...5...3
 424     38.....49
 425     7...3...2
 426     .7.9..3..
 427     .231..4.8
 428     ....83...
 429 """)
 430
 431 print grid
 432
 433 grid.solve()
 434
 435 print grid