X-Git-Url: http://git.veekun.com/pseudoku.git/blobdiff_plain/9065fe89fb6f81e7c358100e9127349c27bbb4f4..30f8ff60eb4bd6d8b6f4467ba0b7bbe29a8a92ee:/pseudoku/grid/__init__.py diff --git a/pseudoku/grid/__init__.py b/pseudoku/grid/__init__.py index 94d0833..83e358f 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,100 +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(self, value, normalize=True): - """Sets the value of this cell. If `normalize` is True or omitted, the - grid will be updated accordingly. - """ - self._values = [value] - if normalize: - 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() - class Grid(object): """Represents a Sudoku grid.""" @@ -120,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): @@ -158,21 +65,29 @@ 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. + """ + + condition = lambda constraint: isinstance(constraint, constraint_class) + return filter(condition, self._constraints) - def _get_box_width(self): - return self._box_width - box_width = property(_get_box_width) + 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_size(self): - return self._size - size = property(_get_size) + box_height = property(attrgetter('_box_height')) + box_width = property(attrgetter('_box_width')) + size = property(attrgetter('_size')) + constraints = property(attrgetter('_constraints')) - def _get_cell_groups(self): - return self._rows + self._columns + self._boxes - cell_groups = property(_get_cell_groups) + def _is_filled(self): + for cell in self._cells: + if cell.value == None: + return False + return True + filled = property(_is_filled) ### Constructors @@ -184,16 +99,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.""" @@ -205,8 +119,8 @@ 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 @@ -244,8 +158,8 @@ 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 @@ -253,40 +167,68 @@ class Grid(object): 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): return self._cells[self._cellidx(row, column)] - def is_filled(self): + ### Solving + + def normalize_cells(self): + """Normalizes every cell in the grid. + + Returns the number of cell changes.""" + + cell_changes = 0 for cell in self._cells: - if cell.value == None: - return False - return True + cell_changes += cell.normalize() - ### Solving + return cell_changes - def check(self): - """Returns True iff the grid is solved. Raises an exception if an - integrity problem is found, such as a value appearing twice in a row. - """ - # TODO remove this; name sucks and concept also sucks - return None + 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() - def solve(self): - """Attempts to solve the grid.""" - # XXX track how many cells are changed and repeat as appropriate + return cell_changes - # Step 0: Normalize cells, i.e. find any that can only be one value - self.normalize_cells() + _solution_steps = [ + normalize_cells, + resolve_uniques, + ] - # Step 1: Find values that can only go in one cell in a group - for group in self.cell_groups: - group.resolve_uniques() + def solve(self): + """Attempts to solve the grid by running through various methods of + elimination one at a time, from simplest to most complex.""" + while True: + for method in self._solution_steps: + cell_changes = method(self) - def normalize_cells(self): - """Normalizes every cell in the grid.""" - for cell in self._cells: - cell.normalize() + # If we changed something, start over with simple steps again + if cell_changes: + break + + # If we didn't do anything this round, we're done + if not cell_changes: + break