八皇后的来源
八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上 。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n 。当且仅当n = 1或n ≥ 4时问题有解 。
八皇后问题最早是由国际象棋棋手马克斯·贝瑟尔（Max ）于1848年提出 。第一个解在1850年由弗朗兹·诺克（Franz Nauck）给出 。并且将其推广为更一般的n皇后摆放问题 。诺克也是首先将问题推广到更一般的n皇后摆放问题的人之一 。
问题分析
我们先不看8皇后，我们先来看一下4皇后，其实原理都是一样的，比如在下面的4*4的格子里，如果我们在其中一个格子里输入了皇后，那么在这一行这一列和这左右两边的对角线上都不能有皇后 。
所以有一种方式就是我们一个个去试
第一行
比如我们在第一行第一列输入了一个皇后
第二行
第二行我们就不能在第一列和第二列输入皇后了，因为有冲突了 。但我们可以在第3列输入皇后
第三行
第三行我们发现在任何位置输入都会有冲突 。这说明我们之前选择的是错误的，再回到上一步，我们发现第二步不光能选择第3列，而且还能选择第4列，既然选择第3列不合适，那我们就选择第4列吧
第二行（重新选择）
第二行我们选择第4列
第三行（重新选择）
第3行我们只有选择第2列不会有冲突
第四行
我们发现第4行又没有可选择的了 。第一次重试失败
第二次重试
到这里我们只有重新回到第一步了，这说明我们之前第一行选择第一列是无解的，所以我们第一行不应该选择第一列，我们再来选择第二列来试试
第一行
这一行我们选择第2列
第二行
第二行我们前3个都不能选，只能选第4列
第三行
第三行我们只能选第1列
第四行
第四行我们只能选第3列
最后我们终于找到了一组解 。除了这组解还有没有其他解呢，肯定还是有的，因为4皇后是有两组解的，这里我们就不在一个个试了 。
我们来看一下他查找的过程，就是先从第1行的第1列开始往下找，然后再从第1行的第2列……，一直到第1行的第n列 。代码该怎么写呢，看到这里估计大家都已经想到了，这不就是一棵N叉树的前序遍历吗，我们来看下，是不是下面这样的 。
我们先来看一下二叉树的前序遍历怎么写，不明白的可以参考下373，数据结构-6,树
public static void preOrder(TreeNode tree) {if (tree == null)return;System.out.printf(tree.val + "");preOrder(tree.left);preOrder(tree.right);}
二叉树是有两个子节点，那么N叉树当然是有N个子节点了，所以N叉树的前序遍历是这样的
public static void preOrder(TreeNode tree) {if (tree == null)return;System.out.printf(tree.val + "");preOrder("第1个子节点");preOrder("第2个子节点");……preOrder("第n个子节点");}
文章插图
如果N是一个很大的值，这样写要写死人了，我们一般使用循环的方式
public static void preOrder(TreeNode tree) {if (tree == null)return;System.out.printf(tree.val + "");for (int i = 0; i preOrder("第i个子节点");
- IB数学课程复习指南
- PTN950设备的LPT功能
- 如何比较两个PDF文件的不同？在手机上如何处理？
- 祛痘疤最好的产品,祛痘疤最好的产品
- 专升本热门专业排行榜,广州自考专升本热门专业的课程有哪些
- 祛黑头收缩毛孔的面膜排名,什么面膜去黑头收缩毛孔最好
- 神仙武力排行榜,中国神仙的武力排行
- 专利多个实施例,专利的实施例与比较例的区别
- 神仙兵器排行榜,古代神仙的武器都有哪些？
- 专利审查指南,新的专利审查指南什么时候出版