N 皇后问题 HDU - 2553

发表于 | 更新于 | 分类于

在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。

Input

共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。

Output

共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。

Sample Input

1
2
3
4
1
8
5
0

Sample Output

1
2
3
1
92
10

思想:

按行枚举，每一行只能放一个皇后，三个标记变量，v[0]-列，v[1]-左下对角线，v[2]-右上对角线 ，
表示这个地方是否被占 

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
50
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 15;
int a[N][N], pos[N];
bool v[3][N * 3];	
int n, cnt;

void print()		//打印结果函数 
{
	for(int i = 0; i < n; i ++ )
	{
		for(int j = 0; j < n; j ++ )
		{
			if(pos[i] == j)				//找到每行所放的皇后位置 
				cout << 'X';
			else
				cout << 'O';
		}
		cout << '\n';
	}
	puts("");
}
void dfs(int k)
{
	if(k == n)		//放到第n行，即皇后全部放完，记录答案，打印 
	{
		cnt ++;		
		print();
		return ;
	}	
	for(int i = 0; i < n; i ++ )
	{
		if(!v[0][i] && !v[1][k + i] && !v[2][k - i + n])	//行，左下右上对角线，左上右下对角线都没被占 
		{
			pos[k] = i;				//这行的皇后放在第i列 
			v[0][i] = v[1][k + i] = v[2][k - i + n] = 1;		//三个位置被占 
			dfs(k + 1);			//枚举下一行 
			v[0][i] = v[1][k + i] = v[2][k - i + n] = 0;  	//进行回溯，还原现场，不影响下一次放 
		}
	}	
}
int main()
{
	cin >> n;
	dfs(0);
	cout << cnt;
	return 0;
}
0%