这一题也是路径问题，那也要从树的概念去分析。根据每行每列都不能重复，得到每行每列最多1个棋子；又根据棋子数等于边长N，得到每行每列最少1个棋子；因此每行每列只能是1个棋子。

　　首先忽略过滤条件，第一行的1个棋子有N种可能，每一种可能就是一棵N叉树，一共有N层，这N棵树就构成了森林，这个森林的子叶数量就是方案数了。

　　程序代码：

　　运行结果：

　　可见，如果没有过滤条件，方案数是非常惊人的。现在我们考虑过滤条件。第一和二过滤条件比较简单，第三个条件就有点复杂了，因为条件里没有数量关系。那么我们得把第三个条件转化为数量的关系。从函数图像中可以知道对角线的倾角是±45°，即正切值是±1。由于下一层节点的行数都大于它的上层节点的行数，这样，第三个条件就转化为：当前节点的列数减它的祖先的列数之差的绝对值不等于它的行数减它的祖先的行数之差。为了回溯检查，每个节点增加它的父节点指针。

　　程序代码：

　　运行结果：

　　N等于8，这正是“八皇后问题”。下面是使用树的递归遍历算法的程序，请在有“#”号的地方加上注释，使程序更加容易被人看懂。

---

添加 家长论坛微信