N皇后问题2

题目描述:

现在要在N*N棋盘内放N个皇后，使任意两个皇后都不相吃。

皇后可以吃同一行，同一列，同一对角线的棋子。

输出所有的方案。

输入格式:

输入一个数N

输出格式:

输出所有的方案

样例输入:

4

样例输出:

2 4 1 3
3 1 4 2

提示:

4 <= N <= 13

qq1010903229 : 听说有些人在N皇后问题1中打表 0ms AC，于是我出了这道题。

算法提示：位运算优化

请完善程序：

#include <bits/stdc++.h>
using namespace std;
int n,a[50], all,ans;
void print() {
	for(int i=1; i<=n; i++) {
		int cnt = 0, c;
		c = a[i];      //a[i]=8，那么cnt为4，即放在第4列上
		while(c) {  //算出2的几次方是a[i], 如a[i]=8，那么c为8,4,2,1,0，所以cnt的值为4
			_______________
			c = ( c >> 1 );
		}
		printf("%d ",  cnt ); 
	}
	printf( "\n" );
	return;
}

void dfs(int now,int r,int ld,int rd) {	//列及两个方向的对角线 
	if( r == all )    {		//每一列上全为1，也就是说没位置可放了，或写成 now>n 
		print( );
		return;
	}
	int  pos = all & _____________ ;  //把当前第now行上不能放的列，排除掉
	while( pos ) {
		int p = pos & _____________;	//把pos代表的可放列中都试放一遍，取最低位（ 最右 ）的1 
		pos -= p; 					//把相应位（列）上的1置为0 或 pos ^= p
		______________;  			//a[i]记得是2的多少次的值，是2的(列号-1）次方的值
		dfs(____________________);  //对角线：/的对角线左移一列，\的对角线是右移一列
		//每个放置的列p，对下行来说会影响到2*p 和 p/2的列 
	}
}

int main() {
	cin >> n;
	all = ( 1 << n ) - 1;   // all为从第1列到第n列，全部为1
	dfs( 1, 0, 0, 0 );   //第几行，后面是列及两个方向的对角线所覆盖的列号
	return 0;
}

时间限制: 400ms
空间限制: 16MB

---

来源: by qq1010903229