Update sudoku-solver.py

kamyu104 · kamyu104 · commit 0ff86d24dade · 2015-11-29T20:38:18.000+08:00
diff --git a/Python/sudoku-solver.py b/Python/sudoku-solver.py
@@ -13,46 +13,33 @@ class Solution:
     # Solve the Sudoku by modifying the input board in-place.
     # Do not return any value.
     def solveSudoku(self, board):
-        for i in xrange(len(board)):
-            for j in xrange(len(board[0])):
-                if(board[i][j] == '.'):
-                    for k in xrange(9):
-                        board[i][j] = chr(ord('1') + k)
-                        if self.isValid(board, i, j) and self.solveSudoku(board):
-                            return True
-                        board[i][j] = '.'
+        def isValid(board, x, y):
+            for i in xrange(9):
+                if i != x and board[i][y] == board[x][y]:
                     return False
-        return True
-    
-    def isValid(self, board, x, y):
-        for i in xrange(9):
-            if i != x and board[i][y] == board[x][y]:
-                return False
-            
-        for j in xrange(9):
-            if j != y and board[x][j] == board[x][y]:
-                return False
-            
-        i = 3 * (x / 3)
-        while i < 3 * (x / 3 + 1):
-            j = 3 * (y / 3)
-            while j < 3 * (y / 3 + 1):
-                if (i != x or j != y) and board[i][j] == board[x][y]:
+            for j in xrange(9):
+                if j != y and board[x][j] == board[x][y]:
                     return False
-                j += 1
-            i += 1
-            
-        return True
+            i = 3 * (x / 3)
+            while i < 3 * (x / 3 + 1):
+                j = 3 * (y / 3)
+                while j < 3 * (y / 3 + 1):
+                    if (i != x or j != y) and board[i][j] == board[x][y]:
+                        return False
+                    j += 1
+                i += 1
+            return True
+        
+        def solver(board):
+            for i in xrange(len(board)):
+                for j in xrange(len(board[0])):
+                    if(board[i][j] == '.'):
+                        for k in xrange(9):
+                            board[i][j] = chr(ord('1') + k)
+                            if isValid(board, i, j) and solver(board):
+                                return True
+                            board[i][j] = '.'
+                        return False
+            return True
 
-
-if __name__ == "__main__":
-    board = [['5', '3', '.', '.', '7', '.', '.', '.', '.'],
-             ['6', '.', '.', '1', '9', '5', '.', '.', '.'],
-             ['.', '9', '8', '.', '.', '.', '.', '6', '.'],
-             ['8', '.', '.', '.', '6', '.', '.', '.', '3'],
-             ['4', '.', '.', '8', '.', '3', '.', '.', '1'],
-             ['7', '.', '.', '.', '2', '.', '.', '.', '6'],
-             ['.', '6', '.', '.', '.', '.', '2', '8', '.'],
-             ['.', '.', '.', '4', '1', '9', '.', '.', '5'],
-             ['.', '.', '.', '.', '8', '.', '.', '7', '9']]
-    print Solution().solveSudoku(board)
+        solver(board)
