题意 中文n/*n的棋盘放n个皇后(攻击同行/列/主副对角线) 使任何两个都不互相攻击 有多少种方法
枚举每一行 用vis[3][i]记录列 主对角线 副对角线是否被占 同列和对角线都没被占就继续枚举下一行 当枚举到n+1行的时候就是一个合法答案了
注: n/*n的方阵中主对角线可以用(i-j+n)标号 副对角线可以用(i+j)标号
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 50;
int n, cnt, vis[3][N], ans[N];
void getans(int cur)
{
if(cur == n) ++cnt;
for(int i = 0; cur < n && i < n; ++i)
{
if(vis[0][i] || vis[1][cur + i] || vis[2][cur - i + n]) continue;
vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 1;
getans(cur + 1);
vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 0;
}
}
int main()
{
for(int i=1;i<=10;++i)
{
cnt = 0,n=i;
getans(0);
ans[i]=cnt;
}
while(scanf("%d", &n), n)
printf("%d\n", ans[n]);
return 0;
}
|
非递归的回溯
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <cstdio>
#include <cmath>
using namespace std;
const int M = 20, N = 8;
int col[M], vis[3][M], last[M], cnt;
bool check(int r)
{
for(int i = 1; i < r; ++i)
if(i + col[i] == r + col[r] || i - col[i] == r - col[r] || col[i] == col[r])
return false;
return true;
}
void gao()
{
int r = 1;
col[1] = 0;
while(r)
{
col[r] = col[r] + 1;
if(col[r] > N) {--r; continue;}
if(!check(r)) continue;
if(r == N)
{
for(int i = 1; i <= N; ++i)
printf("%d ", col[i]);
puts("");
++cnt;
}
else col[++r] = 0;
}
}
int main()
{
cnt = 0;
gao();
printf("%d\n", cnt);
return 0;
}
|
还有可以打印答案的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #include<cstdio>
#include<cstring>
using namespace std;
const int N = 1000;
int n, cnt, c[N], col[N][N], vis[3][N];
void getans(int cur)
{
if(cur == n)
{
++cnt;
for(int i = 0; i < n; ++i)
col[cnt][i] = c[i];
}
else
{
for(int i = 0; i < n; ++i)
if(!vis[0][i] && !vis[1][cur + i] && !vis[2][cur - i + n])
{
c[cur] = i;
vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 1;
getans(cur + 1);
vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 0;
}
}
}
int main()
{
while(scanf("%d", &n))
{
memset(vis, 0, sizeof(vis));
cnt = 0;
getans(0);
printf("%d皇后问题共有%d组解:\n\n", n, cnt);
for(int k = 1; k <= cnt; ++k)
{
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
printf("%d ", j == col[k][i]);
printf("\n");
}
printf("\n");
}
}
return 0;
}
|
N皇后问题
Problem Description
在N/*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。
Input
共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。
Output
共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。
Sample Input
1 8 5 0
Sample Output
1 92 10