#include <iostream>
using namespace std;
bool isOk(int c[], int row); // 判断能否在第row行第c[row]列插入一个皇后
void queen(int row, int c[], int n, int& total); // 回溯核心部分
int main()
{
int n; // 皇后的数量
cout << "enter the number of queen:\n";
cin >> n;
int* c = new int[n]; // 记录皇后的行列位置,i为行j为列,如c[i]=j表示第i行的第j列
int total = 0; // 方案种数
queen(0, c, n, total);
cout << "total = " << total;
return 0;
}
void queen(int row, int c[], int n, int& total)
{
if (row == n) // 当row==n的时,摆放完毕,输出,记数
{
for (int i = 0; i < n; i++)
cout << c[i] << " ";
cout <<"\n";
total++;
return;
}
// 皇后还未摆放完,则执行下面程序//遍历所有列,找到第row行应该放在第几列
for (int col = 0; col < n; col++)
{
c[row] = col;
// 如果可以放在row行col列则继续摆放下一行
if (isOk(c, row)) queen(row+1, c, n, total);
// 如果不能放在row行col列,则当前分支的解被剪枝,col++继续循环下一分枝
}
// 如果循环了所有的列都不能摆放,表示该行的所有解分枝都被剪去,则会回溯到前一层函数改变上一行皇后的摆放位置
}
bool isOk(int c[], int row)
{
for (int i = 0; i < row; i++)
{ // 第row行皇后不能和任意之前的皇后在同一列或 \方向或 / 方向
// \斜线上的元素差相等,因为通项为(i-x,j-x); /斜线上的元素和相等,国为通项为(i-x,j+x)
if (c[i] == c[row] || c[row]-row == c[i]-i || c[row]+row == c[i]+i)
return false;
}
return true;
}