from math import sqrt
from operator import attrgetter
import re
-from weakref import ref
+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)]
"""
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)
-
- grid = property(lambda self: self._grid())
- constraints = property(attrgetter('_constraints'))
-
- def __init__(self, grid, row, column):
- self._grid = ref(grid)
- self._row = row
- self._col = column
- self._values = range(self.grid.size)
- self._constraints = []
- self._normalized = False
-
- def add_constraint(self, constraint):
- self._constraints.append(constraint)
-
- 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 constraint in self.constraints:
- for cell in constraint.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."""
return filter(condition, self._constraints)
rows = property(lambda self: self.get_constraints(Row))
+ columns = property(lambda self: self.get_constraints(Column))
+ boxes = property(lambda self: self.get_constraints(Box))
+
box_height = property(attrgetter('_box_height'))
box_width = property(attrgetter('_box_width'))
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):
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
+
+ _solution_steps = [
+ normalize_cells,
+ resolve_uniques,
+ ]
- # Step 0: Normalize cells, i.e. find any that can only be one value
- self.normalize_cells()
+ def solve(self):
+ """Attempts to solve the grid by running through various methods of
+ elimination one at a time, from simplest to most complex."""
- # Step 1: Find values that can only go in one cell in a group
- for group in self.constraints:
- group.resolve_uniques()
+ while True:
+ for method in self._solution_steps:
+ cell_changes = method(self)
+ # If we changed something, start over with simple steps again
+ if cell_changes:
+ 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 done
+ if not cell_changes:
+ break
projects / pseudoku.git / blobdiff