C++-如何用位运算实现n皇后问题？

Question

有没有可能用位运算解决n皇后问题？

Answer 1

这个网上应该有很多吧……http://www.matrix67.com/blog/关键的是看懂这段代码：

void solve(int row, int ld, int rd){
int pos, p;
if ( row != upperlim ){
****pos = upperlim & (~(row | ld | rd ));
while ( pos ){
p = pos & (~pos + 1);
pos = pos - p;
solve(row | p, (ld | p) << 1, (rd | p) >> 1);
}****
}
else ++ Ans;
}

可以输出每一步的查找后，row、rd、ld【主要针对32位机器，可以自行调整】：

#include <iostream>
using namespace std;
#include <math.h>

int sum = 0;
int upperlimit = 1;
char b[41]={'',''};
void binary(int num)
{
int k=1,blank=1;
for(int i=0;i<32;i++)
{
if(num&k)
{
b[40-i-blank]='1';

if((i+1)%4==0)
{
++blank;
b[40-i-blank]=' ';
}
}
else
{
b[40-i-blank]='0';

if((i+1)%4==0)
{
++blank;
b[40-i-blank]=' ';
}
}
k=k<<1;
}
b[40]=(char)0;
//b[0]=(char)0;
}

void compare(int row,int ld,int rd,int num_queen)
{
int blank_count=num_queen/4;//计算空格数
int loc=40-num_queen-blank_count;
cout<<"初始值："<<endl;
cout<<"row="<<row<<","<<(binary(row),(b+loc))
<<" ld="<<(binary(ld),(b+loc))
<<" rd="<<(binary(rd),(b+loc))<<endl;
if(row!=upperlimit)
{
int pos = upperlimit&~(row|ld|rd);
while(pos!=0)
{
int p=pos&-pos;
pos-=p;
cout<<" p="<<(binary(p),(b+loc))
<<" pos="<<(binary(pos),(b+loc))<<endl;

compare(row+p,(ld+p)<<1,(rd+p)>>1,num_queen);
}
}
else{
sum++;
}
}

int main()
{
int num_queen;
cout<<"请输入皇后的个数:";
cin>>num_queen;

upperlimit = (upperlimit<<num_queen)-1;
compare(0,0,0,num_queen);
cout<<"问题的解如下:"<<sum<<endl;
return 0;
}