n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

也就是说：存在一个N*N的棋盘，要放N个棋子，每个棋子不同行，不同列，不同（正反）对角线，如图：

 解题思路： 递归 + 回朔

首先我们要给定一个矩阵，来存放棋子，从第一行开始遍历，接着遍历这一行的每一列。假设我们在位置[1, 2]处已经放上棋子，我们开始遍历第二行，首先判断[2,1]位置存放棋子是否可行，调用check函数（稍后再说），显然与上一行棋子处于同一对角线，不行返回False,以此类推直到便利到位置[2,4]时这是一个可行的位置，再继续往下遍历。

总结的来说就是在遍历当前行时，之前行的棋子已经确定好了，从而以此判断该行的各个位置是否可行。

当然对于主函数来说我们需要一个递归终止的条件，很简单当当前行数大于N时，我们就已经得到了一个符合条件的矩阵。

除此之外，我们如果用矩阵存储，每次都要通过遍历来确定之前行棋子所在的位置，时间复杂度爆炸。所以这里做一个简化，我们用一个[1, n]的矩阵来存储，也就是说[row, col] = [i, board[i]]，这样我们只需要O(1)的时间复杂度就能知道上一行的信息。

再说check函数，首先我们是一行行进行遍历，一定不会存在同行的情况，同列也比较好判断，对于正负对角线，通过观察我们可以发现，我们设row，col为当前行当前列，那么对于位置[i, j]。如果符合等式|row- i| = |col-j|，那么[i, j]如[row, col]位于同一对角线。把上述两种情况合并，若果if abs(col - j) == 0 or abs(col - j) == abs(row-i)，那么[i, j]与[row, col]必处于同列或者同对角线上。

代码：

def check(board, row, col):
    i = 0
    for i in range(row):
        if abs(board[i]-col) == 0 or abs(board[i]-col) == abs(i-row):
            return False
    return True


def eightqueen(board, row):
    border = len(board)
    if row >= border:
        for i,col in enumerate(board):
            print('□ ' * col + '■ ' + '□ ' * (len(board) - 1 - col))
        print("")
    col = 0
    while col < border:
        for col in range(border):
            if check(board, row, col):
                board[row] = col
                eightqueen(board, row+1)
        col += 1



board = [0 for i in range(4)]
eightqueen(board, 0)

四皇后：两种情况

八皇后：92种情况