hdu2553：N皇后问题（dfs）

http://acm.hdu.edu.cn/showproblem.php?pid=2553

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

解题思路：

一行肯定只能放一个，所以第几个就放在第几行，判断一下同列，左上和右上有没有在一条直线上即可。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 20
int a[N][N], book[N], s[N], ans, n;
void dfs(int i)
{
	int j, k, flag;
	if(i == n+1)
	{		
		ans++;
		return ;
	}
	for(j=1; j<=n; j++)
	{
		flag = 1;
		if(book[j]==1)
			continue;
		for(k=min(i,j)-1; k>=1; k--)
			if(a[i-k][j-k]==1 )
			{
				flag=0;
				break;
			}
		if(flag)
			for(k=min(n-j,i); k>=0; k--)
				if(a[i-k][j+k]==1)
				{
					flag=0;
					break;
				}
		if(flag)
		{
			a[i][j] = 1;
			book[j] = 1;
			dfs(i+1);
			book[j] = 0;
			a[i][j] = 0;
		}
	}
}
int main()
{
	int i;
	for(i=1; i<=10; i++)
	{
		ans=0;
		memset(a, 0, sizeof(a));
		memset(book, 0, sizeof(book));
		n=i;
		dfs(1);
		s[i]=ans;
	}		
	while(scanf("%d", &n), n!=0)
	{	
		printf("%d
", s[n]);
	}
	return 0;
}