From 5f305518adfcb89e940eac9073a337054d8c695c Mon Sep 17 00:00:00 2001 From: Eevee Date: Wed, 7 Jan 2009 09:30:23 -0500 Subject: [PATCH] Improved solving; should now solve all easy puzzles. Grid.solve() now keeps trying its elimination methods until they stop doing anything. Also snuck in Constraint.is_linear, in preparation for solving by row/box interaction. --- pseudoku/__init__.py | 2 +- pseudoku/grid/__init__.py | 52 +++++++++++++++++++++++++++++++++++--------- pseudoku/grid/cell.py | 39 +++++++++++++++++++++------------ pseudoku/grid/constraints.py | 23 +++++++++++++++++++- 4 files changed, 90 insertions(+), 26 deletions(-) diff --git a/pseudoku/__init__.py b/pseudoku/__init__.py index 2fe15f3..c7a803b 100644 --- a/pseudoku/__init__.py +++ b/pseudoku/__init__.py @@ -1,5 +1,5 @@ from grid import Grid -from grid.cellgroup import Diagonal +from grid.constraints import Diagonal import render.text def main(): diff --git a/pseudoku/grid/__init__.py b/pseudoku/grid/__init__.py index 9ba0158..caf135d 100644 --- a/pseudoku/grid/__init__.py +++ b/pseudoku/grid/__init__.py @@ -196,19 +196,51 @@ class Grid(object): return None + def normalize_cells(self): + """Normalizes every cell in the grid. + + Returns the number of cell changes.""" + + cell_changes = 0 + + for cell in self._cells: + cell_changes += cell.normalize() + + return cell_changes + + 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 + + _solution_steps = [ + normalize_cells, + resolve_uniques, + ] + def solve(self): - """Attempts to solve the grid.""" + """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 - # Step 0: Normalize cells, i.e. find any that can only be one value - self.normalize_cells() + while not self.is_filled(): + cell_changes = 0 - # Step 1: Find values that can only go in one cell in a group - for group in self.constraints: - group.resolve_uniques() + for method in self._solution_steps: + cell_changes += method(self) + # If we changed something, start over with simple steps again + if x != 0: + 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 stuck + if cell_changes == 0: + break diff --git a/pseudoku/grid/cell.py b/pseudoku/grid/cell.py index 0262130..66eb446 100644 --- a/pseudoku/grid/cell.py +++ b/pseudoku/grid/cell.py @@ -35,47 +35,58 @@ class Cell(object): def set(self, value, normalize=True): """Sets the value of this cell. If `normalize` is True or omitted, the grid will be updated accordingly. + + Returns the number of cell changes. """ self._values = [value] if normalize: self._normalized = False - self.normalize() - + return self.normalize() + 1 + + return 1 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. + This method is exhaustive; repeated calls should have no effect. + + Returns the number of cell changes. """ if self._normalized: # Already done - return + return 0 # Set this now just in case of infinite looping self._normalized = True if not self.solved: # Don't know the value yet - return + return 0 # Elimination time + cell_changes = 0 for constraint in self.constraints: for cell in constraint.cells: if cell == self: continue - cell.eliminate(self.value) + cell_changes += cell.eliminate(self.value) + return cell_changes def eliminate(self, value): - """Eliminates the given value as a possibility for this cell.""" - if value in self._values: - self._values.remove(value) + """Eliminates the given value as a possibility for this cell. + + Returns the number of cell changes.""" + if value not in self._values: + return 0 - if len(self._values) == 0: - # XXX give me a real exception here - raise Exception + self._values.remove(value) - self._normalized = False - self.normalize() + if len(self._values) == 0: + # XXX give me a real exception here + raise Exception + + self._normalized = False + return self.normalize() + 1 diff --git a/pseudoku/grid/constraints.py b/pseudoku/grid/constraints.py index 2495102..e1ea667 100644 --- a/pseudoku/grid/constraints.py +++ b/pseudoku/grid/constraints.py @@ -7,6 +7,11 @@ class Constraint(object): ### Accessors + # True iff a constraint consists of a straight line of cells. Used to + # quickly skip over pairs of constraints that cannot possibly have more + # than one cell in common. + is_linear = False + # NOTE: _cells is a list of refs; _grid is a ref # XXX document this cells = property(lambda self: [ x() for x in self._cells ]) @@ -28,6 +33,14 @@ class Constraint(object): return possible_cells def resolve_uniques(self): + """Searches for values that can only appear in one cell, and sets them + appropriately. + + Returns the number of cell changes. + """ + + cell_changes = 0 + for value in xrange(self.grid.size): # XXX cache values that are taken care of possible_cells = self.find_value(value) @@ -43,7 +56,9 @@ class Constraint(object): continue # Only cell in the group that can be value - target_cell.set(value) + cell_changes += target_cell.set(value) + + return cell_changes class Box(Constraint): @@ -68,6 +83,8 @@ class Box(Constraint): class Row(Constraint): + is_linear = True + def __init__(self, grid, position): self._grid = ref(grid) self._pos = position @@ -77,6 +94,8 @@ class Row(Constraint): self._cells.append(ref(self.grid.cell(self._pos, col))) class Column(Constraint): + is_linear = True + def __init__(self, grid, position): self._grid = ref(grid) self._pos = position @@ -86,6 +105,8 @@ class Column(Constraint): self._cells.append(ref(self.grid.cell(row, self._pos))) class Diagonal(Constraint): + is_linear = True + def __init__(self, grid, direction='down', offset=0): self._grid = ref(grid) self._direction = direction -- 2.7.4