解题思路
- 用三个变量来描述皇后摆放的位置
- 对于列来说，用一个变量的32位来表示皇后放放在了那些列
- 对于右上到左下对角线，也用一个变量的位信息表示
- 对于左上到右下对角线，也用一个变量的位信息表示
- 列皇后所在的位置就是直接把放皇后的位设置成1
- 右上到左下对角线就是上一个限制，加上当前决定放皇后的位置，右移一位。
- 左上到右下对角线的限制就是上一个限制，加上当前决定放皇后的位置，再左移一位
代码实现
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#define u unsigned
#define ll long long
#define sc scanf
#define pr printf
#define fr(i, j, n) for (int i = j; i < n; i++)
#define N 1001
int ans;//有几个方案可以放皇后
int path[14];//放皇后的路径
int n;//表示几皇后问题
int len;//表示路径数组的长度
void dfs(int limit, int col, int left, int right)//limit表示需要摆放几个皇后，col表示皇后摆放在那些列，left表示当前行右上到左下的限制，right表示当前行左上到右下的限制
{
if (limit == col) {//如果皇后摆放满了就应该等于limit，因为放了n个皇后也就是n个1
if (ans < 3) {//打印路径
for (int i = 0; i < len; i++) {
pr("%d ", path[i] + 1);
}
pr("\n");
}
ans++;//方案数加一
return ;
}
int ban = col | left | right;//总的限制等于这些信息或起来
int c = ~ban & limit;//可以摆放的位置
int lowbit = 0;//取出可以摆放的位置的低位
while(c)//只要还有位置可以放皇后就继续尝试
{
lowbit = c & -c;//取出可以放皇后的位置
path[len++] = log2(lowbit);//取出对应的列数
c ^= lowbit;//把放皇后的位置清零
dfs(limit, col | lowbit, (left | lowbit) >> 1, (right | lowbit) << 1);//left | lowbit等于把之前的限制加上当前放皇后的位置，right | lowbit等于把之前的限制加上当前放皇后的位置
len--;
}
}
int main(int argc, char* argv[])
{
sc("%d", &n);//几皇后问题
dfs((1 << n) - 1, 0, 0, 0);//limit设置成低位有n个1其他位全是0，刚开始没有皇后摆放所以是0，右上到左下的限制刚开始也是0，左上到右下的限制刚开始也是0
pr("%d", ans);//输出摆放的方案数
return 0;
}