80ms python code, use dfs with choice


  • 3
    T
    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):
        res = self.dfs(board)
        for n, row in enumerate(res):
            board[n] = ''.join(row)
    
    def dfs(self, board):
        stack = [board]
        while stack:
            s = stack.pop()
            result = self.fill_board(s)
            if result == 'complete':
                return s
            for r in result:
                stack.append(r)
                
    def fill_board(self, board):
        digits = set('123456789')
        choice, best = {}, []
        for j in range(9):
            for i in range(9):
                if board[j][i] == '.':
                    square = {board[j//3*3+y][i//3*3+x]
                              for y in range(3) for x in range(3)}
                    row = {board[j][x] for x in range(9)}
                    col = {board[y][i] for y in range(9)}
                    rest = digits.difference(square, row, col)
                    if len(rest) == 1:
                        board[j][i] = rest.pop()
                        return self.fill_board(board)
                    elif len(rest) == 0:
                        return ''
                    else:
                        choice[(j, i)] = rest
        if not choice:
            return 'complete'
        y, x = min(choice, key=lambda k: len(choice[k]))
        for n in choice[(y, x)]:
            b = copy.deepcopy(board)
            b[y][x] = n
            best.append(b)
        return best
    

    Every time we find a '.', we store the possible numbers we can choice in a dict,

    if the possible numbers is only one, we fill the board first and refill the board from beginning,

    and last , we choose a position where the possible numbers is least to continue search


Log in to reply
 

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