X-Git-Url: http://git.veekun.com/pseudoku.git/blobdiff_plain/a49a2fc56c430884ad137031168836c9a3c6bfe9..6c46caf7943b1beaadf32f5bbd78b1aee647b825:/pseudoku/grid/__init__.py diff --git a/pseudoku/grid/__init__.py b/pseudoku/grid/__init__.py index e91a1bd..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,86 +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_constraints(self): - return self._constraints - constraints = property(_get_constraints) - - def __init__(self, grid, row, column): - self._grid = proxy(grid) - self._row = row - self._col = column - self._values = range(self._grid.size) - self._constraints = [] - self._normalized = False - - def add_constraint(self, constraint): - self._constraints.append(constraint) - - 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 constraint in self.constraints: - for cell in constraint.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.""" @@ -106,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): @@ -144,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_constraints(self): - return self._constraints - constraints = property(_get_constraints) + def _is_filled(self): + for cell in self._cells: + if cell.value == None: + return False + return True + filled = property(_is_filled) ### Constructors @@ -170,9 +99,9 @@ class Grid(object): self._box_width = box_width self._size = box_height * box_width - 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) @@ -190,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 @@ -229,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 @@ -246,7 +175,7 @@ class Grid(object): cell.add_constraint(constraint) def add_default_constraints(self): - for i in xrange(self._size): + for i in xrange(self.size): self.add_constraint(Row(self, i)) self.add_constraint(Column(self, i)) self.add_constraint(Box(self, i)) @@ -258,35 +187,48 @@ class Grid(object): 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.constraints: - 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