Commits

lakin.wecker  committed 1a6d416 Draft

initial version with very simple solver.

  • Participants

Comments (0)

Files changed (3)

+.pyc$

File sudoku/__init__.py

+import sys
+from collections import defaultdict
+
+#-------------------------------------------------------------------------------
+class Cell(object):
+
+    #---------------------------------------------------------------------------
+    def __init__(self, row, col, game):
+        self.row = row
+        self.col = col
+        self.game = game
+        self._value = None
+
+        self.allowed = [1 for x in range(9)]
+
+    #---------------------------------------------------------------------------
+    def __unicode__(self):
+        return u"%s" % (self.value or " ",)
+    __repr__ = __unicode__
+
+    #---------------------------------------------------------------------------
+    def get_value(self):
+        return self._value
+
+    #---------------------------------------------------------------------------
+    def set_value(self, value):
+        #self._check_validity()
+        self._value = value
+        self.allowed = [0 for x in range(9)]
+        #self._update_neighbors()
+    value = property(get_value, set_value)
+
+    #---------------------------------------------------------------------------
+    def update_allowed(self):
+
+        # Assume everything allowed - and reduce it based on value in our block
+        # row and column
+        if self.value is None:
+            self.allowed = [1 for x in range(9)]
+            self.filter_row(self.row, self.allowed)
+            self.filter_col(self.col, self.allowed)
+            self.filter_block(self.row, self.col, self.allowed)
+        else:
+            self.allowed = [0 for x in range(9)]
+
+    #---------------------------------------------------------------------------
+    def filter_row(self, row, allowed):
+        for cell in self.game.row_iter(row):
+            if cell.value is not None:
+                allowed[cell.value-1] = 0
+
+    #---------------------------------------------------------------------------
+    def filter_col(self, col, allowed):
+        for cell in self.game.col_iter(col):
+            if cell.value is not None:
+                allowed[cell.value-1] = 0
+
+    #---------------------------------------------------------------------------
+    def filter_block(self, row, col, allowed):
+        for cell in self.game.block_iter(row, col):
+            if cell.value is not None:
+                allowed[cell.value-1] = 0
+
+#-------------------------------------------------------------------------------
+class Game(object):
+
+    #---------------------------------------------------------------------------
+    def __init__(self, grid):
+        self.grid = grid
+        for row in range(9):
+            for col in range(9):
+                val = self.grid[row][col]
+                self.grid[row][col] = Cell(row, col, self)
+                self.grid[row][col].value = val
+
+    #---------------------------------------------------------------------------
+    def is_solved(self):
+        count = 0
+        for row in range(9):
+            for col in range(9):
+                if self.grid[row][col].value is None:
+                    count += 1
+        print "missing %s values" % (count,)
+        return count == 0
+
+    #---------------------------------------------------------------------------
+    def row_iter(self, row):
+        for col in range(9):
+            yield self.grid[row][col]
+
+    #---------------------------------------------------------------------------
+    def col_iter(self, col):
+        for row in range(9):
+            yield self.grid[row][col]
+
+    #---------------------------------------------------------------------------
+    def block_iter(self, row, col):
+        if row < 3:
+            start_row = 0
+        elif row < 6:
+            start_row = 3
+        else:
+            start_row = 6
+
+        if col < 3:
+            start_col = 0
+        elif col < 6:
+            start_col = 3
+        else:
+            start_col = 6
+
+        for row in range(start_row, start_row+3):
+            for col in range(start_col, start_col+3):
+                yield self.grid[row][col]
+
+    #---------------------------------------------------------------------------
+    def solve_cell(self, row, col):
+
+        # First - see if we've narrowed it down so that ONLY one value can go
+        #         here because the row, column and block have used up the other
+        #         values.
+        cell = self.grid[row][col]
+        cell.update_allowed()
+        if sum(cell.allowed) == 1:
+            for i in range(9):
+                if (cell.allowed[i]):
+                    cell.value = i + 1
+                    cell.update_allowed()
+
+    #---------------------------------------------------------------------------
+    def solve_iteration(self):
+        for row in range(9):
+            for col in range(9):
+                val = self.grid[row][col].value
+                cell = self.grid[row][col]
+                cell.update_allowed()
+                if val is None:
+                    self.solve_cell(row, col)
+
+
+        # go through all the rows and see which empty cells are the ONLY
+        # cells that can have a particular value.
+        for row in range(9):
+            cells_for_value = defaultdict(list)
+            for col in range(9):
+                cell = self.grid[row][col]
+                cell.update_allowed()
+                if cell.value is None:
+                    for i in range(9):
+                        if cell.allowed[i] == 1:
+                            cells_for_value[i+1].append(cell)
+
+            for key, cells in cells_for_value.iteritems():
+                # if this is the ONLY one that allows this value
+                # in the row, make it so
+                if len(cells) == 1:
+                    cell = cells[0]
+                    if cell.value is None:
+                        cell.value = key
+                        cell.update_allowed()
+
+        # go through all the cols and see which empty cells are the ONLY
+        # cells that can have a particular value.
+        for col in range(9):
+            cells_for_value = defaultdict(list)
+            for row in range(9):
+                cell = self.grid[row][col]
+                cell.update_allowed()
+                if cell.value is None:
+                    for i in range(9):
+                        if cell.allowed[i] == 1:
+                            cells_for_value[i+1].append(cell)
+
+            for key, cells in cells_for_value.iteritems():
+                # if this is the ONLY one that allows this value
+                # in the row, make it so
+                if len(cells) == 1:
+                    cell = cells[0]
+                    if cell.value is None:
+                        cell.value = key
+                        cell.update_allowed()
+
+        # go through all the cols and see which empty cells are the ONLY
+        # cells that can have a particular value.
+        blocks = [
+                [[0,1,2], [0,1,2]],
+                [[0,1,2], [3,4,5]],
+                [[0,1,2], [6,7,8]],
+                [[3,4,5], [0,1,2]],
+                [[3,4,5], [3,4,5]],
+                [[3,4,5], [6,7,8]],
+                [[6,7,8], [0,1,2]],
+                [[6,7,8], [3,4,5]],
+                [[6,7,8], [6,7,8]],
+        ]
+        for block in blocks:
+            cells_for_value = defaultdict(list)
+            for row in block[0]:
+                for col in block[1]:
+                    cell = self.grid[row][col]
+                    cell.update_allowed()
+                    if cell.value is None:
+                        for i in range(9):
+                            if cell.allowed[i] == 1:
+                                cells_for_value[i+1].append(cell)
+
+            for key, cells in cells_for_value.iteritems():
+                # if this is the ONLY one that allows this value
+                # in the row, make it so
+                if len(cells) == 1:
+                    cell = cells[0]
+                    if cell.value is None:
+                        cell.value = key
+                        cell.update_allowed()
+
+    #---------------------------------------------------------------------------
+    def solve(self):
+        while not self.is_solved():
+            self.solve_iteration()
+
+
+    #---------------------------------------------------------------------------
+    def __unicode__(self):
+        row_count = 0
+        output = u""
+        for row in self.grid:
+            if row_count % 3 == 0:
+                output += (u" "*80)
+                output += u"\n"
+            col_count = 0
+            for col in row:
+                if col_count % 3 == 0:
+                    output += "  "
+                output += (u"(%s)" % col)
+                col_count += 1
+            output += "\n"
+            row_count += 1
+        return output
+
+
+_ = None
+grid = [
+    [_, _, _,   _, _, _,   _, _, _],
+    [2, _, 6,   7, _, 9,   _, _, _],
+    [1, _, _,   _, 2, 8,   _, _, 9],
+
+    [_, _, 3,   4, _, 5,   _, 9, 2],
+    [_, _, 1,   _, _, _,   3, _, _],
+    [9, 5, _,   2, _, 3,   7, _, _],
+
+    [7, _, _,   9, _, _,   _, _, 8],
+    [_, _, _,   8, _, 4,   6, _, 7],
+    [_, _, _,   _, _, _,   _, _, _],
+]
+
+if __name__ == "__main__":
+    game = Game(grid)
+    print unicode(game)
+    game.solve_iteration()
+    game.solve_iteration()
+    game.solve_iteration()
+    game.solve_iteration()
+    game.solve_iteration()
+    game.solve_iteration()
+    game.solve_iteration()
+    game.solve_iteration()
+    print unicode(game)
+    game.is_solved()

