Python code using backtracking


  • 0
    H
    class Solution(object):
        def solveSudoku(self, board):
            """
            :type board: List[List[str]]
            :rtype: void Do not return anything, modify board in-place instead.
            """
            def check(board, x, y, ch):
                '''
                check the board if we try to assign the 'blank' grid board[x][y] as 'ch' 
                '''
                n = 9
                for i in range(0, n):
                    if board[i][y] == ch:   # check the row that board[x][y] belongs to
                        return False
                    if board[x][i] == ch:   # check the col that board[x][y] belongs to 
                        return False
                    if board[(x//3)*3 + i//3][(y//3)*3 + i%3] == ch:    # check the sub box that board[x][y] belongs to
                        return False
                return True
                
            def fill_board(board, posi, index):
                '''
                backtracking
                '''
                if index == len(posi):
                    return True 
                # try to fill the grid
                x, y = posi[index]  # unpack the position of current blank grid
                for digit in list('123456789'):    
                    if check(board, x, y, digit):   # try to assign board[x][y] as 'digit'. If it is ok, assign it.
                        board[x][y] = digit 
                        # fill the next blank grid
                        if fill_board(board, posi, index+1):    # actually, 'True' means all the following blank grids are correctly assigned.
                            return True
                        else:
                            board[x][y] = '.'   # otherwise, go back (recover board[x][y] to '.')
                # it has not returned, so this branch is not possible              
                return False   
            
            n = 9
            # find all '.' girds and record their positions
            posi = []
            for i in range(n):
                for j in range(n):
                    if board[i][j]=='.':
                        posi.append((i, j))
            fill_board(board, posi, 0)
            return
    

Log in to reply
 

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