Improved solving; should now solve all easy puzzles.

[pseudoku.git] / pseudoku / grid / __init__.py

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
 
 
+    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