HDU2553 N皇后问题【回溯法】

本文主要是介绍HDU2553 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

题目大意：N*N的棋盘上放N个皇后，N个皇后不能出现在同一行，同一列或是同一斜行。

思路：直接枚举判断太慢了，考虑到每行每列只有一个皇后，那么用一个数组C[x]表示第

x行放置的皇后所在的列编号，即x表示行，C[x]表示列。判断是否和前边所放皇后冲突可以

判断当前第cur行与之前的0~j行是否冲突。

C[cur] == C[j] || cur-C[cur] == j-C[j] || cur+C[cur] == j+C[j]分别判断是否在同一列,同一

主对角线,同一副对角线上。

但是还可以继续优化。直接用一个vis[3][?]直接判断当前尝试的皇后所在列和对角线是否已

有其他皇后，即 !vis[0][i]所在列是否有其他皇后，!vis[1][cur+i]所在副对角线是否有其他皇

后，!vis[2][cur-i+n]所在副对角线上是否有其他皇后。

但是这样提交的代码也超时了。。。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;int vis[3][50],C[30],tot,N;
void Search(int cur)
{if(cur == N){tot++;}else{for(int i = 0; i < N; i++){if(!vis[0][i] && !vis[1][cur+i] && !vis[2][cur-i+N]){vis[0][i] = vis[1][cur+i] = vis[2][cur-i+N] = 1;Search(cur+1);vis[0][i] = vis[1][cur+i] = vis[2][cur-i+N] = 0;}}}}
int main()
{while(~scanf("%d",&N) && N){tot = 0;memset(vis,0,sizeof(vis));Search(0);printf("%d\n",tot);}return 0;
}

果断打表过

#include<iostream>
using namespace std;int main()
{int a[23] = {0,1,0,0,2,10,4,40,92,352,724};int N;while(cin >> N){if(N==0)break;elsecout << a[N] << endl;}
}

这篇关于HDU2553 N皇后问题【回溯法】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---