八皇后问题
最后更新于：2022-04-01 10:11:46
题意描述：在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;
}
~~~
运行结果：其中方块表示皇后所在的位置
