From: Eevee <eevee@nyarumaa.(none)>
Date: Sun, 7 Dec 2008 00:16:48 +0000 (-0500)
Subject: Simple Sudoku solver.
X-Git-Url: http://git.veekun.com/pseudoku.git/commitdiff_plain/814cd65ab17e00cd78062f8c5c2472e6e68d6de8?ds=sidebyside

Simple Sudoku solver.

Solves a 3x3 Sudoku grid hardcoded into it, as long as only simple
elimination is required.
---

814cd65ab17e00cd78062f8c5c2472e6e68d6de8
diff --git a/pseudoku.py b/pseudoku.py
new file mode 100644
index 0000000..e6db889
--- /dev/null
+++ b/pseudoku.py
@@ -0,0 +1,342 @@
+from weakref import proxy
+
+symbols = [str(x + 1) for x in range(9)] + [chr(x + 97) for x in xrange(26)]
+
+
+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
+
+    ### 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)
+
+    ### Methods
+
+    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)
+
+    def from_lists(self, *rows):
+        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)
+
+
+    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(3, 3)
+grid.from_lists(
+    [ 0, 0, 0, 6, 9, 0, 0, 0, 0 ],
+    [ 9, 0, 5, 0, 0, 8, 7, 6, 0 ],
+    [ 0, 0, 4, 0, 0, 1, 0, 2, 0 ],
+    [ 6, 0, 0, 0, 5, 0, 0, 0, 3 ],
+    [ 3, 8, 0, 0, 0, 0, 0, 4, 9 ],
+    [ 7, 0, 0, 0, 3, 0, 0, 0, 2 ],
+    [ 0, 7, 0, 9, 0, 0, 3, 0, 0 ],
+    [ 0, 2, 3, 1, 0, 0, 4, 0, 8 ],
+    [ 0, 0, 0, 0, 8, 3, 0, 0, 0 ],
+)
+
+print grid
+
+grid.solve()
+
+print grid