X-Git-Url: http://git.veekun.com/pseudoku.git/blobdiff_plain/bfc07962deafde17e2b41f8d659313b7746dca07..ef420dd690bb7803272ebc08c8e7a6e132dd0061:/lib/pseudoku/grid/__init__.py diff --git a/lib/pseudoku/grid/__init__.py b/lib/pseudoku/grid/__init__.py deleted file mode 100644 index d1906ae..0000000 --- a/lib/pseudoku/grid/__init__.py +++ /dev/null @@ -1,319 +0,0 @@ -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