n-皇后以及全排列的问题--递归以及非递归的解法
首先说下全排序的问题? 这个问题可以说是最经典的问题，
?
实现这个问题的最经典的方法莫过于递归实现了：
?
代码确实很简洁：（从网上转载---很多的）
void perm(char *buf,int start,int end) { if(start==end){//当只要求对数组中一个字母进行全排列时，只要就按该数组输出即可 for(int i=0;i<=end;i++){ printf("%c",buf[i]); } printf("\n"); } else{//多个字母全排列 for(int i=start;i<=end;i++){ char temp=buf[start];//交换数组第一个元素与后续的元素 buf[start]=buf[i]; buf[i]=temp; perm(buf,start+1,end);//后续元素递归全排列 temp=buf[start];//将交换后的数组还原 buf[start]=buf[i]; buf[i]=temp; } } } ?简介带来的问题就是递归算法本身就不是很容易理解，另外一方面就是递归算法比较浪费内存空间。
?
? 首先就是perm(buf【】,start,end)实现数组的start的索引到end索引的全排序，每次我们需要从第一个元素与需要全排的索引的第一个交换，求解完后在替换回来。。。如此递归下去，只能说到这里了，再说下去我也很迷糊
这种递归算法也有缺点，就是它不能取出中间重复的序列，加入求1,2,2,3的全排列不能取出重复的? 需要另外的便利控制。。。
?
在网上看到一些全排序比较新颖的实现方法---字典序列的方法来就全排序
比如求3,1,2,4的全排列，
这种方法将这些序列进行了一个排序，比如得到全排序之后的的所有序列第一个序列是，1,2,3,4 最后一个序列是4,3,2,1
也就是递增的方法来查找序列，比如，3214的下一个序列就是3241
?
问题的关键就是如何调整这个数的 序列
方法如下：
1.首先对要求全排序的数列进行递增的排序，
2.从序列的最后端点开始查找这样的一个元素，这个元素比相邻的后面的元素小，记录下这个元素的下标i;
3.然后此时i后方的元素是整体递减的，所以我们直接从序列的最后方开始找比元素大的元素，并记录下标j；
4，然后swap（A[i]，A[j]）；
5，将元素i后方的所有元素逆转；
6.然后输出，新的序列
7.知道序列全部递减停止；
?
void swap(int *a,int *b) //交换{int tmp=*a;*a=*b;*b=tmp;}void revArr(int *arr,int k,int m) //数组arr 从k到m进行逆置{while(k<m){swap(arr+k,arr+m);k++;m--;}}void print(int *x,int n) //打印{for(int i=0;i<n;i++){ printf("%d ",x[i]);}printf("\n"); }int fullArr(int *arr,int n){if(n==1){return 1;}int i,j;while(1){ print(arr,n);for(i=n-2;i>=0;i--) {if(arr[i]<arr[i+1]) //从数组后方找到后一个数大于前一个数 记住下表i{break;}if(i==0){return 1;//函数结束出口}}for(j=n-1;j>i;j--) //在i后方找到一个数比i大而且最接近i的数，我们可以直接从后先前找，因为i后方的数都是升序的{if(arr[j]>arr[i]){break;}}swap(arr+i,arr+j); //交换i与j revArr(arr,i+1,n-1); //i后方的数逆置}}?
说到递归 不得不让人想起n-皇后问题。
?
问题描述，就是在一个n*n的棋盘上防止n个棋子，其中任何两个棋子不可以在同行，同列，同一斜线上出现。
?
解决这个问题的最经典思路就是回溯法：
在解空间内（树），根据剪枝函数（约束函数）来去除不合适的解路径（采用深度优先遍历的方式来遍历接空间树），找到合适的解路径；
?
首先定义一个长度为n的数组blank，初始化全为-1，每个元素代表第i行上防止棋子的列数。
?
剪枝函数的条件：if(x[j]==i||abs(x[j]-i)==abs(j-k)) return false；
?
从树第第一层开始，逐个向下查找，加入到k层，查找失败则返回带k-1层，继续查找。。直到最后blank[n-1]==n? 退出并返回
下面是非递归的实现--容易理解
?
void BackTrack(int *blank,int n)// n-皇后的非递归实现{ for(int i=0;i<n;i++) //初始化n-元组-- { blank[i]=0; } int k=0; while(blank[0]!=n) //当遍历到最后时，blank[0] 会自加到n { while(blank[k]<n&&!place(k,blank[k],blank)) //首先找到复合条件的点 { blank[k]++; } if(blank[k]<=n-1) { if(k==n-1) //遍历到最后一层 成功 { //成功 for(int j=0;j<n;j++) { printf("%d ",blank[j]); } printf("\n"); blank[k]++; } else //检查到下一个节点 { k++; blank[k]=0; } } else { k--; blank[k]++; } }}??