Renamed integrity tests to standard.

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

diff --git a/pseudoku/grid/__init__.py b/pseudoku/grid/__init__.py
index 94d0833..83e358f 100644 (file)
--- a/pseudoku/grid/__init__.py
+++ b/pseudoku/grid/__init__.py
@@ -1,10 +1,11 @@
 from __future__ import division
 
 from math import sqrt
 from __future__ import division
 
 from math import sqrt

+from operator import attrgetter

 import re
 import re

-from weakref import proxy

 
 

-from cellgroup import 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)]
 
 
 symbols = [str(x + 1) for x in range(9)] + [chr(x + 97) for x in xrange(26)]
 


@@ -18,100 +19,6 @@ class GridIntegrityError(Exception):
     """
     pass
 
     """
     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)
-
-    def _get_row(self):
-        """Returns the Row object associated with this cell."""
-        return self._grid._rows[self._row]
-    row = property(_get_row)
-
-    def _get_column(self):
-        """Returns the Column object associated with this cell."""
-        return self._grid._columns[self._col]
-    column = property(_get_column)
-
-    def _get_box(self):
-        """Returns the Box object associated with this cell."""
-        # Some actual math required here!
-        # Row 0..2 -> box 0..2
-        # Col 0..2 -> box 0, 3, 6 (box col 0)
-        box_row = self._row // self._grid._box_height
-        box_col = self._col // self._grid._box_width
-        box_idx = box_row * self._grid._box_height + box_col
-        return self._grid._boxes[box_idx]
-    box = property(_get_box)
-
-    def __init__(self, grid, row, column):
-        self._grid = proxy(grid)
-        self._row = row
-        self._col = column
-        self._values = range(self._grid.size)
-        self._normalized = False
-
-    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 group_type in 'row', 'column', 'box':
-            group = getattr(self, group_type)
-            for cell in group.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."""
 
 class Grid(object):
     """Represents a Sudoku grid."""


@@ -120,7 +27,7 @@ class Grid(object):
 
     def _cellidx(self, row, col):
         """Hashes a row and column into a flat array index."""
 
     def _cellidx(self, row, col):
         """Hashes a row and column into a flat array index."""

-        return row * self._size + col
+        return row * self.size + col

 
     @classmethod
     def _infer_box_size(cls, dimension):
 
     @classmethod
     def _infer_box_size(cls, dimension):


@@ -158,21 +65,29 @@ class Grid(object):
 
     ### Accessors
 
 
     ### Accessors
 

-    def _get_box_height(self):
-        return self._box_height
-    box_height = property(_get_box_height)
+    def get_constraints(self, constraint_class=Constraint):
+        """Returns constraints of a certain type.  Returns all of them by
+        default.
+        """
+
+        condition = lambda constraint: isinstance(constraint, constraint_class)
+        return filter(condition, self._constraints)

 
 

-    def _get_box_width(self):
-        return self._box_width
-    box_width = property(_get_box_width)
+    rows = property(lambda self: self.get_constraints(Row))
+    columns = property(lambda self: self.get_constraints(Column))
+    boxes = property(lambda self: self.get_constraints(Box))

 
 

-    def _get_size(self):
-        return self._size
-    size = property(_get_size)
+    box_height = property(attrgetter('_box_height'))
+    box_width = property(attrgetter('_box_width'))
+    size = property(attrgetter('_size'))
+    constraints = property(attrgetter('_constraints'))

 
 

-    def _get_cell_groups(self):
-        return self._rows + self._columns + self._boxes
-    cell_groups = property(_get_cell_groups)
+    def _is_filled(self):
+        for cell in self._cells:
+            if cell.value == None:
+                return False
+        return True
+    filled = property(_is_filled)

 
     ### Constructors
 
 
     ### Constructors
 


@@ -184,16 +99,15 @@ class Grid(object):
         self._box_width = box_width
         self._size = box_height * box_width
 
         self._box_width = box_width
         self._size = box_height * box_width
 

-        self._rows = [Row(self, i) for i in xrange(self._size)]
-        self._columns = [Column(self, i) for i in xrange(self._size)]
-        self._boxes = [Box(self, i) for i in xrange(self._size)]
-
-        self._cells = range(self._size ** 2)
-        for row in xrange(self._size):
-            for col in xrange(self._size):
+        self._cells = range(self.size ** 2)
+        for row in xrange(self.size):
+            for col in xrange(self.size):

                 self._cells[self._cellidx(row, col)] \
                     = Cell(self, row, col)
 
                 self._cells[self._cellidx(row, col)] \
                     = Cell(self, row, col)
 

+        self._constraints = []
+        self.add_default_constraints()
+

     @classmethod
     def from_matrix(cls, rows, box_height=None, box_width=None):
         """Creates and returns a grid read from a list of lists."""
     @classmethod
     def from_matrix(cls, rows, box_height=None, box_width=None):
         """Creates and returns a grid read from a list of lists."""


@@ -205,8 +119,8 @@ class Grid(object):
 
         self = cls(box_width=box_width, box_height=box_height)
 
 
         self = cls(box_width=box_width, box_height=box_height)
 

-        for row in xrange(self._size):
-            for col in xrange(self._size):
+        for row in xrange(self.size):
+            for col in xrange(self.size):

                 value = rows[row][col]
                 if not value:
                     continue
                 value = rows[row][col]
                 if not value:
                     continue


@@ -244,8 +158,8 @@ class Grid(object):
 
         self = cls(box_width=box_width, box_height=box_height)
 
 
         self = cls(box_width=box_width, box_height=box_height)
 

-        for row in xrange(self._size):
-            for col in xrange(self._size):
+        for row in xrange(self.size):
+            for col in xrange(self.size):

                 ch = grid[ self._cellidx(row, col) ]
                 if ch == '0':
                     continue
                 ch = grid[ self._cellidx(row, col) ]
                 if ch == '0':
                     continue


@@ -253,40 +167,68 @@ class Grid(object):
 
         return self
 
 
         return self
 

+    ### Constraints
+
+    def add_constraint(self, constraint):
+        self._constraints.append(constraint)
+        for cell in constraint.cells:
+            cell.add_constraint(constraint)
+
+    def add_default_constraints(self):
+        for i in xrange(self.size):
+            self.add_constraint(Row(self, i))
+            self.add_constraint(Column(self, i))
+            self.add_constraint(Box(self, i))
+
+        return
+

     ### Inspectors
 
     def cell(self, row, column):
         return self._cells[self._cellidx(row, column)]
 
     ### Inspectors
 
     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:
         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.cell_groups:
-            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