带着问题学算法之回溯法与八皇后问题

八皇后问题描述：在国际象棋棋盘上（8*8）放置八个皇后，使得任意两个皇后之间不能在同一行，同一列，也不能位于同于对角线上。问共有多少种不同的方法，并且指出各种不同的放法。

数据表示：用一个数组x[9]来存放数据，x[0]为0，表示八叉树（类比二叉树）的根节点，x[1]到x[8]表示皇后摆放位置，取值都为1到8，如x[i]=j表示第i行的皇后放在第j列。

解题策略：首先我们分析一下问题的解，我们每取出一个皇后，放入一行，共有八种不同的放法，然后再放第二个皇后，同样如果不考虑规则，还是有八种放法。于是我们可以用一个八叉树来描述这个过程。从根节点开始，树每增加一层，便是多放一个皇后，直到第8层（根节点为0层），最后得到一个完全八叉树。　　　　紧接着我们开始用深度优先遍历这个八叉树，在遍历的过程中，进行相应的条件的判断。以便去掉不合规则的子树。　　那么具体用什么条件来进行子树的裁剪呢？主要有两个条件，一是不同行的皇后不在同一列，即x[i]!=x[j]，二是不同行的皇后不在同一个对角，即abs(i-j)!=abs(x[i]-x[j])。只有同时满足这两个条件，才可以继续下一行，否则进行回溯（返回到前一行进行判断）。

代码实现：用递归实现八叉树的遍历