DFS python solution with sets


  • 0
    S

    Use three sets to track the available choices for each row/column/square.

    class Solution(object):
        def solveSudoku(self, board):
            row_remain = [set(xrange(1,10)) for _ in xrange(9)]
            col_remain = [set(xrange(1,10)) for _ in xrange(9)]
            sqr_remain = [set(xrange(1,10)) for _ in xrange(9)]
            # Find available remaining choices
            count = 0
            for i in xrange(9):
                for j in xrange(9):
                    if board[i][j] != '.':
                        val = int(board[i][j])
                        row_remain[i].discard(val)
                        col_remain[j].discard(val)
                        sqr_remain[i/3*3+j/3].discard(val)
                    else:
                        count += 1
            
            
            # backtracking search
            def dfs(i, j, count):
                if count == 0:
                    return 1
                # Find first blank in the board
                while board[i][j] != '.':
                    if j == 8:
                        i += 1
                        j = 0
                    else:
                        j += 1
                available = row_remain[i] & col_remain[j] & sqr_remain[i/3*3+j/3]
                for choice in available:
                    board[i][j] = str(choice)
                    row_remain[i].discard(choice)
                    col_remain[j].discard(choice)
                    sqr_remain[i/3*3+j/3].discard(choice)
                    if dfs(i, j, count - 1):
                        return 1
                    row_remain[i].add(choice)
                    col_remain[j].add(choice)
                    sqr_remain[i/3*3+j/3].add(choice)
                    board[i][j] = '.'
                return 0
    
            dfs(0, 0, count)
    

Log in to reply
 

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