51. N皇后

https://leetcode-cn.com/problems/n-queens/

解法一：回溯

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。皇后的走法：可以到达横向、纵向和斜线（45度，135度）的任意距离。

核心方法是判断指定（i，j）位置能否放，能放就递归i+1的所有列，不能放就回溯

因为是一行行从上往下填的，因此判断函数只需要判断上方的棋盘，即同一列，以及左上和右上方向。

用到了python的多变量for循环，用zip函数。注意循环的终点以范围最短的为准：

>>> for i,j,k in zip(range(9), range(1,9), range(2,11)):  #每次对三个变量分别循环
...    print(i,j,k)
... 
0 1 2
1 2 3
2 3 4
3 4 5
4 5 6
5 6 7
6 7 8
7 8 9  #j先到达终点，所有变量一起结束

此外由于回溯棋盘时，string的元素不能修改，因此用一个二维字符列表，而不是一维string列表来表示棋盘。而最终结果要求一个一维string列表，因此得到的结果还需要转换，将字符列表转为string，用join函数

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        self.record = []
        board = [['.'] * n for _ in range(n)]   #注意二维列表的创建方式
        self.solve(board, 0, n)
        return self.record

    def solve(self, board, i, n):
        if i == n:    #来到最后一行，得到一个结果
            res = [] 
            for k in range(n):
                res.append(''.join(board[k]))   #将棋盘每行转为一个string填入结果
            self.record.append(res)

        for j in range(n):
            if self.isValid(board, i, j, n):    #若合法则填入，并递归进入下一行
                board[i][j] = 'Q'
                self.solve(board, i+1, n)
                board[i][j] = '.'    #还原现场

    def isValid(self, board, row, col, n): #判断row，col位置是否合法
        #判断同一列
         for i in range(row-1, -1, -1):
            if board[i][col] == 'Q':    
                return False
        #判断左上方向
        for i, j in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):
            if board[i][j] == 'Q':
                return False
        #判断右上方向
        for i, j in zip(range(row - 1, -1, -1), range(col + 1, n)):
            if board[i][j] == 'Q':
                return False
        return True

2021.9.12优化

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        record = []
        board = [['.'] * n for _ in range(n)]   #注意二维列表的创建方式
        #判断row，col位置是否合法
        def isvalid(board, row, col, n):
            #向上搜索同一列
            for i in range(row-1, -1, -1):
                if board[i][col] == 'Q':
                    return False
            #左上
            for i,j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
                if board[i][j] == 'Q':
                    return False
            #右上
            for i,j in zip(range(row-1, -1, -1), range(col+1, n)):
                if board[i][j] == 'Q':
                    return False
            return True
        #从i行开始遍历棋盘
        def solve(board, i, n):
            #递归出口
            if i == n:
                res = []
                for k in range(n):
                    res.append(''.join(board[k]))
                record.append(res)
                return
            for j in range(n):
                if not isvalid(board, i, j, n):
                    continue
                board[i][j] = 'Q'
                solve(board, i+1, n)    #递归找下一行
                board[i][j] = '.'   #重置

        solve(board, 0, n)
        return record