在 n * n 的棋盘上放置n个皇后,使得每一行、每一列、每一条对角线有且只有一个皇后,实质上可以抽象为对 1 ~ n 这n个自然数进行全排列,排列中数字i所处的位置顺序代表行号,i代表列号,那么得到的排列组合必定满足每行每列不重复,只要再对对角线位置进行判断即可。为了方便起见,使用递归进行处理。
const int maxn = 11;
int queen[maxn]; // 创建棋盘,i代表行号,queen[i]代表列号
int count = 0; // count记录满足的组合数
int n; // 在 n * n 的棋盘上放置n个皇后
bool hashTable[maxn] = {false}; // 散列判断当前自然数是否已经被使用,即当前列是否有皇后
void generateQueen(int index) // index代表当前正在处理的行号
{
if (index == n + 1) // 递归边界,已经处理完n行则返回
{
count++; // 能到达这一步一定是合法的
return;
}
for (int x = 1; x <= n; x++) // 对第x列进行处理
if (hashTable[x] == false) // 第x列还没有皇后
{
bool flag = true; // flag用来判断对角线是否满足条件
for (int pre = 1; pre < index; pre++) // 与前面已放置的皇后进行对角线位置判断
if (abs(pre - index) == abs(queen[pre] - x)) // 如果对角线位置已有皇后
{
flag = false;
break;
}
if (flag) // index行、x列位置合法
{
queen[index] = x;
hashTable[x] = true; // 第x列标记为已有皇后
generateQueen[index + 1]; // 对下一行进行处理
hashTable[x] = false; // 递归完毕,还原第x列为未占用
}
}
}
网友评论