八皇后之回溯法解决[转]

问题描述：

要在8*8的国际象棋棋盘中放8个皇后，使任意两个皇后都不能互相吃掉。规则是皇后能吃掉同一行、同一列、同一对角线的棋子。如下图即是两种方案：

、

解决方案：

8*8的棋盘要摆放8个皇后，且不能同行同列同对角线，那么每行必定会有一个皇后。我们可以设一个数组a用来存放每一行皇后的位置，元素值表示第几列（如a[1]=5表示第一行的皇后处于第五个格）。然后只需要求出数组a的值 问题就解决了，下面介绍三种回溯解法：

1、八个for循环。用枚举的办法，八个for循环分别枚举每一行的8个位置，但是我们不用全部枚举完，可以采用“剪枝策略”，即遇到不适合的情况就回溯。例如当a[1]=4,第二行a[2]=4与a[1]同列，不符合题意。接下来的六个循环就不用穷举下去了，直接"continue;"去检验a[2]=5.....具体代码如下：

[cpp] view plaincopyprint?
 
  1. void main()  
  2. {  
  3.     int a[9];  
  4.     int i,t=1;  
  5.     for(a[1]=1;a[1]<9;a[1]++)  
  6.         for(a[2]=1;a[2]<9;a[2]++)  
  7.         {  
  8.             if(!Check(a,2)) continue;  
  9.             for(a[3]=1;a[3]<9;a[3]++)  
  10.             {  
  11.                 if(!Check(a,3)) continue;  
  12.                 for(a[4]=1;a[4]<9;a[4]++)  
  13.                 {  
  14.                     if(!Check(a,4)) continue;  
  15.                     for(a[5]=1;a[5]<9;a[5]++)  
  16.                     {  
  17.                         if(!Check(a,5)) continue;  
  18.                         for(a[6]=1;a[6]<9;a[6]++)  
  19.                         {  
  20.                             if(!Check(a,6)) continue;  
  21.                             for(a[7]=1;a[7]<9;a[7]++)  
  22.                             {  
  23.                                 if(!Check(a,7)) continue;  
  24.                                 for(a[8]=1;a[8]<9;a[8]++)  
  25.                                 {  
  26.                                     if(!Check(a,8)) continue;  
  27.                                     else   
  28.                                     {  
  29.                                         printf("第%d种解法： ",t++);  
  30.                                         for(i=1;i<9;i++)  
  31.                                             printf("第%d个皇后：%d ",i,a[i]);  
  32.                                         printf(" ");  
  33. }       }   }   }   }   }   }   }   }  
[cpp] view plaincopyprint?
 
  1. /////////////////////////////////Check函数功能：检验第n行的皇后是否和之前的皇后有冲突，没有的话返回1  
  2. int Check(int a[],int n)  
  3. {  
  4.     for(int i=1;i<n;i++)  
  5.     {  
  6.         if(abs(a[i]-a[n])==abs(i-n) || a[i]==a[n])//////////////见下面注释  
  7.             return 0;  
  8.     }  
  9.     return 1;  
  10. }  

代码注释：

某一行的皇后a[n]不能和之前的皇后a[i]位置有冲突，约束条件为：

a、不在同一列：a[n] != a[i]

b、不在同一行：因为现在是每一行求一个皇后的位置，所以同一行不会有冲突，不需要考虑。

c、不在同一对左角线：a[n]-a[i] != n-i

d、不在同一右对角线：a[n]-a[i] != -(n-i)

条件c和d可以合成：abs(a[n]-a[i]) != abs(n-i)

总结：其实这里用到的就是深度优先搜索的思想，从第一行的皇后一直深入去找第二行、第三行...皇后的位置。其中加上了约束条件Check函数进行“剪枝”。这就是回溯算法的思想：深度优先搜索，遇到不满足的情况就进行回溯。

2、方法一的优化。上述代码易读、易懂，但是用八个for循环不免显得很累赘，而且如果要求在100*100的棋盘上放100个皇后这种“N皇后问题“呢？难道用100个for循环吗？我们来把代码优化一下，用到的思想还是和方法一相同：深度优先搜索、回溯。具体代码如下：

[cpp] view plaincopyprint?
 
  1. void main()  
  2. {  
  3.     int a[256]={0};  
  4.     int i=1,j,n,t=1;////////////////////////////////////i表示当前正在搜索第i行的皇后位置  
  5.     printf("请输入几皇后？n=");  
  6.     scanf("%d",&n);  
  7.     while(i>0)  
  8.     {  
  9.         for(a[i]++;a[i]<=n;a[i]++)  
  10.         {  
  11.             if(Check(a,i))//////////////////////////////如果第i行的皇后与之前的皇后位置上没有冲突，则break跳出循环  
  12.                 break;  
  13.         }  
  14.         if(a[i]<=n)/////////////////////////////////////如果a[i]<=n，即上面的for循环是由“break;”跳出来的,即第i行皇后的位置符合条件  
  15.         {  
  16.             if(i==n)////////////////////////////////////找到一组解，输出  
  17.             {  
  18.                 printf("第%d种解法： ",t++);  
  19.                 for(j=1;j<=n;j++)  
  20.                     printf("第%d个皇后：%d ",j,a[j]);  
  21.                 printf(" ");  
  22.             }  
  23.             else////////////////////////////////////////未找完  
  24.             {  
  25.                 i++;  
  26.                 a[i]=0;  
  27.             }  
  28.         }  
  29.         else  
  30.             i--;////////////////////////////////////////回溯  
  31.     }  
  32. }  

代码注释：上面用到的Check函数和方法一的Check函数相同。

总结：虽然上面代码中只用到两层循环，但是思想、思路和方法一都是一样的，时间复杂度也是和方法一的时间复杂度相同。当n大于10之后运算就已经比较困难了。

3、递归实现。上面两种方法都是用到了深度优先搜索，而一般而言，深度优先搜索都是可以用递归来实现的。下面我们用递归的方式解决八皇后问题。具体代码如下：

[cpp] view plaincopyprint?
 
  1. int a[20],n,i,j,t=1;////////////////////////////////////////全局变量  
  2.   
  3. void Try(int i)  
  4. {  
  5.     int j,k;  
  6.     for(j=1;j<=n;j++)  
  7.     {  
  8.         a[i]=j;  
  9.         if(Check(a,i))///////////////////////////////////////如果第j列不会与之前的皇后冲突  
  10.         {  
  11.             if(i<n)//////////////////////////////////////////如果i<n，即还没有找到八个皇后，继续递归  
  12.                 Try(i+1);  
  13.             else ////////////////////////////////////////////如果找到了一组解就输出  
  14.             {  
  15.                 printf("第%d种解法： ",t++);  
  16.                 for(k=1;k<=n;k++)  
  17.                     printf("第%d个皇后：%d ",j,a[k]);  
  18.                 printf(" ");  
  19. }   }   }   }  
  20.   
  21. void main()  
  22. {  
  23.     printf("几皇后？n=");  
  24.     scanf("%d",&n);  
  25.     Try(1);  
  26. }  

 代码注释：

a、此处递归的思路很简单，每一层递归表示一行皇后，j表示列，即a[i]=j表示第i行的皇后位置在第j列。

b、以上用到的Check函数与方法一的Check函数相同。

我不清楚是什么原因，递归的速度竟然明显比前面的两种方法快？？

转自：http://blog.csdn.net/bone_ace/article/details/41419695

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/myPersonalTailor/p/4838853.html