題意描述：在8X8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。
可從行出發考慮，對于第一行中的第一個位置都考慮其擺放一個皇后，然后移動到下一行第一個位置，并考慮在該位置擺放皇后是否會造成攻擊，若是則考慮該行的下一個位置；如不是則繼續考慮下一行，直到八個皇后都被放置。
總的來說就是采用深度搜索加上迭代的方法來解決這個問題。
~~~
//八皇后問題，采用回溯法
#include<iostream>
using namespace std;
int g_nQueenLoc[8][8];
int nLeftToRight[15] = {0}; //對角線是否有皇后
int nRightToLeft[15] = {0};
int nRow[8] = {0};
int g_nQueenDown = 0; //已經放置的皇后數目
int g_nTotalNum = 0; //可能的解數目
void printQueen()
{
cout<<endl<<"第"<<g_nTotalNum<<"種放置方法為:"<<endl;
for(int i = 0; i< 8; i++)
{
for (int j = 0; j < 8; j++)
{
cout<<" ";
if (g_nQueenLoc[i][j])
{
cout<<"█";
}
else
cout<<g_nQueenLoc[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
}
void PutQueenDown(int xParm, int yParm)
{
int left2Right = 7 - xParm + yParm;
int Right2Left = xParm + yParm;
if(nLeftToRight[left2Right] == 0 && nRightToLeft[Right2Left] == 0 && nRow[yParm] == 0) //表明該位置可以放置皇后
{
nLeftToRight[left2Right] = 1; //標記該位置已經放置皇后
nRightToLeft[Right2Left] = 1;
nRow[yParm] = 1;
g_nQueenLoc[xParm][yParm] = 1;
g_nQueenDown++;
if (g_nQueenDown != 8)
{
PutQueenDown(xParm+1, 0);
}
else if (g_nQueenDown == 8)
{
g_nTotalNum++;
printQueen();
}
//還原該位置
g_nQueenDown--;
nLeftToRight[left2Right] = 0;
nRightToLeft[Right2Left] = 0;
nRow[yParm] = 0;
g_nQueenLoc[xParm][yParm] = 0;
}
if (yParm == 7)
{
return;
}
else
PutQueenDown(xParm, yParm+1);
}
int main()
{
cout<<"八皇后問題"<<endl;
memset(g_nQueenLoc, 0, sizeof(g_nQueenLoc));
PutQueenDown(0, 0);
cout<<"共有解法"<<g_nTotalNum<<"種"<<endl;
system("pause");
return 0;
}
~~~
運行結果：其中方塊表示皇后所在的位置
