今天复习了回溯算法。N皇后问题是一个典型的需要用回溯算法来解决的问题。回溯算法可以用递归方法来实现，也可以用非递归方法来实现。用递归的方法来解决回溯的问题思路很清晰，但是耗费的内存资源较多，速度也较慢；非递归方法具有速度快和耗费较少内存资源的优点，但是程序的逻辑结构却很复杂——不过搞懂之后觉得也很简单。
在写非递归算法之前，参考了网上的一些文章，但是觉得那些程序都很晦涩难懂，而且存在一些问题，我索性自己写了一个，花了我不少时间。
递归实现：
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
/**//* 记录当前的放置方案 */
int *x;
/**//* 皇后的个数N 和 方案数目 */
int n,sum=0;
/**//* 检查参数所指示的这一行皇后放置方案是否满足要求 */
int Place(int);
/**//* 递归方法求取皇后放置方案*/
void Queen1(void);
/**//* 用户递归求取皇后放置方案的递归方法 */
void TraceBack(int);
/**//* 打印当前成功的放置方案 */
void PrintMethod(void);
void main(void)
{
long start,stop;
printf("input n: ");
scanf("%d",&n);
x=(int *)malloc(sizeof(int)*n);
time(&start);/**//*记录开始时间*/
Queen1();
time(&stop);/**//*记录结束时间*/
printf("\nmethod total %d \n",sum);
printf("\nuse %d seconds \n",(int)(stop-start));
}
int Place(int r)
{
int i;
for(i=0;i<r;i++){
if(x[r]==x[i] || abs(r-i)==abs(x[r]-x[i]))
return 0;
}
return 1;
}
void TraceBack(int r)
{
int i;
if(r>=n){
sum++;
/**//* PrintMethod(); */
}else{
for(i=0;i<n;i++){
x[r]=i;
if(Place(r)) TraceBack(r+1);
}
}
}
void PrintMethod(void)
{
int i,j;
printf("\nmethod %d\n",sum);
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(j==x[i]) printf("*");
else printf("#");
}
printf("\n");
}
}
void Queen1(void)
{
TraceBack(0);
}
非递归实现：
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
/**//* 记录当前的放置方案 */
int *x;
/**//* 皇后的个数N 和 方案数目 */
int n,sum=0;
/**//* 检查参数所指示的这一行皇后放置方案是否满足要求 */
int Place(int);
/**//* 非递归的方法求取皇后放置方案 */
void Queen2(void);
/**//* 打印当前成功的放置方案 */
void PrintMethod(void);
void main(void)
{
long start,stop;
printf("input n: ");
scanf("%d",&n);
x=(int *)malloc(sizeof(int)*n);
time(&start);/**//*记录开始时间*/
Queen2();
time(&stop);/**//*记录结束时间*/
printf("\nmethod total %d \n",sum);
printf("\nuse %d seconds \n",(int)(stop-start));
}
int Place(int r)
{
int i;
for(i=0;i<r;i++){
if(x[r]==x[i] || abs(r-i)==abs(x[r]-x[i]))
return 0;
}
return 1;
}
void Queen2(void)
{
int i,k;
for(i=0;i<n;i++)
x[i]=0;
k=0;
while(1){
if(x[k]>=n){
/**//* 如果当前第K行的放置位置超出了范围，那么检查该行是否为第0行
如果是第0行，说明所有的方案都已经遍历完毕，函数返回；否则回退到前一行
*/
if(k==0) break;
x[k]=0; /**//* 下次遍历的初始位置 */
k--; /**//* 返回上一行 */
x[k]++; /**//*下一种放置方案*/
}
else if(!Place(k)){
/**//* 如果当前第K行的放置方案不满足要求，采取下一种放置方案*/
x[k]++;
}
else{
if(k==(n-1)){
/**//* 如果已经是最后一行，那么表示已经成功得到一种放置方案*/
sum++;
/**//* PrintMethod(); */
x[k]=0; /**//*下次遍历的初始位置*/
k--; /**//*返回上一行*/
x[k]++; /**//*下一种放置方案*/
}else
k++; /**//* 否则开始配置下一行的皇后 */
}
}
}
void PrintMethod(void)
{
int i,j;
printf("\nmethod %d\n",sum);
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(j==x[i]) printf("*");
else printf("#");
}
printf("\n");
}
}
两种方法的性能比较：
N | 递归算法所用时间（秒） | 非递归算法所用时间（秒） |
13 | 6 | 6 |
14 | 37 | 35 |
15 | 267 | 254 |
从上面的数据可以看出，两种方法所用的时间相差并不大，但是递归算法所耗用的内存空间要比非递归算法大得多。因为我还不知道如何检测应用程序所用的内存空间的大小，所以无法给出准确的证明。