回溯法

回溯法

在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。

                                  

利用回溯法：

回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。 回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。

解法

(1)针对所给问题，定义问题的解空间；

(2)确定易于搜索的解空间结构（递归树）；

(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

一般递归代码如下:

void backtrack(int t)//传递值通过参数
{if (t>n) output(x);elsefor (int i=f(n,t);i<=g(n,t);i++) {x[t]=h(i);//记录中间结果！if (constraint(t)&&bound(t)) backtrack(t+1);//限制条件加边界}
}

迭代代码

void iterativeBacktrack ()
{int t=1;while (t>0) {if (f(n,t)<=g(n,t)) for (int i=f(n,t);i<=g(n,t);i++) {x[t]=h(i);if (constraint(t)&&bound(t)) {if (solution(t)) output(x);else t++;}}else t--;}

此n皇后问题分析

1、解空间（0，n-1）

2、结构为一递归树，基本上每个有n个子节点

3、减枝函数为：不能同行，同列，对角线上

如何规划n*n的空间呢？

----令解空间为A[i] ----值范围为：0-n-1。列为i,用level表示当前层次

(S[i] == val || abs(S[i]-val) == abs(i-level)) //同列，对角线上，此种方法不会出现同行故未考虑

以下为实现代码：

#include <iostream>
#include <cmath>
using namespace std;int count_path();
void print_path(int S[],int n);
bool check(int level,int val,int S[]);
void trace_path(int n,int level,int S[]);
void nqueen(int n);int main()
{int n(0);cout<<"please input n";cout<<endl;cin>>n;nqueen(n);cout<<count_path()-1;return 0;
}bool check(int level,int val,int S[])
{for (int i = 0;i < level ;i++){if (S[i] == val || abs(S[i]-val) == abs(i-level)){return false;}}return true;
}void trace_path(int n,int level,int S[])
{if(level >= n){cout<<"find path:";print_path(S,n);count_path();cout<<endl;return ;}else{for(int i = 0 ;i < n;i++){if(check(level,i,S)){S[level] = i;trace_path(n,level+1,S);}}}}void nqueen(int n)
{if (n > 20){cout<< "值太大！小于20."<<endl;return ;}int *S = new int [n];trace_path(n,0,S);
}void print_path(int S[],int n)
{for (int i = 0;i < n;i++){cout<<S[i]<<"t";}
}
int count_path()
{static int count = 0;count++;return count;
}

测试：

please input n = 4
2
find path:1     3       0       2
find path:2     0       3       1

please input n = 6
4
find path:1     3       5       0       2       4
find path:2     5       1       4       0       3
find path:3     0       4       1       5       2
find path:4     2       0       5       3       1

please input n = 3
0

结果太多略：
please input n = 8
92
please input n = 7
40