+++ /dev/null
-from __future__ import division
-
-from math import sqrt
-import re
-from weakref import proxy
-
-symbols = [str(x + 1) for x in range(9)] + [chr(x + 97) for x in xrange(26)]
-
-
-class GridSizeError(Exception):
- pass
-
-class CellGroup(object):
- """Represents any group of cells in a grid."""
-
- ### Accessors
-
- cells = []
-
- ### Methods
- # XXX inherited __init__
-
- def find_value(self, value):
- """Returns the cells that can be a specific value."""
- possible_cells = []
- for cell in self.cells:
- if value in cell._values:
- possible_cells.append(cell)
-
- if len(possible_cells) == 0:
- raise Exception # XXX
-
- return possible_cells
-
- def resolve_uniques(self):
- for value in xrange(self._grid._size):
- # XXX cache values that are taken care of
- possible_cells = self.find_value(value)
-
- if len(possible_cells) > 1:
- # Not unique
- continue
-
- target_cell = possible_cells[0]
- if target_cell.solved:
- # Already seen this
- # XXX this is what cache is for
- continue
-
- # Only cell in the group that can be value
- target_cell.set(value)
-
-
-class Box(CellGroup):
- def _get_box_row(self):
- return self._pos // self._grid._box_width
- box_row = property(_get_box_row)
-
- def _get_box_column(self):
- return self._pos % self._grid._box_height
- box_column = property(_get_box_column)
-
- def _get_cells(self):
- # XXX generator + docstring
- cells = []
- for row in xrange(self._grid._box_height):
- for col in xrange(self._grid._box_width):
- cell_row = row + self.box_row * self._grid._box_height
- cell_col = col + self.box_column * self._grid._box_width
- cells.append(self._grid.cell(cell_row, cell_col))
- return cells
- cells = property(_get_cells)
-
- def __init__(self, grid, position):
- self._grid = proxy(grid)
- self._pos = position
-
-
-class Row(CellGroup):
- def _get_cells(self):
- # XXX generator + docstring
- cells = []
- for col in xrange(self._grid._size):
- cells.append(self._grid.cell(self._pos, col))
- return cells
- cells = property(_get_cells)
-
- def __init__(self, grid, position):
- self._grid = proxy(grid)
- self._pos = position
-
-
-class Column(CellGroup):
- def _get_cells(self):
- # XXX generator + docstring
- cells = []
- for row in xrange(self._grid._size):
- cells.append(self._grid.cell(row, self._pos))
- return cells
- cells = property(_get_cells)
-
- def __init__(self, grid, position):
- self._grid = proxy(grid)
- self._pos = position
-
-
-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):
- # XXX
- 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
-
-
-grid = Grid.from_string("..... ..... ..... ..... ....")
-grid = Grid.from_string("""
- ...69....
- 9.5..876.
- ..4..1.2.
- 6...5...3
- 38.....49
- 7...3...2
- .7.9..3..
- .231..4.8
- ....83...
-""")
-
-print grid
-
-grid.solve()
-
-print grid
projects / pseudoku.git / blobdiff