from grid import Grid
-from grid.cellgroup import Diagonal
+from grid.constraints import Diagonal
import render.text
def main():
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
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.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.
- 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
- 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
- return
+ return 0
# Elimination time
+ cell_changes = 0
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):
- """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
### 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 ])
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)
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 Row(Constraint):
+ is_linear = True
+
def __init__(self, grid, position):
self._grid = ref(grid)
self._pos = position
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
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
projects / pseudoku.git / commitdiff
