X-Git-Url: http://git.veekun.com/pseudoku.git/blobdiff_plain/625dc584bed28259ed4db1665b99c8d6f4261033..30f8ff60eb4bd6d8b6f4467ba0b7bbe29a8a92ee:/pseudoku/grid/__init__.py

diff --git a/pseudoku/grid/__init__.py b/pseudoku/grid/__init__.py
index 9ba0158..83e358f 100644
--- a/pseudoku/grid/__init__.py
+++ b/pseudoku/grid/__init__.py
@@ -82,6 +82,13 @@ class Grid(object):
     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):
@@ -180,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