在8×8的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后不得处在同一行、同一列或者同一对角斜线上。下图就是一种符合条件的摆放方法。请求出总共有多少种摆法。

解决这个八皇后问题通常需要用递归，而递归对编程能力的要求比较高。因此有不少面试官青睐这个题目，用来考察应聘者的分析复杂问题的能力以及编程的能力。因为八个皇后中的任意两个不能处在同一行，那么肯定是每一个皇后占据一行。于是可以定义一个数组ColumnIndex[8]，数组中第i个数字表示位于第i行的皇后的列号。先把ColumnIndex的八个数字分别用0-7初始化，接下来要做的事情就是对数组ColumnIndex做全排列。由于是用不同的数字初始化数组中的数字，因此任意两个皇后肯定不同列。所以只需要判断得到的每一个排列对应的八个皇后是不是在同一对角斜线上，也就是数组的两个下标i和j，是不是i-j==ColumnIndex[i]-Column[j]或者j-i==ColumnIndex[i]-ColumnIndex[j]。

参考代码如下：

int g_number = 0;

void EightQueen()
{
const int queens = 8;
int ColumnIndex[queens];
for(int i = 0; i < queens; ++ i)
ColumnIndex[i] = i;

Permutation(ColumnIndex, queens, 0);
}

void Permutation(int ColumnIndex[], int length, int index)
{
if (index == length)
{
if (Check(ColumnIndex, length))
{
++g_number;
PrintQueen(ColumnIndex, length);
}
}
else
{
for (int i = index; i < length; ++ i)
{
int temp = ColumnIndex[i];
ColumnIndex[i] = ColumnIndex[index];
ColumnIndex[index] = temp;

Permutation(ColumnIndex, length, index + 1);

temp = ColumnIndex[index];
ColumnIndex[index] = ColumnIndex[i];
ColumnIndex[i] = temp;
}
}
}

bool Check(int ColumnIndex[], int length)
{
for (int i = 0; i < length; ++ i)
{
for (int j = i + 1; j < length; ++ j)
{
if ((i – j == ColumnIndex[i] – ColumnIndex[j])
|| (j – i == ColumnIndex[i] – ColumnIndex[j]))
return false;
}
}

return true;
}

void PrintQueen(int ColumnIndex[], int length)
{
printf(“Solution %d\n”, g_number);

for (int i = 0; i < length; ++i)
printf(“%d\t”, ColumnIndex[i]);

printf(“\n”);
}

八皇后问题一共有 92 个互不相同的解。如果将旋转和对称的解归为一种的话，则一共有12个独立解。