1. 问题描述

在 8 * 8 的国际象棋棋盘上摆放八个皇后，任意两个皇后不能处于同一行、同一列或同一斜线上，请求出所有的摆法。

2. 算法描述

用回溯算法来考虑此问题，在放置皇后之前判断该位置是否会产生冲突。有冲突就继续判断下一个位置，没有冲突就就移到下一行放置。用这种办法，当子节点穷举完发现都没有，回到原来的节点，选择另一个分支。用这种方法，不重复，不遗漏。用矩阵来表示皇后摆放的位置，因篇幅有限，我们这里设置 4 * 4 的矩阵来模拟算法。
在这里插入图片描述
用 4*4 的矩阵来表示棋盘的位置，会占用相当一部分的空间，为改进算法，我们用一个一位数组来存储这个矩阵。用数组中元素的位置来代表矩阵的行，用数组元素的内容来代表矩阵的列。那么，矩阵的遍历过程就是 1，2，3，4 的排列组合。我们可以得到如图所示的树状图。
在这里插入图片描述
有冲突解决冲突，没有冲突往前走，无路可走往回退，走到最后是答案。为了加快有无冲突的判断速度，可以给每行和两个方向的每条对角线是否有皇后占据建立标志数组。放下一个新皇后做标志，回溯时挪动一个旧皇后清除标志。这里我们用递归的方法实现该算法。

3. 代码实现

// An highlighted block
#八皇后问题 
def solveNQ(board,row,count): if row >= 8: count[0] = count[0] + 1 print("-------------第",count[0],"个-----------------") 		print_board(board) return True; for col in range(8): if is_Safe(board,row,col): board[row] = col if solveNQ(board,row+1,count): pass return False def is_Safe(board,row,col): i = 0 while i < row: if abs(col-board[i]) in [0,abs(row-i)]: return False i = i + 1 return True def print_board(board): import sys for i,col in enumerate(board): sys.stdout.write('□ ' * col + '■ ' + '□ ' * (len(board) - 1 - col)) print('') if __name__ == "__main__": count = [0] board = [0,0,0,0,0,0,0,0] solveNQ(board,0,count) print("该问题总共有",count,"个解")

4. 总结

运行结果显示，将八皇后的放置位置在棋盘上打印出来，并记录其结果总数，结果显示八皇后问题一共有 92 种解。
在这里插入图片描述

参考和致谢

八皇后问题_百度百科 https://baike.baidu.com/item/八皇后问题/11053477?fr=aladdin
漫画：什么是八皇后问题？ https://blog.csdn.net/csdnsevenn/article/details/79607688
关于穷举：算法课堂内容记录 https://blog.csdn.net/weixin_45439696/article/details/110141797