X-Git-Url: http://git.veekun.com/pseudoku.git/blobdiff_plain/ef420dd690bb7803272ebc08c8e7a6e132dd0061..5f305518adfcb89e940eac9073a337054d8c695c:/pseudoku/grid/__init__.py diff --git a/pseudoku/grid/__init__.py b/pseudoku/grid/__init__.py index 2f77aaf..caf135d 100644 --- a/pseudoku/grid/__init__.py +++ b/pseudoku/grid/__init__.py @@ -1,10 +1,11 @@ from __future__ import division from math import sqrt +from operator import attrgetter import re -from weakref import proxy -from cellgroup import Row, Column, Box +from cell import Cell +from constraints import Constraint, Row, Column, Box symbols = [str(x + 1) for x in range(9)] + [chr(x + 97) for x in xrange(26)] @@ -18,112 +19,6 @@ class GridIntegrityError(Exception): """ pass -class Cell(object): - """Represents a single cell/value within a sudoku grid.""" - - ### Accessors - - def _get_solved(self): - """True iff this cell has been solved.""" - return len(self._values) == 1 - solved = property(_get_solved) - - def _get_value(self): - """Returns this cell's value, if it has one known.""" - if self.solved: - return self._values[0] - return None - value = property(_get_value) - - def _get_row(self): - """Returns the Row object associated with this cell.""" - return self._grid._rows[self._row] - row = property(_get_row) - - def _get_column(self): - """Returns the Column object associated with this cell.""" - return self._grid._columns[self._col] - column = property(_get_column) - - def _get_box(self): - """Returns the Box object associated with this cell.""" - # Some actual math required here! - # Row 0..2 -> box 0..2 - # Col 0..2 -> box 0, 3, 6 (box col 0) - box_row = self._row // self._grid._box_height - box_col = self._col // self._grid._box_width - box_idx = box_row * self._grid._box_height + box_col - return self._grid._boxes[box_idx] - box = property(_get_box) - - def __init__(self, grid, row, column): - self._grid = proxy(grid) - self._row = row - self._col = column - self._values = range(self._grid.size) - self._normalized = False - - def set_naively(self, value): - """Sets the value of this cell, WITHOUT eliminating the value from - every other cell in its row/column/box. - """ - - self._values = [value] - - def set(self, value): - """Sets the value of this cell and adjusts the grid accordingly.""" - self.set_naively(value) - self._normalized = False - self.normalize() - - - - def normalize(self): - """Checks to see if this cell has only one possible value left. If - so, sets that as its value and eliminates it from every related cell. - This method is exhaustive; that repeated calls should have no effect. - """ - - if self._normalized: - # Already done - return - - # Set this now just in case of infinite looping - self._normalized = True - - if not self.solved: - # Don't know the value yet - return - - # Elimination time - for group_type in 'row', 'column', 'box': - group = getattr(self, group_type) - for cell in group.cells: - if cell == self: - continue - cell.eliminate(self.value) - - - def eliminate(self, value): - """Eliminates the given value as a possibility for this cell.""" - if value in self._values: - self._values.remove(value) - - if len(self._values) == 0: - # XXX give me a real exception here - raise Exception - - self._normalized = False - self.normalize() - - - def __str__(self): - """Stringification for pretty-printing.""" - if self.value != None: - return symbols[self.value] - - return '.' - class Grid(object): """Represents a Sudoku grid.""" @@ -132,7 +27,7 @@ class Grid(object): def _cellidx(self, row, col): """Hashes a row and column into a flat array index.""" - return row * self._size + col + return row * self.size + col @classmethod def _infer_box_size(cls, dimension): @@ -170,21 +65,22 @@ class Grid(object): ### Accessors - def _get_box_height(self): - return self._box_height - box_height = property(_get_box_height) + def get_constraints(self, constraint_class=Constraint): + """Returns constraints of a certain type. Returns all of them by + default. + """ - def _get_box_width(self): - return self._box_width - box_width = property(_get_box_width) + condition = lambda constraint: isinstance(constraint, constraint_class) + return filter(condition, self._constraints) - def _get_size(self): - return self._size - size = property(_get_size) + rows = property(lambda self: self.get_constraints(Row)) + columns = property(lambda self: self.get_constraints(Column)) + boxes = property(lambda self: self.get_constraints(Box)) - def _get_cell_groups(self): - return self._rows + self._columns + self._boxes - cell_groups = property(_get_cell_groups) + box_height = property(attrgetter('_box_height')) + box_width = property(attrgetter('_box_width')) + size = property(attrgetter('_size')) + constraints = property(attrgetter('_constraints')) ### Constructors @@ -196,16 +92,15 @@ class Grid(object): self._box_width = box_width self._size = box_height * box_width - self._rows = [Row(self, i) for i in xrange(self._size)] - self._columns = [Column(self, i) for i in xrange(self._size)] - self._boxes = [Box(self, i) for i in xrange(self._size)] - - self._cells = range(self._size ** 2) - for row in xrange(self._size): - for col in xrange(self._size): + self._cells = range(self.size ** 2) + for row in xrange(self.size): + for col in xrange(self.size): self._cells[self._cellidx(row, col)] \ = Cell(self, row, col) + self._constraints = [] + self.add_default_constraints() + @classmethod def from_matrix(cls, rows, box_height=None, box_width=None): """Creates and returns a grid read from a list of lists.""" @@ -217,12 +112,12 @@ class Grid(object): self = cls(box_width=box_width, box_height=box_height) - for row in xrange(self._size): - for col in xrange(self._size): + for row in xrange(self.size): + for col in xrange(self.size): value = rows[row][col] if not value: continue - self.cell(row, col).set_naively(value - 1) + self.cell(row, col).set(value - 1, normalize=False) return self @@ -256,15 +151,30 @@ class Grid(object): self = cls(box_width=box_width, box_height=box_height) - for row in xrange(self._size): - for col in xrange(self._size): + for row in xrange(self.size): + for col in xrange(self.size): ch = grid[ self._cellidx(row, col) ] if ch == '0': continue - self.cell(row, col).set_naively(symbols.index(ch)) + self.cell(row, col).set(symbols.index(ch), normalize=False) return self + ### Constraints + + def add_constraint(self, constraint): + self._constraints.append(constraint) + for cell in constraint.cells: + cell.add_constraint(constraint) + + def add_default_constraints(self): + for i in xrange(self.size): + self.add_constraint(Row(self, i)) + self.add_constraint(Column(self, i)) + self.add_constraint(Box(self, i)) + + return + ### Inspectors def cell(self, row, column): @@ -286,47 +196,51 @@ class Grid(object): return None - def solve(self): - """Attempts to solve the grid.""" - # XXX track how many cells are changed and repeat as appropriate + def normalize_cells(self): + """Normalizes every cell in the grid. + + Returns the number of cell changes.""" - # Step 0: Normalize cells, i.e. find any that can only be one value - self.normalize_cells() + cell_changes = 0 - # Step 1: Find values that can only go in one cell in a group - for group in self.cell_groups: - group.resolve_uniques() + for cell in self._cells: + cell_changes += cell.normalize() + return cell_changes - def normalize_cells(self): - """Normalizes every cell in the grid.""" - for cell in self._cells: - cell.normalize() + def resolve_uniques(self): + """Searches each group of cells for a value that can only appear in a + single cell. + + Returns the number of cell changes.""" + + cell_changes = 0 + + for constraint in self.constraints: + cell_changes += constraint.resolve_uniques() + return cell_changes - def __str__(self): - """Pretty-printing.""" - divider = '+' - for box in xrange(self._box_height): - for col in xrange(self._box_width): - divider += '-' - divider += '+' + _solution_steps = [ + normalize_cells, + resolve_uniques, + ] - res = '' - for row in xrange(self._size): - if row % self._box_height == 0: - res += divider - res += "\n" + def solve(self): + """Attempts to solve the grid by running through various methods of + elimination one at a time, from simplest to most complex.""" + # XXX track how many cells are changed and repeat as appropriate - for col in xrange(self._size): - if col % self._box_width == 0: - res += '|' - res += str(self.cell(row, col)) + while not self.is_filled(): + cell_changes = 0 - res += '|' - res += "\n" + for method in self._solution_steps: + cell_changes += method(self) - res += divider - res += "\n" + # If we changed something, start over with simple steps again + if x != 0: + break - return res + # If we didn't do anything this round, we're stuck + if cell_changes == 0: + break