Leetcode: interview question 08.12 Eight queens [DFS + backtrack]

analysis

Define a function to generate the current queens Result
then queens Used to record each line of queen Where are they
backtrack Used to record the current second i Yes queen Where's your location
If at present i = n You can add the final result
Otherwise start traversing each j, If the current ij Satisfy cols diag1 and diag2 You can take this j
Then we set queen And add three set
then dfs The next layer Go back to the previous set Go over the next j

ac code

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        # backtrack + set
        row = ['.'] * n
        queens = [-1] * n
        cols, diag1, diag2 = set(), set(), set()
        ans = []

        def generateBoard():
            board = []
            for i in range(n):
                row[queens[i]] = 'Q'
                board.append(''.join(row))
                row[queens[i]] = '.'
            return board
        
        def backtrack(i):
            if i == n:
                ans.append(generateBoard())
            else:
                # next row which col
                for j in range(n):
                    if j in cols or i + j in diag1 or i - j in diag2:
                        continue
                    # dfs + backtrack
                    queens[i] = j
                    cols.add(j)
                    diag1.add(i + j)
                    diag2.add(i - j)
                    backtrack(i + 1)
                    cols.remove(j)
                    diag1.remove(i + j)
                    diag2.remove(i - j)
        
        backtrack(0)
        return ans

summary

dfs + backtrack The complexity of is not n Of n Power A lot of them have been pruned in the middle
Complexity is o(N!)