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
Source
2008 HZNU Programming Contest
这道题目来源于杭电的oj，超链接如下：
2553 N皇后问题
题解：
八皇后问题：八重循环。N皇后，N重循环？
用递归替代多重循环！
这道题的解题思路为递归回溯 + 打表。
我们知道棋盘上每一行只能有一个皇后，N个皇后必然在N行上。不妨我们假设第 i 个皇后在第 i 行上的某列，并且前 i - 1 行皇后已经摆好确定了位置，那么我们只需枚举第 i 行的每一列并与前 i - 1行皇后的位置进行比较，若找到某一列使得皇后不冲突满足要求，那就把第 i 个皇后放在这一列上，然后就递归搜索下一行，同理将第 i +1个皇后摆放在第 i +1行某列上，一直这样递归搜索下去直到最后一行将最后一个皇后摆放好，这就是问题的一个解，然后往前回溯直到整个递归完成看能有多少解也就是多少种摆放方案。若在第 i 行没有找到满足要求的位置，那么就回溯到上一行也就是第 i -1行寻找下一个满足的位置，若第 i -1行也没有找到满足要求的位置，那么继续往前回溯寻找直至递归完成。
这里强调一下，这道题必须打表，否则很容易会超时，因为递归有着大量的重复计算。
代码实现
#include<iostream>
#include<cmath>
using namespace std;
int N;
int queenPos[11],a[11];//queenPos[11]用来存放算好的皇后位置。棋盘最左上角是(0,0)
int count;//计数
void NQueen(int k);int main()
{
for(N=1; N<=10; ++N)//打表{
count=0;NQueen(0);//从第 0行开始摆皇后，第1个皇后摆放在第 0行a[N]=count;}while(cin >> N && N!=0){
cout << a[N] << endl;}return 0;
}void NQueen(int k) //在 0 ~ k-1 行皇后已经摆好的情况下，摆第 k行及其后的皇后
{
if(k==N)//N个皇后已经摆好 {
count++;return ;}for(int i=0; i<N; ++i) //枚举第 k个皇后的位置（也就是枚举棋盘的每一列）{
int j;for(j=0; j<k; ++j)//和已经摆好的 k个皇后的位置比较，看是否冲突 {
if(queenPos[j]==i || abs(queenPos[j]-i)==abs(k-j))break;//冲突，则试下一个位置}if(j==k)//当前选的位置 i与前面已经摆放好的皇后位置不冲突 {
queenPos[k]=i;//将第 k个皇后摆放在位置 i NQueen(k+1);//继续向下递归搜索摆放第 k+1行的皇后 }}/*逐行放置皇后，那么不用判断皇后是否在同一行queenPos[j]==i 用来判断皇后是否在同一列abs(queenPos[j]-i)==abs(k-j) 用来判断皇后是否在同一条对角线*/
这道题其实用到深度优先搜索算法的思想， 用深度优先搜索的递归实现进行查找并解决问题。并且N皇后问题当N大于等于4才有讨论意义，而且不只有一个放置方案。
这里放一个终极打表的代码：
#include <iostream>
using namespace std;
int a[11]={
0,1,0,0,2,10,4,40,92,352,724};
int main()
{
int N;while(cin >> N && N!=0){
cout << a[N] << endl;}return 0;
}感谢阅读，若有错误还请指出，如果有什么不懂的也可以留言！