File sudoku/tests.py

+from unittest import TestCase
+
+from sudoku import Game
+
+_ = None
+
+class SimpleTestCases(TestCase):
+    def test_row_almost_filled(self):
+        game = Game([
+            [_, _, _,   _, _, _,   _, _, _],
+            [_, 2, 3,   4, 5, 6,   7, 8, 9],
+            [_, _, _,   _, _, _,   _, _, _],
+            [_, _, _,   _, _, _,   _, _, _],
+            [_, _, _,   _, _, _,   _, _, _],
+            [_, _, _,   _, _, _,   _, _, _],
+            [_, _, _,   _, _, _,   _, _, _],
+            [_, _, _,   _, _, _,   _, _, _],
+            [_, _, _,   _, _, _,   _, _, _],
+        ])
+        cell = game.grid[1][0]
+        game.solve_cell(1, 0)
+        self.assertEqual(cell.value, 1)
+
+    def test_col_almost_filled(self):
+        game = Game([
+            [_, _, _,   _, _, _,   _, _, _],
+            [_, 2, _,   _, _, _,   _, _, _],
+            [_, 3, _,   _, _, _,   _, _, _],
+            [_, 4, _,   _, _, _,   _, _, _],
+            [_, 5, _,   _, _, _,   _, _, _],
+            [_, 6, _,   _, _, _,   _, _, _],
+            [_, 7, _,   _, _, _,   _, _, _],
+            [_, 8, _,   _, _, _,   _, _, _],
+            [_, 9, _,   _, _, _,   _, _, _],
+        ])
+        cell = game.grid[0][1]
+        game.solve_cell(0, 1)
+        self.assertEqual(cell.value, 1)
+
+    def test_block_almost_filled(self):
+        game = Game([
+            [3, _, 9,   _, _, _,   _, _, _],
+            [4, 2, 8,   _, _, _,   _, _, _],
+            [5, 6, 7,   _, _, _,   _, _, _],
+            [_, _, _,   _, _, _,   _, _, _],
+            [_, _, _,   _, _, _,   _, _, _],
+            [_, _, _,   _, _, _,   _, _, _],
+            [_, _, _,   _, _, _,   _, _, _],
+            [_, _, _,   _, _, _,   _, _, _],
+            [_, _, _,   _, _, _,   _, _, _],
+        ])
+        cell = game.grid[0][1]
+        game.solve_cell(0, 1)
+        self.assertEqual(cell.value, 1)
+
+    def test_cell_is_only_one_that_can_have_number_in_block(self):
+        game = Game([
+            [_, _, _,   _, _, _,   _, _, _],
+            [_, _, _,   _, _, _,   2, _, _],
+            [_, _, _,   2, _, _,   _, _, _],
+
+            [_, 2, _,   _, _, _,   _, _, _],
+            [_, _, _,   _, _, _,   _, _, _],
+            [_, _, _,   _, _, _,   _, _, _],
+
+            [_, _, 2,   _, _, _,   _, _, _],
+            [_, _, _,   _, _, _,   _, _, _],
+            [_, _, _,   _, _, _,   _, _, _],
+        ])
+        cell = game.grid[0][0]
+        game.solve_iteration()
+        self.assertEqual(cell.value, 2)
+
+    def test_cell_is_only_one_that_can_have_number_in_block_2(self):
+        game = Game([
+            [_, _, _,   _, _, _,   1, _, _],
+            [_, _, _,   _, _, _,   _, _, 5],
+            [_, _, _,   2, _, _,   _, _, _],
+
+            [_, 2, _,   _, _, _,   _, _, _],
+            [_, _, _,   _, _, _,   _, 2, _],
+            [_, _, _,   _, _, _,   _, _, _],
+
+            [_, _, 2,   _, _, _,   _, _, _],
+            [_, _, _,   _, _, _,   _, _, _],
+            [_, _, _,   _, _, _,   _, _, 2],
+        ])
+        cell = game.grid[0][0]
+        game.solve_iteration()
+        self.assertEqual(cell.value, 2)