首页 > 代码库 > 2017.5.3 3.n皇后问题

2017.5.3 3.n皇后问题

题目描述

在N*N(N<=10)的棋盘上放N个皇后,使得她们不能相互攻击。两个皇后能相互攻击当且仅当它们在同一行,或者同一列,或者同一条对角线上。 找出一共有多少种放置方法。

输入

第一行输入N。

输出

输出方案总数。

样例输入

4

样例输出

2

数据范围限制

N<=10

 

 

之前用暴力DFS写过一次,今天又尝试学了一下剪枝。

问题的解可以用一个n元向量X=(x1,x2,.....xn)表示,即第n个皇后放在第i行第xi列上。 两个皇后不能放在同一列上,xi≠ xj;若两个皇后的摆放位置分别是(i,xi)和(j,xj),在棋盘上斜率为-1的斜线上,满足条件i-j=xi-xj;在棋盘上斜率为1的斜线上,满足条件i+j=xi+xj; 综合两种情况,由于两个皇后不能位于同一斜线上,所以|i-xi|≠ |j-xj|。

 

 1 #include<cstdio>
 2 
 3 int n,ans; 
 4 int a[15];
 5 
 6 void DFS(int u)
 7 {
 8     if(u>n)
 9         {
10             ++ans;
11             return;
12         }
13     for(int i=1;i<=n;i++)
14         {
15             bool law=1;
16             for(int j=1;j<u&&law;j++)
17                 if(a[j]==i||a[j]+j==i+u||a[j]-j==i-u)
18                     law=0;
19             if(!law) continue;
20             a[u]=i;
21             DFS(u+1);
22         }
23 }
24 
25 int main()
26 {
27     scanf("%d",&n);
28     ans=0;
29     DFS(1);
30     printf("%d\n",ans);
31     return 0;
32 }

 

2017.5.3 3.n皇后问题