回溯法求n皇后问题（递归、非递归及优化）_求解n皇后问题(非递归回溯法) 分数 10 全屏浏览 切换布局 作者 王东 单位 贵州师

    n皇后问题是一个以国际象棋为背景的问题：在n×n的国际象棋棋盘上放置n个皇后，使得任何一个皇后都无法直接吃掉其他的皇后，即任意两个皇后都不能处于同一条横行、纵行或斜线上。

蛮力法思想：

    解决n皇后问题的思想本质上就是蛮力法，生成所有可能的摆放情况，并判断该情况是否满足要求，我们以树结构来表示解决问题的方法。以4*4的棋盘为例，第0层的根节点为空白的棋盘，第1层为只在棋盘的第一行摆放的四种不同情况，第2层是在第1层的基础上，摆放第二行的棋子，最后的叶子结点便是所有可能的完整摆放情况，共256种，但加上中途生成的不完整情况共1+4+16+64+256=340种。

回溯法思想：

    回溯法其实是以蛮力法为基础，只是不需要生成所有的情况，我们可以发现，在整棵树中，有些棋盘的摆放情况在未达到叶子结点时,便已经不满足n皇后的条件了，那么我们就没有必要再去往下摆放棋子（生成下一层的结点），而是直接回到该结点的父节点，生成新的情况进行判断。通过这种方法可以减少生成完全树中的一些不必要的子树，我们称之为“剪枝”。具体实现中回溯法与蛮力法的主要区别在于判断棋盘的代码所在的位置，蛮力法在摆放完所有皇后后再判断，回溯法在每摆放好一个皇后时就进行判断。