Problem Description
在N*N的方格棋盘放置了N个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在与棋盘边框成45角的斜线上。
你的任务是,对于给定的N,求出有多少种合法的放置方法。
Input
共有若干行,每行一个正整数N≤10,表示棋盘和皇后的数量;如果N=0,表示结束。
Output
共有若干行,每行一个正整数,表示对应输入行的皇后的不同放置数量。
Sample Input
1
8
5
0
Sample Output
1
92
10
Source
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll sum, mark;
void test(ll col, ll ld, ll rd)
//col是哪些列有皇后
//ld是当前行哪些位置会被左斜攻击
//rd是当前行哪些位置会被右斜攻击
{
if (col != mark)
{
ll pos = mark & ~(col | ld | rd);
//获取哪些位置能放
while (pos)
{
ll p = pos & -pos;//取得最靠后的1位
pos -= p;//去掉
test(col | p, ((ld | p) << 1) & mark, (rd | p) >> 1);
}
}
else
sum++;
}
int main()
{
ios::sync_with_stdio(false);
int n;
while (cin >> n)
{
if (!n)
break;
sum = 0, mark = 1;
mark = (mark << n) - 1;//以上初始化↑
test(0, 0, 0);//计算
cout << sum << endl;//输出
}
return 0;
}