首页 > ACM题库 > HDU-杭电 > hdu 2553 N皇后问题-回溯和剪枝-[解题报告]C++
2014
02-10

hdu 2553 N皇后问题-回溯和剪枝-[解题报告]C++

N皇后问题

问题描述 :

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

输入:

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

输出:

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

样例输入:

1
8
5
0

样例输出:

1
92
10

此题是经典的N皇后问题,描述:在一个N*N的棋盘上要摆放N个皇后,要求任意两个皇后不能在同一行,同一列或者同一条与棋盘的边成45度角的斜线上,即与对角线平行的斜线上,求对于不同的N,各有多少种摆法使任意两个皇后不能相互攻击。


用回溯法就可以解决,设皇后的编号依次为1,2,……,n,则可以认为第i个皇后必须摆放在第i行,然后枚举第一个皇后的位置进行回溯,若某一次发现某个皇后无法找到摆放位置则直接返回,如果所有皇后都可以找到摆放位置,则说明存在一种摆法满足要求,统计有多少种摆法即可。


此题n<=10,测试数据中会有大量重复数据,因此要保存答案,遇到曾经计算过的n直接输出即可,否则可能会超时。


#include<iostream>
using namespace std;
int n;
int x[100];
int ans[11];
bool Place(int k)
{
	int i = 1;
	while (i<k)
	{
		if (x[i]==x[k] || abs(x[i]-x[k])==abs(i-k))	return false;
		i++;
	}
	return true;
}
int main()
{
	int k, cnt;
	memset(ans, 0, sizeof(ans));
	while (scanf("%d", &n)!=EOF && n!=0)
	{
		if (ans[n]>0) 
		{
			printf("%d\n", ans[n]);
			continue;
		}
		x[1] = 0;
		k = 1, cnt = 0;
		while (k>0)
		{
			x[k]++;
			while (x[k]<=n && !Place(k))
			{
				x[k]++;
			}
			if (x[k]<=n)
			{
				if (k==n)
				{
					cnt++;
				}
				else 
				{
					k++;
					x[k] = 0;
				}
			}
			else k--;
		}
		ans[n] = cnt;
		printf("%d\n", cnt);
	}
	return 0;
}

解题转自:http://blog.csdn.net/alongela/article/details/6755770


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