N皇后问题

N皇后是回溯算法经典问题之一。问题如下：请在一个n x n的正方形盘面上布置n名皇后，因为每一名皇后都可以自上下左右斜方向攻击，所以需保证每一行、每一列和每一条斜线上都只有一名皇后。

回溯算法可以用一句话概括：不撞南墙不回头，一撞南墙就回头。它采用了试错的思想。

如图所示，用1表示皇后，从第一个空格开始，把皇后放在格中。

只要盘面还有继续布置皇后的可能，就继续下去。当碰到盘面不成立或者没有布置可能的时候，再后退。因为第一行不能有两名皇后，所以从第二行继续。如图所示，假设第二名皇后在第二行第一个空格。

检查盘面，因为盘面不成立，所以改变第二名皇后的位置。

第二行的第二个空格也不可行，因为两名皇后将占用同一斜线。所以将第二名皇后放在第二行的第三个空格上，这时盘面是成立的。前进一行。

因为第三行皇后没有可行的位置。这时候碰到了“南墙”，所以后退一行。退回到第二行，将第二名皇后放在下一个空格上。因为盘面成立，所以再次前进到第三行

经过尝试，把第三名皇后放在第二个空格里。然而，来到第四行时，无可行选项。所以再次返回到第三行，单身第三行也无其他可行选项。此时除了后退到第二行没有其他选择，但第二名皇后已经在最后一个空格了，没有其他选项。

因此，后退到第一行，将第一名皇后换到下一个空格中。

重复以上步骤，最终会得到正确答案之一。

回溯算法思路是每一次只布置一个皇后，如果盘面可行，就继续布置下一个皇后。一旦盘面陷入死局，就返回一步，调整上一个皇后的位置。

# 输出所有成立的n·n盘面
def NQueens(n):
    # 检查盘面是否成立
    def checkBoard(rowIndex):
        for i in range(rowIndex):  # rowIndex是当前行数
            if cols[i] == cols[rowIndex]:  # 检查竖线
                return False

            if abs(cols[i] - cols[rowIndex]) == rowIndex - i:  # 检查斜线
                return False
        return True

    # 布置第rowIndex行到最后一行的皇后
    def helper(rowIndex):
        if rowIndex == n:  # 边界条件
            board = [[0 for _ in range(n)] for _ in range(n)]
            for i in range(n):
                board[i][cols[i]] = 1
            res.append(board)  # 把当前盘面加入结果列表
            return  # 返回
        for i in range(n):  # 依次尝试当前行的空格
            cols[rowIndex] = i
            if checkBoard(rowIndex):  # 检查当前盘面
                helper(rowIndex + 1)   # 进入下一行
    # _是一个常用的占位符，表示我们不关心这个位置的具体值
    cols = [0 for _ in range(n)]  # 每一行皇后的纵坐标
    res = []  # 结果列表
    helper(0)  # 从第1行开始
    return res

输入

result = NQueens(5)
for i in range(len(result)):
    print("第", i+1, "种解法")
    for j in range(len(result[i])):
        print(result[i][j])

输出