Accepted Python solution


  • 9
    X
    class Solution:
        # @param board, a 9x9 2D array
        # Solve the Sudoku by modifying the input board in-place.
        # Do not return any value.
        def solveSudoku(self, board):
            self.board = board
            self.solve()
        
        def findUnassigned(self):
            for row in range(9):
                for col in range(9):
                    if self.board[row][col] == ".":
                        return row, col
            return -1, -1
        
        def solve(self):
            row, col = self.findUnassigned()
            #no unassigned position is found, puzzle solved
            if row == -1 and col == -1:
                return True
            for num in ["1","2","3","4","5","6","7","8","9"]:
                if self.isSafe(row, col, num):
                    self.board[row][col] = num
                    if self.solve():
                        return True
                    self.board[row][col] = "."
            return False
                
        def isSafe(self, row, col, ch):
            boxrow = row - row%3
            boxcol = col - col%3
            if self.checkrow(row,ch) and self.checkcol(col,ch) and self.checksquare(boxrow, boxcol, ch):
                return True
            return False
        
        def checkrow(self, row, ch):
            for col in range(9):
                if self.board[row][col] == ch:
                    return False
            return True
        
        def checkcol(self, col, ch):
            for row in range(9):
                if self.board[row][col] == ch:
                    return False
            return True
           
        def checksquare(self, row, col, ch):
            for r in range(row, row+3):
                for c in range(col, col+3):
                    if self.board[r][c] == ch:
                        return False
            return True
    

    It's a simple backtracking solution.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.