回 溯 法
回溯算法实际是一个类似枚举的搜索尝试方法，它的主题思想是在搜索尝试中找问题的解，当不满足求解条件就”回溯”返回，尝试别的路径。回溯算法是尝试搜索算法中最为基本的一种算法，其采用了一种“走不通就掉头”的思想，作为其控制结构。
【例1】八皇后问题模型建立
要在8*8的国际象棋棋盘中放八个皇后，使任意两个皇后都不能互相吃掉。规则：皇后能吃掉同一行、同一列、同一对角线的任意棋子。如图5-12为一种方案，求所有的解。
模型建立
不妨设八个皇后为xi，她们分别在第i行（i=1，2，3，4……，8），这样问题的解空间，就是一个八个皇后所在列的序号，为n元一维向量（x1,x2,x3,x4,x5,x6,x7,x8）,搜索空间是1≤xi≤8（i=1，2，3，4……，8），共88个状态。约束条件是八个（1,x1）,(2,x2) ,(3,x3),(4,x4) ,(5,x5), (6,x6) , (7,x7), (8,x8)不在同一行、同一列和同一对角线上。
虽然问题共有88个状态，但算法不会真正地搜索这么多的状态，因为前面已经说明，回溯法采用的是“走不通就掉头”的策略，而形如(1,1,x3,x4, x5,x6,x7,x8）的状态共有86个，由于1，2号皇后
在同一列不满足约束条件，回溯后这86个状态是不会搜索的。
算法设计1：加约束条件的枚举算法
最简单的算法就是通过八重循环模拟搜索空间中的88个状态，按深度优先思想，从第一个皇后从第一列开始搜索，每前进一步检查是否满足约束条件,不满足时，用continue语句回溯，满足满足约束条件，开始下一层循环，直到找出问题的解。
约束条件不在同一列的表达式为xi xj；而在同一主对角线上时xi-i=xj-j, 在同一负对角线上时xi+i=xj+j，因此，不在同一对角线上的约束条件表示为abs(xi-xj) abs(i-j)（abs（）取绝对值）。
算法1：
queen1（ ）{int a[9]; for (a[1]=1;a[1]