题解 | #N皇后问题#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型 the n
# @return int整型
#
from copy import deepcopy
class Solution:
    res = []

    def isValid(self, n, row, col, Queen):
        # 判断同一列是否有皇后
        i = 0
        j = col
        while i < row:
            if Queen[i][j] == "True":
                return False
            i += 1

        i, j = row, col
        # 判断45度角，是否有皇后

        while i-1 >= 0 and j-1 >=0:
            if Queen[i - 1][j - 1] == "True":
                return False
            i -= 1
            j -= 1

        # 判断135度角是否有皇后
        n = n
        i, j = row, col
        while i-1 >= 0 and j+1 <= n-1:
            #添加的时候True是字符串，要加引号
            if Queen[i-1][j+1] == "True":
                return False
            i -= 1
            j += 1

        return True

    def backtrace(self, n, row, Queen):
        # row=n停止递归，能到第n行说明了整个棋盘走完了
        if row == n:
            #添加Queue，由于Queue是列表，要添加Queue的拷贝对象进去，后面棋盘就变了，会影响到res的结果
            new=deepcopy(Queen)
            self.res.append(new)

            #递归终止后务必记得反馈回
            return

        # i代表列数，遍历row的每一列
        for i in range(n):
            if self.isValid(n, row, i, Queen):
                Queen[row][i] = "True"
                #将下一列传入，遍历函数
                self.backtrace(n, row + 1, Queen)
                Queen[row][i] = "False"

    def Nqueen(self, n: int) -> int:
        # write code here
        # 初始化Queen，就是棋盘的大小
        Queen = [["False" for i in range(n)] for i in range(n)]
        # 初始化row=0
        self.backtrace(n, 0, Queen)
        #print(self.res)
        for x in self.res:
          print()
          for i in range(n):
              print(x[i])

        return len(self.res)