N皇后问题（Python实现）

article/2025/10/6 0:55:31

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 = 0for i in range(row):if abs(board[i]-col) == 0 or abs(board[i]-col) == abs(i-row):return Falsereturn Truedef eightqueen(board, row):border = len(board)if row >= border:for i,col in enumerate(board):print('□ ' * col + '■ ' + '□ ' * (len(board) - 1 - col))print("")col = 0while col < border:for col in range(border):if check(board, row, col):board[row] = coleightqueen(board, row+1)col += 1board = [0 for i in range(4)]
eightqueen(board, 0)

四皇后：两种情况