hdu1116回溯N皇后问题

经过思考，不难发现：恰好N个皇后放在不同行不同列，那么是不是可以转换成N个皇后所在行分别确定（一人一行）的情况下对她们的所在列的枚举。

也就是列的全排列生成问题，我们用c[x]表示x行皇后的列编号。而我们知道0~N-1的排列一共有N的阶乘，枚举量不会超过它。

if(cur==n)//递归边界。只要走到这里，所有的皇后必然不冲突
tot++;

根据我们的代码，我们是从cur=0开始的，

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int n,tot,c[1000];
 5 void search(int cur)
 6 {
 7     int i,j;
 8     if(cur==n)//递归边界。只要走到这里，所有的皇后必然不冲突
 9     tot++;
10     else
11     for(i=0;i<n;i++)
12     {
13         int ok=1;
14         c[cur]=i;//尝试把第cur行的皇后放在第i列
15         for(j=0;j<cur;j++)
16         if(c[cur]==c[j]||cur-c[cur]==j-c[j]||cur+c[cur]==j+c[j])//检查是否与前面的皇后冲突
17         {
18             ok=0;break;
19         }
20         if(ok)
21         search(cur+1);//如果合法，继续递归
22     }
23 }
24 int main()
25 {
26     int a[15];
27     for(int i=0;i<10;i++){
28         tot=0;
29         n=i+1;
30         search(0);
31         a[n]=tot;
32     }
33     while(cin>>n&&n)
34     {
35         cout<<a[n]<<endl;
36     }
37 }

search(cur+1);//如果合法，继续递归并不会判断n+1行的皇后。所以我们从cur=0开始。

当然从cur=1开始也是可以的，但此时

if(cur==n+1)//递归边界。只要走到这里，所有的皇后必然不冲突

tot++;

程序中的

if(c[cur]==c[j]||cur-c[cur]==j-c[j]||cur+c[cur]==j+c[j])//检查是否与前面的皇后冲突
        {
            ok=0;break;
        }

既然是逐行放置，那么皇后肯定不会横向攻击，因此只需检查是否纵向和斜向攻击即可。条件c[cur]==c[j]||cur-c[cur]==j-c[j]||cur+c[cur]==j+c[j])

y-x标示了主对角线，斜率为1；

y+x标示了副对角线，斜率为-1；

画画图就知道了

我们还可以用二维数组vis[2][]直接判断当前尝试放的皇后的对角线和纵向有没有皇后已经放了，注意主对角线标示y-x可能为负数，所以要加n

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 using namespace std;
 6 int n,tot,c[1000];
 7 int vis[3][1000];
 8 void search(int cur)
 9 {
10     if(cur==n)tot++;
11     else{
12         for(int i=0;i<n;i++){
13             if(!vis[0][i]&&!vis[1][cur+i]&&!vis[2][cur-i+n]){
14             c[cur]=i;//如果不需要打印皇后所在列，可以舍去
15             vis[0][i]=vis[1][cur+i]=vis[2][cur-i+n]=1;//标示这些空已经不能再放皇后
16             search(cur+1);
17             vis[0][i]=vis[1][cur+i]=vis[2][cur-i+n]=0;//回溯要改回来
18             }
19         }
20     }
21 }
22 int main()
23 {
24     int a[15];
25     for(int i=0;i<10;i++){
26         memset(vis,0,sizeof(vis));
27         tot=0;
28         n=i+1;
29         search(0);
30         a[n]=tot;
31     }
32     while(cin>>n&&n)
33     {
34         cout<<a[n]<<endl;
35     }
36 }