题解 | #N皇后问题#

N皇后问题-官方题解简化版

典型的回溯-排列问题，关键在于判断当前位置放皇后是否合法。最费力的方法是把与当前位置同列，左斜线，右斜线的所有坐标都遍历一遍，看这些坐标中是否已经有皇后了，但这样会涉及很多没有必要的访问。由于两个点（i,j）(m,n)在一条斜线上会满足，abs(i-m)=abs(j-n)的数学关系，那么通过当前点和之前皇后的坐标，就可以直接判断两点是否在一条斜线上。所以只需遍历已放置的皇后位置即可知道当前点是否可以放置一个皇后。

class Solution:
    def Nqueen(self , n: int) -> int:
        visited = []
        count = 0
        def available(row, col):
            for i, j in enumerate(visited):  # 列表内下标i代表行，元素j代表列
                if j == col or abs(j-col)==abs(i-row):   # 同列，在一条斜线上
                    return False
            return True
        def backTracking(i):
            nonlocal count
            if i == n:
                count += 1
                return
            for j in range(n):
                if available(i, j):
                    visited.append(j)    # 列表内下标代表行，元素代表列
                    backTracking(i+1)
                    visited.pop()
        backTracking(0)      
        return count