--- /dev/null
+from __future__ import division
+
+from math import sqrt
+import re
+from weakref import proxy
+
+from cellgroup import Row, Column, Box
+
+symbols = [str(x + 1) for x in range(9)] + [chr(x + 97) for x in xrange(26)]
+
+class GridSizeError(Exception):
+ 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_naively(self, value):
+ """Sets the value of this cell, WITHOUT eliminating the value from
+ every other cell in its row/column/box.
+ """
+
+ self._values = [value]
+
+ def set(self, value):
+ """Sets the value of this cell and adjusts the grid accordingly."""
+ self.set_naively(value)
+ 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()
+
+
+ def __str__(self):
+ """Stringification for pretty-printing."""
+ if self.value != None:
+ return symbols[self.value]
+
+ return '.'
+
+
+class Grid(object):
+ """Represents a Sudoku grid."""
+
+ ### Utilities
+
+ def _cellidx(self, row, col):
+ """Hashes a row and column into a flat array index."""
+ return row * self._size + col
+
+ @classmethod
+ def _infer_box_size(cls, dimension):
+ """Attempts to infer the size of a box, given some dimension of the
+ entire grid, i.e. the number of cells per box/row/column.
+
+ Returns a tuple of height, width."""
+
+ # Most obvious: probably n * n.
+ root = int(sqrt(dimension))
+ if root ** 2 == dimension:
+ return root, root
+
+ # Otherwise, probably n * (n - 1) or n * (n - 2).
+ # These puzzles generally have the wide side (n) as the width.
+ # This is of course entirely unreliable, but better than nothing..
+ # n^2 - (1|2)n - dimension = 0
+ # Determinant is (1|2)^2 + 4 * dimension and has to be square
+ for difference in 1, 2:
+ determinant = difference ** 2 + 4 * dimension
+ root = int(sqrt(determinant))
+ if root ** 2 != determinant:
+ continue
+
+ n = (-difference + root) / 2
+ if n != int(n):
+ continue
+
+ # Success!
+ return n - difference, n
+
+ # Okay, I don't have a clue.
+ raise GridSizeError("Can't infer box height and width for grid size "
+ "%d; please specify them manually" % dimension)
+
+ ### Accessors
+
+ def _get_box_height(self):
+ return self._box_height
+ box_height = property(_get_box_height)
+
+ def _get_box_width(self):
+ return self._box_width
+ box_width = property(_get_box_width)
+
+ def _get_size(self):
+ return self._size
+ size = property(_get_size)
+
+ def _get_cell_groups(self):
+ return self._rows + self._columns + self._boxes
+ cell_groups = property(_get_cell_groups)
+
+ ### Constructors
+
+ def __init__(self, box_height=3, box_width=None):
+ if not box_width:
+ box_width = box_height
+
+ self._box_height = box_height
+ 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[self._cellidx(row, col)] \
+ = Cell(self, row, col)
+
+ @classmethod
+ def from_matrix(cls, rows, box_height=None, box_width=None):
+ """Creates and returns a grid read from a list of lists."""
+
+ if not box_height:
+ box_height, box_width = cls._infer_box_size(len(rows))
+ elif not box_width:
+ box_width = box_height
+
+ self = cls(box_width=box_width, box_height=box_height)
+
+ for row in xrange(self._size):
+ for col in xrange(self._size):
+ value = rows[row][col]
+ if not value:
+ continue
+ self.cell(row, col).set_naively(value - 1)
+
+ return self
+
+ @classmethod
+ def from_string(cls, grid, box_height=None, box_width=None):
+ # XXX sanity check dimensions
+ """Creates and returns a grid from a string of symbols.
+
+ Symbols are the digits 1 to 9 followed by the letters of the alphabet.
+ Zeroes and periods are assumed to be empty cells. All other characters
+ are ignored.
+
+ Since whitespace is ignored, the string could be all in one line or
+ laid out visually in a square, one row per line."""
+
+ # Collapse the string down to just characters we want
+ grid = grid.lower()
+ grid = re.sub('\\.', '0', grid)
+ grid = re.sub('[^0-9a-z]', '', grid)
+
+ # Figure out the length of one side/box
+ size = int(sqrt(len(grid)))
+ if size ** 2 != len(grid):
+ raise GridSizeError("Provided string does not form a square")
+
+ # Set height/width..
+ if not box_height:
+ box_height, box_width = cls._infer_box_size(size)
+ elif not box_width:
+ box_width = box_height
+
+ self = cls(box_width=box_width, box_height=box_height)
+
+ for row in xrange(self._size):
+ for col in xrange(self._size):
+ ch = grid[ self._cellidx(row, col) ]
+ if ch == '0':
+ continue
+ self.cell(row, col).set_naively(symbols.index(ch))
+
+ return self
+
+ ### Methods
+
+ def cell(self, row, column):
+ return self._cells[self._cellidx(row, column)]
+
+
+ ### Solving
+
+ 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
+ return None
+
+ def solve(self):
+ """Attempts to solve the grid."""
+ # 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()
+
+ # Step 1: Find values that can only go in one cell in a group
+ for group in self.cell_groups:
+ group.resolve_uniques()
+
+
+ def normalize_cells(self):
+ """Normalizes every cell in the grid."""
+ for cell in self._cells:
+ cell.normalize()
+
+
+ def __str__(self):
+ """Pretty-printing."""
+ divider = '+'
+ for box in xrange(self._box_height):
+ for col in xrange(self._box_width):
+ divider += '-'
+ divider += '+'
+
+ res = ''
+ for row in xrange(self._size):
+ if row % self._box_height == 0:
+ res += divider
+ res += "\n"
+
+ for col in xrange(self._size):
+ if col % self._box_width == 0:
+ res += '|'
+ res += str(self.cell(row, col))
+
+ res += '|'
+ res += "\n"
+
+ res += divider
+ res += "\n"
+
+ return res
projects / pseudoku.git / blobdiff