Python Straighforward Backtrack

  • 0
        def solveSudoku(self, board):
            def backtrack(board, memo, blanks, pos):
                if pos >= len(blanks): return True
                r, c = blanks[pos]
                for i in range(1,10):
                    s = str(i)
                    if (r,s) not in memo and (s,c) not in memo and (r//3,c//3,s) not in memo: 
                        board[r][c] = s
                        # add to set to indicate values have been used
                        memo.add((r,s)); memo.add((s,c)); memo.add((r//3,c//3,s))
                        if backtrack(board, memo, blanks, pos+1): return True
                        # removing values since current iteration is invalid
                        memo.remove((r,s)); memo.remove((s,c)); memo.remove((r//3,c//3,s))
            if not board: return 
            N, memo, blanks = len(board), set(), []
            for r in range(N):
                for c in range(N):
                    if board[r][c].isdigit(): 
                        # adding existing values to set
                        memo.add((r,board[r][c])); memo.add((board[r][c],c)); memo.add((r//3,c//3,board[r][c]))
                    # add to list of blanks to backtrack on
                    else: blanks.append((r,c))
            backtrack(board, memo, blanks, 0)

Log in to reply

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