pseudoku.py

   1 from weakref import proxy
   2
   3 symbols = [str(x + 1) for x in range(9)] + [chr(x + 97) for x in xrange(26)]
   4
   5
   6 class CellGroup(object):
   7     """Represents any group of cells in a grid."""
   8
   9     ### Accessors
  10
  11     cells = []
  12
  13     ### Methods
  14     # XXX inherited __init__
  15
  16     def find_value(self, value):
  17         """Returns the cells that can be a specific value."""
  18         possible_cells = []
  19         for cell in self.cells:
  20             if value in cell._values:
  21                 possible_cells.append(cell)
  22
  23         if len(possible_cells) == 0:
  24             raise Exception  # XXX
  25
  26         return possible_cells
  27
  28     def resolve_uniques(self):
  29         for value in xrange(self._grid._size):
  30             # XXX cache values that are taken care of
  31             possible_cells = self.find_value(value)
  32
  33             if len(possible_cells) > 1:
  34                 # Not unique
  35                 continue
  36
  37             target_cell = possible_cells[0]
  38             if target_cell.solved:
  39                 # Already seen this
  40                 # XXX this is what cache is for
  41                 continue
  42
  43             # Only cell in the group that can be value
  44             target_cell.set(value)
  45
  46
  47 class Box(CellGroup):
  48     def _get_box_row(self):
  49         return self._pos // self._grid._box_width
  50     box_row = property(_get_box_row)
  51
  52     def _get_box_column(self):
  53         return self._pos % self._grid._box_height
  54     box_column = property(_get_box_column)
  55
  56     def _get_cells(self):
  57         # XXX generator + docstring
  58         cells = []
  59         for row in xrange(self._grid._box_height):
  60             for col in xrange(self._grid._box_width):
  61                 cell_row = row + self.box_row * self._grid._box_height
  62                 cell_col = col + self.box_column * self._grid._box_width
  63                 cells.append(self._grid.cell(cell_row, cell_col))
  64         return cells
  65     cells = property(_get_cells)
  66
  67     def __init__(self, grid, position):
  68         self._grid = proxy(grid)
  69         self._pos = position
  70
  71
  72 class Row(CellGroup):
  73     def _get_cells(self):
  74         # XXX generator + docstring
  75         cells = []
  76         for col in xrange(self._grid._size):
  77             cells.append(self._grid.cell(self._pos, col))
  78         return cells
  79     cells = property(_get_cells)
  80
  81     def __init__(self, grid, position):
  82         self._grid = proxy(grid)
  83         self._pos = position
  84
  85
  86 class Column(CellGroup):
  87     def _get_cells(self):
  88         # XXX generator + docstring
  89         cells = []
  90         for row in xrange(self._grid._size):
  91             cells.append(self._grid.cell(row, self._pos))
  92         return cells
  93     cells = property(_get_cells)
  94
  95     def __init__(self, grid, position):
  96         self._grid = proxy(grid)
  97         self._pos = position
  98
  99
 100 class Cell(object):
 101     """Represents a single cell/value within a sudoku grid."""
 102
 103     ### Accessors
 104
 105     def _get_solved(self):
 106         """True iff this cell has been solved."""
 107         return len(self._values) == 1
 108     solved = property(_get_solved)
 109
 110     def _get_value(self):
 111         """Returns this cell's value, if it has one known."""
 112         if self.solved:
 113             return self._values[0]
 114         return None
 115     value = property(_get_value)
 116
 117     def _get_row(self):
 118         """Returns the Row object associated with this cell."""
 119         return self._grid._rows[self._row]
 120     row = property(_get_row)
 121
 122     def _get_column(self):
 123         """Returns the Column object associated with this cell."""
 124         return self._grid._columns[self._col]
 125     column = property(_get_column)
 126
 127     def _get_box(self):
 128         """Returns the Box object associated with this cell."""
 129         # Some actual math required here!
 130         # Row 0..2 -> box 0..2
 131         # Col 0..2 -> box 0, 3, 6 (box col 0)
 132         box_row = self._row // self._grid._box_height
 133         box_col = self._col // self._grid._box_width
 134         box_idx = box_row * self._grid._box_height + box_col
 135         return self._grid._boxes[box_idx]
 136     box = property(_get_box)
 137
 138     def __init__(self, grid, row, column):
 139         self._grid = proxy(grid)
 140         self._row = row
 141         self._col = column
 142         self._values = range(self._grid.size)
 143         self._normalized = False
 144
 145     def set_naively(self, value):
 146         """Sets the value of this cell, WITHOUT eliminating the value from
 147         every other cell in its row/column/box.
 148         """
 149
 150         self._values = [value]
 151
 152     def set(self, value):
 153         """Sets the value of this cell and adjusts the grid accordingly."""
 154         self.set_naively(value)
 155         self._normalized = False
 156         self.normalize()
 157
 158
 159
 160     def normalize(self):
 161         """Checks to see if this cell has only one possible value left.  If
 162         so, sets that as its value and eliminates it from every related cell.
 163         This method is exhaustive; that repeated calls should have no effect.
 164         """
 165
 166         if self._normalized:
 167             # Already done
 168             return
 169
 170         # Set this now just in case of infinite looping
 171         self._normalized = True
 172
 173         if not self.solved:
 174             # Don't know the value yet
 175             return
 176
 177         # Elimination time
 178         for group_type in 'row', 'column', 'box':
 179             group = getattr(self, group_type)
 180             for cell in group.cells:
 181                 if cell == self:
 182                     continue
 183                 cell.eliminate(self.value)
 184
 185
 186     def eliminate(self, value):
 187         """Eliminates the given value as a possibility for this cell."""
 188         if value in self._values:
 189             self._values.remove(value)
 190
 191             if len(self._values) == 0:
 192                 # XXX give me a real exception here
 193                 raise Exception
 194
 195             self._normalized = False
 196             self.normalize()
 197
 198
 199     def __str__(self):
 200         """Stringification for pretty-printing."""
 201         if self.value != None:
 202             return symbols[self.value]
 203
 204         return '.'
 205
 206
 207
 208
 209 class Grid(object):
 210     """Represents a Sudoku grid."""
 211
 212     ### Utilities
 213
 214     def _cellidx(self, row, col):
 215         """Hashes a row and column into a flat array index."""
 216         return row * self._size + col
 217
 218     ### Accessors
 219
 220     def _get_box_height(self):
 221         return self._box_height
 222     box_height = property(_get_box_height)
 223
 224     def _get_box_width(self):
 225         return self._box_width
 226     box_width = property(_get_box_width)
 227
 228     def _get_size(self):
 229         return self._size
 230     size = property(_get_size)
 231
 232     def _get_cell_groups(self):
 233         return self._rows + self._columns + self._boxes
 234     cell_groups = property(_get_cell_groups)
 235
 236     ### Methods
 237
 238     def __init__(self, box_height=3, box_width=None):
 239         if not box_width:
 240             box_width = box_height
 241
 242         self._box_height = box_height
 243         self._box_width = box_width
 244         self._size = box_height * box_width
 245
 246         self._rows = [Row(self, i) for i in xrange(self._size)]
 247         self._columns = [Column(self, i) for i in xrange(self._size)]
 248         self._boxes = [Box(self, i) for i in xrange(self._size)]
 249
 250         self._cells = range(self._size ** 2)
 251         for row in xrange(self._size):
 252             for col in xrange(self._size):
 253                 self._cells[self._cellidx(row, col)] \
 254                     = Cell(self, row, col)
 255
 256     def from_lists(self, *rows):
 257         for row in xrange(self._size):
 258             for col in xrange(self._size):
 259                 value = rows[row][col]
 260                 if not value:
 261                     continue
 262                 self.cell(row, col).set_naively(value - 1)
 263
 264
 265     def cell(self, row, column):
 266         return self._cells[self._cellidx(row, column)]
 267
 268
 269     ### Solving
 270
 271     def check(self):
 272         """Returns True iff the grid is solved.  Raises an exception if an
 273         integrity problem is found, such as a value appearing twice in a row.
 274         """
 275         # TODO
 276         return None
 277
 278     def solve(self):
 279         """Attempts to solve the grid."""
 280         # XXX track how many cells are changed and repeat as appropriate
 281
 282         # Step 0: Normalize cells, i.e. find any that can only be one value
 283         self.normalize_cells()
 284
 285         # Step 1: Find values that can only go in one cell in a group
 286         for group in self.cell_groups:
 287             group.resolve_uniques()
 288
 289
 290     def normalize_cells(self):
 291         """Normalizes every cell in the grid."""
 292         for cell in self._cells:
 293             cell.normalize()
 294
 295
 296     def __str__(self):
 297         """Pretty-printing."""
 298         divider = '+'
 299         for box in xrange(self._box_height):
 300             for col in xrange(self._box_width):
 301                 divider += '-'
 302             divider += '+'
 303
 304         res = ''
 305         for row in xrange(self._size):
 306             if row % self._box_height == 0:
 307                 res += divider
 308                 res += "\n"
 309
 310             for col in xrange(self._size):
 311                 if col % self._box_width == 0:
 312                     res += '|'
 313                 res += str(self.cell(row, col))
 314
 315             res += '|'
 316             res += "\n"
 317
 318         res += divider
 319         res += "\n"
 320
 321         return res
 322
 323
 324
 325 grid = Grid(3, 3)
 326 grid.from_lists(
 327     [ 0, 0, 0, 6, 9, 0, 0, 0, 0 ],
 328     [ 9, 0, 5, 0, 0, 8, 7, 6, 0 ],
 329     [ 0, 0, 4, 0, 0, 1, 0, 2, 0 ],
 330     [ 6, 0, 0, 0, 5, 0, 0, 0, 3 ],
 331     [ 3, 8, 0, 0, 0, 0, 0, 4, 9 ],
 332     [ 7, 0, 0, 0, 3, 0, 0, 0, 2 ],
 333     [ 0, 7, 0, 9, 0, 0, 3, 0, 0 ],
 334     [ 0, 2, 3, 1, 0, 0, 4, 0, 8 ],
 335     [ 0, 0, 0, 0, 8, 3, 0, 0, 0 ],
 336 )
 337
 338 print grid
 339
 340 grid.solve()
 341
 342 print grid