[backtracking method] queen n problem

Leetcode N queens problem to flash back
Topic link : https://leetcode-cn.com/problems/n-queens/.

1. backtracking

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        #  Determine whether there is a conflict 
        def isok(r, c, lis):
            #  Column 
            for i in range(len(lis)):
                if lis[i][c] == 'Q':
                    return False

            #  Upper right corner 
            i = r - 1
            j = c + 1
            while 0 <= i and j < len(lis):
                if lis[i][j] == 'Q':
                    return False
                i -= 1
                j += 1

            #  top left corner 
            i = r - 1
            j = c - 1
            while 0 <= i and 0 <= j:
                if lis[i][j] == 'Q':
                    return False
                i -= 1
                j -= 1
            return True

        def backtracking(lis, r, n):
            if r == n:  #  When the number of rows traversed is equal to n Equality means that a result is found 
                path = []
                for i in lis:  #  The installation topic requires that the results be loaded into res
                    path_str = "".join(i)
                    path.append(path_str)
                res.append(path)

            for c in range(n):  #  Ergodic column 
                if isok(r, c, lis):  #  If there is no conflict 
                    lis[r][c] = 'Q'  #  Place the queen in this position 
                    backtracking(lis, r + 1, n)  #  Recursively traverse the next line ,
                    lis[r][c] = '.'  #  to flash back , Undo the queen 

        if n == 1:
            return [['Q']]
        lis = [['.' for i in range(n)] for i in range(n)]  #  Create a chessboard 
        res = []  #  Store results 
        backtracking(lis, 0, n)
        return res

• If you only consider not being in the same column, the first row has n Planting , The second line has n-1 Planting , The third line n-2···. So the time complexity is O(n!), Actually consider the case of slashes , Less time complexity
• Suppose the total time complexity is O(n!), But this is just the time complexity of traversing all the cases , There is no time complexity to judge whether the location is reasonable . From the above code, we can see that the function to determine the position also uses a loop , The time complexity of judgment is not O(1)
• Therefore, the part of judging whether the position is reasonable can be optimized , Using collections to implement O(1) Time to judge .

2. Set based backtracking

• About column represents Queen Information ：
  for example 4*4 The chessboard has two results
  [1, 3, 0, 2]
  “.Q. .”,
  “…Q”,
  “Q…”,
  “. .Q.”

  [2, 0, 3, 1]
  “. .Q.”,
  “Q…”,
  “…Q”,
  “.Q. .”
  Here you can see the array subscript +1 It stands for the line , Elements +1 Represents a column ,[1, 3, 0, 2] in 1 Refer to ： The queen is in the first row and the second column . In this way, the information storage mode can be compressed to one dimension

• The diagonals from the top left to the bottom right can be regarded as Chinese character strokes ‘ si ’ The following code variable name is used na Substitute for easy to understand

• Similarly, from top right to bottom left, it can be seen as ‘ skimming ’ pie

• From top left to bottom right , Each position on the same slash satisfies that the difference between row subscript and column subscript is equal

• Top right to bottom left , Each position on the same slash satisfies that the sum of row subscripts and column subscripts is equal

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def getBoard(n, queens):   #  According to the records  queens, Generate the corresponding chessboard 
            board = []
            row = ["."] * n     #  Record the exact position of the queen in a line （ for example ,'.Q..'  Express   Queen   Located at 1 Column ）
            for i in range(n):          #  Traverse n A queen 
                row[queens[i]] = "Q"    #  Will be the first i Queens in the column  queens[i]  On 
                board.append("".join(row))
                row[queens[i]] = "."
            return board
        
        def backtracking(i, n):    #  In the  i  That's ok  [0, n-1]  Place the queen 
            if i == n:          #  Find a reasonable result 
                res.append(getBoard(n, queens))
            else:                   #  In the  i  OK, place the queen ,
                for j in range(n):  #  Traverse the row  [0, n-1]  List to see if there is an appropriate solution 
                    if j in cols or i - j in na or i + j in pie:
                        continue    #  The first  i  Queens cannot be placed in  j  Column , namely  (i,j)  It's about , Then skip 
                    queens[i] = j   
                    cols.add(j)         #  Put the current position  (i,j)  Add to the occupied location information 
                    na.add(i - j)
                    pie.add(i + j)           
                    backtracking(i + 1, n)    #  Calculate the next line , That is to say  i+1  That's ok  
                    cols.remove(j)      #  to flash back   Undo the queen 
                    na.remove(i - j)
                    pie.remove(i + j)
    
        res = []
        queens = [-1] * n   #  Every   Queen   Number of columns placed  [0, n-1]
        cols = set()        #  Record column 
        na = set()       #  Record the main diagonal  ( From top left to bottom right ) x-y = const 
        pie = set()       #  Record the secondary diagonal  ( Top right to bottom left ) x+y = const
        backtracking(0, n)     #  From  0  OK, start placing the queen 
        return res

After the test , The set based backtracking method is at least less than the ordinary backtracking method 1/3 Time for
Of course, there are also backtracking methods based on bit operations , It is optimal in both time and space ,
See this article for details 【 Backtracking based on bit operation 】N queens problem 2