N皇后问题

N皇后是经典回溯问题，详见leetcode.51 N皇后
本文代码来自leetcode官方解答，个人觉得写得很干练，很易懂，因此做个记录。

在做这个题之前需要先弄清一个概念，皇后的攻击范围，指的是该皇后所在的行，列，主对角线，次对角线。
因此我们可以采用递归的方法，对每一行做遍历。
然后有一个技巧性的东西就是，可以用两个2N-1长度的列表来分别表示主对角线和次对角线，因为主对角线和次对角线都分别有2N-1条，然后在每条主对角线上都有row-col==常数，且每条对角线对应的常数N不同（-N到N）；每条次对角线上有row+col==常数，且每条对角线对应的常数N不同（0到2N）。
因此在对每一行进行递归的基础上，我们检查改行上的每一个点的所在列，主对角线，次对角线是否可行即可。
直到我们递归到行数row+1==N,依然能找到可行位置，那么就把该方案加入到输出列表中。
主函数体如下：

def backtrack(row = 0):                        #默认参数从第0行开始
            for col in range(n):               #从0开始检查每一列
                if could_place(row, col):      #如果可以放置
                    place_queen(row, col)      #放置该皇后，即将该位置所在列，主对角线，次对角线均标记为1
                    if row + 1 == n:           #如果如果满足条件的已经有N个皇后了就将该方案添加到输出中
                        add_solution()
                    else:                
                        backtrack(row + 1)     #否则递归继续搜寻下一行
                    remove_queen(row, col)     #记得回溯，我们要试每一行每一个可能满足的位置

其中涉及到几个函数

1.检查能否放置

#这里对于我这个菜鸡来说很巧妙，只要列，主对角线，次对角线中有任意一个为1，就会返回0，代表不能放置
#好好学习下这种用法
def could_place(row, col):
            return not (cols[col] + hill_diagonals[row + col] + dale_diagonals[row - col])

2.放置该皇后，即将改位置所在列，主对角线，次对角线全部置1

def place_queen(row, col):
            queens.add((row, col))      #这里记得把改点加入到集合中，方便回溯时移除，以方便得到最后的输出
            cols[col] = 1
            hill_diagonals[row + col] = 1
            dale_diagonals[row - col] = 1

3.移除皇后，用在回溯过程，与放置皇后相反的过程

def remove_queen(row, col):
            queens.remove((row, col))
            cols[col] = 0
            hill_diagonals[row + col] = 0
            dale_diagonals[row - col] = 0

4.当有N个皇后满足了，就按输出要求将该方案添加到输出列表

def add_solution():
            solution = []
            for _, col in sorted(queens):
                solution.append('.' * col + 'Q' + '.' * (n - col - 1))
            output.append(solution)

最终的完整程序如下

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def could_place(row, col):
            return not (cols[col] + hill_diagonals[row + col] + dale_diagonals[row - col])
        
        def place_queen(row, col):
            queens.add((row, col))
            cols[col] = 1
            hill_diagonals[row + col] = 1
            dale_diagonals[row - col] = 1
        
        def remove_queen(row, col):
            queens.remove((row, col))
            cols[col] = 0
            hill_diagonals[row + col] = 0
            dale_diagonals[row - col] = 0
        
        def add_solution():
            solution = []
            for _, col in sorted(queens):
                solution.append('.' * col + 'Q' + '.' * (n - col - 1))
            output.append(solution)
        
        def backtrack(row = 0):
            for col in range(n):
                if could_place(row, col):
                    place_queen(row, col)
                    if row + 1 == n:
                        add_solution()
                    else:
                        backtrack(row + 1)
                    remove_queen(row, col)

        
        cols = [0] * n
        hill_diagonals = [0] * (2 * n - 1)
        dale_diagonals = [0] * (2 * n - 1)
        queens = set()
        output = []
        backtrack()
        return output