X-Git-Url: http://git.veekun.com/pseudoku.git/blobdiff_plain/f66d11f5304e3c2c3853d69acfc864bcb8301903..30f8ff60eb4bd6d8b6f4467ba0b7bbe29a8a92ee:/pseudoku/grid/__init__.py diff --git a/pseudoku/grid/__init__.py b/pseudoku/grid/__init__.py index a62f18f..83e358f 100644 --- a/pseudoku/grid/__init__.py +++ b/pseudoku/grid/__init__.py @@ -3,9 +3,9 @@ from __future__ import division from math import sqrt from operator import attrgetter import re -from weakref import ref -from cellgroup import CellConstraint, 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)] @@ -19,85 +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) - - grid = property(lambda self: self._grid()) - constraints = property(attrgetter('_constraints')) - - def __init__(self, grid, row, column): - self._grid = ref(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.""" @@ -144,7 +65,7 @@ class Grid(object): ### Accessors - def get_constraints(self, constraint_class=CellConstraint): + def get_constraints(self, constraint_class=Constraint): """Returns constraints of a certain type. Returns all of them by default. """ @@ -153,11 +74,21 @@ class Grid(object): return filter(condition, self._constraints) rows = property(lambda self: self.get_constraints(Row)) + columns = property(lambda self: self.get_constraints(Column)) + boxes = property(lambda self: self.get_constraints(Box)) + box_height = property(attrgetter('_box_height')) box_width = property(attrgetter('_box_width')) size = property(attrgetter('_size')) constraints = property(attrgetter('_constraints')) + def _is_filled(self): + for cell in self._cells: + if cell.value == None: + return False + return True + filled = property(_is_filled) + ### Constructors def __init__(self, box_height=3, box_width=None): @@ -256,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 + + _solution_steps = [ + normalize_cells, + resolve_uniques, + ] - # Step 0: Normalize cells, i.e. find any that can only be one value - self.normalize_cells() + def solve(self): + """Attempts to solve the grid by running through various methods of + elimination one at a time, from simplest to most complex.""" - # Step 1: Find values that can only go in one cell in a group - for group in self.constraints: - group.resolve_uniques() + while True: + for method in self._solution_steps: + cell_changes = method(self) + # If we changed something, start over with simple steps again + if cell_changes: + break - def normalize_cells(self): - """Normalizes every cell in the grid.""" - for cell in self._cells: - cell.normalize() + # If we didn't do anything this round, we're done + if not cell_changes: + break