【算法复习二】八皇后问题

一，问题描述

       在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

 

二，分析

       采用逐步试探的方式，先从一个方向往前走，能进则进，不能进则退并尝试另外的路径。首先我们来分析一下国际象棋的规则，这些规则能够限制我们的前进，也就是我们前进途中的障碍物。一个皇后q(x,y)能被满足以下条件的皇后q(row,col)吃掉

       1）x=row(纵向不能有两个皇后)

       2） y=col（横向不能有两个皇后）

       3）col + row = y+x;（斜向正方向）

       4）col - row = y-x;（斜向反方向）

       遇到上述问题之一的时候，说明我们已经遇到了障碍，不能继续向前了。我们需要退回来，尝试其他路径。

       我们将棋盘看作是一个8*8的数组，这样可以使用一种蛮干的思路去解决这个问题，这样我们就是在8*8=64个格子中取出8个的组合，C(64,8) = 4426165368,显然这个数非常大，在蛮干的基础上我们可以增加回溯，从第0列开始，我们逐列进行，从第0行到第7行找到一个不受任何已经现有皇后攻击的位置。

 

          

        前面四列的摆放如上图则 第五列，我们会发现找不到皇后的安全位置

        第五列的时候，摆放任何行都会受到上图所示已经存在的皇后的攻击，这时候我们认为我们撞了南墙了，是回头的时候了，我们后退一列，将原来摆放在第四列的皇后

（3，4）拿走，从（3，4）这个位置开始，我们在第四列中寻找下一个安全位置为（7，4），再继续到第五列，发现第五列仍然没有安全位置，回溯到第四列，此时第四列也是一个死胡同了，我们再回溯到第三列，这样前进几步，回退一步，最终直到在第8列上找到一个安全位置（成功）或者第一列已经是死胡同，但是第8列仍然没有找到安全位置为止

     

       总结一下，用回溯的方法解决8皇后问题的步骤为：

            1>从第一列开始，为皇后找到安全位置，然后跳到下一列

            2>如果在第n列出现死胡同，如果该列为第一列，棋局失败，否则后退到上一列，在进行回溯

            3>如果在第8列上找到了安全位置，则棋局成功。

 

三，源码（精选自网友解答）

       回溯法非递归

[html] view plaincopyprint?

1. #include<iostream>  
2. using namespace std;  
3.   
4. #define N 8  
5. //N代表皇后数  
6. void queen()  
7. {  
8.     int Count=0;         //计算总共的解的数量  
9.     int column[N+1];     //column[m]=n 表示第m列，第n行放置了皇后,这里下表并从0开始  
10.     int row[N+1];        //row[m]=1表示第m行没有皇后，=0表示有皇后  
11.     int b[2*N+1];        //b[m]=1表示第m条主对角线没有皇后，  
12.     int c[2*N+1];        //c[m]=1表示第m条次对角线没有皇后，=0表示有皇后  
13.     int numQueen=1;      //计数已经放置的皇后数目，当numQueen=N时候则表示已经完成探测  
14.     int good=1;          //good=1表示没有发生冲突,good=0表示发生冲突  
15.       
16.     //初始化这些标记  
17.     for(int j=0;j<N+1;++j)  
18.     {  
19.         row[j]=1; //没有皇后   
20.     }  
21.     for(int j=0;j<2*N+1;++j)  
22.     {  
23.         b[j]=c[j]=1;  
24.     }  
25.     column[1]=1;  
26.     column[0]=0;          //初始化第一行第一列，第二行第二列放置皇后  
27.     do  
28.     {  
29.         //没有发生冲突，则继续向下探测，增加皇后或者判断当前是否是解  
30.         if(good)  
31.         {  
32.             //当前皇后数是解，打印，继续向下探测  
33.             if(numQueen==N)  
34.             {  
35.                 Count++;  
36.                 cout<<"找到解"<<endl;  
37.                 for(int j=1;j<N+1;++j)  
38.                 {  
39.                     cout<<j<<"列"<<column[j]<<"行"<<endl;  
40.                 }  
41.                 //最后一个棋子向下移动,移动到本列最后一个  
42.                 while(column[numQueen]==N)  
43.                 {  
44.                     numQueen--;         //皇后数减1，即列数减1，回溯  
45.                     //回溯后将该列以及该列最后一行状态位修改  
46.                     //第numQueen列column[numQueen]行处状态位置修改  
47.                     row[column[numQueen]]=1;  
48.                     b[numQueen+column[numQueen]]=1;  
49.                     c[N+numQueen-column[numQueen]]=1;  
50.                 }  
51.                 column[numQueen]++;     //回溯至上一行，向上一行的下一列继续探测  
52.             }  
53.             //当前不是解，那么继续向下探测  
54.             else  
55.             {  
56.                 //改变该位置对应标志  
57.                 row[column[numQueen]]=0;  
58.                 b[numQueen+column[numQueen]]=0;  
59.                 c[N+numQueen-column[numQueen]]=0;  
60.                 //本次位置没有发生冲突，也不是正确解，那么就应该向下探测下一列的第一行  
61.                 column[++numQueen]=1;  
62.             }  
63.         }  
64.         //如果当前发生了冲突，就在本列继续向下，如果到了本列最后一行，则回溯到上一列  
65.         else  
66.         {  
67.             while(column[numQueen]==N) //到了本列最后一行，还是冲突，那么回溯到上一列  
68.             {  
69.                 numQueen--;  
70.                 row[column[numQueen]]=1;  
71.                 b[numQueen+column[numQueen]]=1;  
72.                 c[N+numQueen-column[numQueen]]=1;  
73.             }  
74.             column[numQueen]++; //发生冲突了，又没有到本列的最后一行，那么在本列继续向下一行探测  
75.         }  
76.         //检测放置了这个位置后是否冲突  
77.         good=row[column[numQueen]]&b[numQueen+column[numQueen]]&c[N+numQueen-column[numQueen]];  
78.     }while(numQueen);  
79.     cout<<N<<"皇后总共找到解："<<Count<<"个"<<endl;  
80. }  
81. int  main()  
82. {  
83.     queen();  
84.     system("pause");  
85.       
86.     return 0;  
87. }  

 

 更牛解答