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.

diff --git a/pseudoku/__init__.py b/pseudoku/__init__.py
index 2fe15f3..c7a803b 100644 (file)
--- a/pseudoku/__init__.py
+++ b/pseudoku/__init__.py
@@ -1,5 +1,5 @@
 from grid import Grid
 from grid import Grid

-from grid.cellgroup import Diagonal
+from grid.constraints import Diagonal

 import render.text
 
 def main():
 import render.text
 
 def main():

diff --git a/pseudoku/grid/__init__.py b/pseudoku/grid/__init__.py
index 9ba0158..caf135d 100644 (file)
--- a/pseudoku/grid/__init__.py
+++ b/pseudoku/grid/__init__.py
@@ -196,19 +196,51 @@ class Grid(object):
         return None
 
 
         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):
     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
 
         # 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 (file)
--- 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.
     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._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.
 
 
     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
         """
 
         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
 
         # 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
 
         # Elimination time

+        cell_changes = 0

         for constraint in self.constraints:
             for cell in constraint.cells:
                 if cell == self:
                     continue
         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):
 
     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 (file)
--- a/pseudoku/grid/constraints.py
+++ b/pseudoku/grid/constraints.py
@@ -7,6 +7,11 @@ class Constraint(object):
 
     ### Accessors
 
 
     ### 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 ])
     # 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):
         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)
         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
                 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):
 
 
 class Box(Constraint):


@@ -68,6 +83,8 @@ class Box(Constraint):
 
 
 class Row(Constraint):
 
 
 class Row(Constraint):

+    is_linear = True
+

     def __init__(self, grid, position):
         self._grid = ref(grid)
         self._pos = position
     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):
             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
     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):
             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
     def __init__(self, grid, direction='down', offset=0):
         self._grid = ref(grid)
         self._direction = direction