八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
解题思路：在这之前我们要明确递归求解其实是分成两个部分的：【1】递归【2】回朔 递归部分就是整个问题的核心求解步骤，也是一个问题重复执行的部分而回朔则发生在问题分解到了尽头，或者问题求解不能再继续下去的时候，程序开始回朔。回朔要确保恢复现场，什么意思呢，就是递归函数在返回后，程序里面的变量要和之前调用递归函数之前一致！这一点在很多时候会被忽略，比如一些全局的变量。
现在我们来看具体问题：第一步肯定是在棋盘的第一行选一个位置，之后我们要干两件事：
【1】更新棋盘的信息，标记哪些位置已经不能放棋子了。
【2】选择下一行要放置棋子的位置 。
之后的核心操作就是重复上面两步，所以上面就是整个问题的递归部分。之后我们要考虑程序的尽头，也就是回朔的条件。
【1】假如我们一直选择棋子的位置直到最后一行，那么我们完成了一次布局，把他记录下来然后回朔到上一层。
【2】假如我们还没到最后一行，但是我们已经不能在这一行放置棋子了，也就说我们的求解遇到了死胡同。这时候我们也要回朔，回到上一行选择别的位置，假如上一行也没位置了，那么就再返回，直到可以继续向下走。
这里我们要注意了，因为棋盘的信息是一个8*8的全局数组，所以当我们返回上一层并且选择其他位置的时候，要把之前选择位置造成的棋盘信息的改动还原回去！
#include<iostream>
using namespace std;
int board[8][8]={0};
int temp_pos[8]={0};
int chessplace[92][8]={0};
int cnt_ways=0;
void copy(int a[],int b[])
{
int i=0;
for(i=0;i<8;i++)
a[i]=b[i];
}
//传入棋子所在的层数和位置
void calplace(int level,int pos)
{
int i=0,j=0,k=0;
int q=0,w=0;
//更新棋盘
for(k=level;k<8;k++)
for(i=0;i<8;i++)
{
if(i==pos||(i==(pos+k-level)&&k>level)||(i==(pos-k+level)&&k>level))
{
if(board[k][i]==0)
board[k][i]=level+1;
}
}
//对下一颗棋子所有可能的位置进行试探遍历
for(j=0;j<8;j++)
{
if(board[level+1][j]==0)
{
temp_pos[level+1]=j;//临时记录
if(level+1==7)
{
copy(chessplace[cnt_ways],temp_pos);//把临时数组里的值复制到最后的结果里面
cnt_ways++;
return;
}
calplace(level+1,j);//递归
//回朔
for(q=0;q<8;q++)
for(w=0;w<8;w++)
if(board[q][w]==level+2)
{
board[q][w]=0;
}
}
}
}
int main()
{
int n=0;
int temp=0;
int i=0,j=0;
for(i=0;i<8;i++)
{
temp_pos[0]=i;//临时记录
calplace(0,i);
memset(board,0,sizeof(board));
}
for(j=0;j<92;j++){
for(i=0;i<8;i++)
chessplace[j][i]++;
}
while(cin>>n)
{
while(n--)
{
cin>>temp;
temp--;
for(i=0;i<8;i++)
cout<<chessplace[temp][i];
cout<<endl;
}
cout<<"writed by damon-lin whos blog is http://blog.csdn.net/linsheng9731 "<<endl;
}
return 0;
}
原文：http://blog.csdn.net/linsheng9731/article/details/23212933