N皇后问题

N皇后问题

•问题描述

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

•算法分析

只考虑第i个皇后放置在第i行的哪一列，所以在放置第i个皇后的时候，可以从第1列判断起，如果可以放置在第1个位置，则跳到下一行放置下一个皇后。如果不能，则跳到下一列...直到最后一列，如果最后一列也不能放置，则说明此时放置方法出错，则回到上一个皇后向之前放置的下一列重新放置。

当第n个皇后放置成功后，即得到一个可行解，此时再回到上一个皇后重新放置寻找下一个可行解...如此后，即可找出一个n皇后问题的所有可行解。

•解空间

4*4国际象棋盘，4个皇后

•算法分析

深度优先遍历

剪枝函数

约束函数

　　　if((col[k] - col[i])*(fabs(col[k] - col[i]) - fabs(k - i))!=0)，即当之前所有皇后与皇后i不在同一水平、垂直方向，也不在对角线方向上时，可以在当前位置放置皇后i，否则考虑下一个位置

 1 void Queen(int i,int n){
 2     if(i > n)
 3         Output();
 4     else{
 5         for(int j=1;j<=n;++j){
 6             int k = 1;
 7             col[i] = j;
 8             while(k < i){
 9             if((col[k] - col[i])*(fabs(col[k] - col[i]) - fabs(k - i))!=0){
10             k++;
11             if(k == i)
12                 Queen(i+1, n);
13              }
14             else{
15             break;
16             }
17               }
18         }
19     }
20 }

•小结

算法效率

时间复杂度分析

深度优先遍历

剪枝函数

约束函数：判断皇后是否处于同一水平、垂直、对角线方向

迭代回溯

•同学的完整代码

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 int path[110];
 7 int row[110],n,m,cnt;
 8 bool judge(int x)
 9 {
10     for(int i=1;i<x;i++)
11    if(row[x]==row[i]||(fabs(x-i)==fabs(row[x]-row[i]))) return false;
12     return true;
13 }
14 void dfs(int x)
15 {
16     if(x>m)
17     {
18         for(int i=1;i<=m;i++)
19         printf("%d ",row[i]);
20         printf("
");
21         cnt++;
22         return;
23     }
24     for(int i=1;i<=n;i++)
25     {
26         row[x]=i;
27         if(judge(x))
28         dfs(x+1);
29     }
30 }
31 int main()
32 {
33     while(scanf("%d%d",&n,&m)!=EOF)
34     {
35         memset(path,0,sizeof(path));
36         memset(row,-1,sizeof(row));
37         cnt=0;
38         dfs(1);
39         printf("%d
",cnt);
40     }
41     return 0;
42 }

View Code