hdu 2553 N皇后问题

做了这么久的搜索，终于还是碰到了N皇后问题，之前一直都不敢去触碰，今天还是无奈的做了

我的代码比较乱，也比较慢，看下大牛的代码吧，感觉好精炼呀，而且效率很高的说

map[]，下标表示所在行，值表示所在列

哈，判断是否在同一对角线上居然是这么判断的，好神奇

要事先打表

#include<iostream>  
#include<string>
using namespace std;
int n,map[20],des[20],cnt,a[11];  
void DFS( int num )  
{  
     if( num == n + 1 )  
     {  
         ++cnt;  
         return ;  
     }  
     for( int i = 1; i <= n; ++i )  
     {  
          if( !des[i] )//判断是否在同一行  
          {  
              int f = 1;  
              map[num] = i;  
              for( int j = 1; j < num; ++j )  
                   if( ( map[num] - num == map[j] - j ) || ( map[num] + num ) == map[j] + j )  
                   {//判断是否在对角线上  
                      f = 0;  
                       break;  
                   }  
              if( f )  
              {  
                  des[i] = 1;  
                 DFS( num + 1 );  
                 des[i] = 0;  
              }  
          }  
      }  
 }  
void  init( )  
{  
      for( int i = 1; i < 11; ++i )  
      {  
           memset( map,0,sizeof( map ) );  
           memset( des,0,sizeof( des ) );  
           cnt = 0,n = i,DFS( 1 ),a[i] = cnt;  
      }  
}  
int main( )  
{  
    init( );  
    int n;  
    while(cin>>n&&n )  
           cout<<a[n]<<endl;  
    return 0;  

} 

下面是位运算版的，来自大牛

即使不打表也不超时

#include<iostream>
#include<algorithm>
using namespace std;
int sum,upperlim;
int ans[11];
void dfs(int row,int ld,int rd)//row 表示哪些列已经放置过，ld表示当前行哪些位置不能放，rd同ld
{                              //不过，rd和ld所不同的是，ld是记录左对角线的影响，rd则相反
    int pos,p;
    if(row!=upperlim)//相等则表示所有列都已经放置了
    {
        pos=upperlim & ~(row|ld|rd);//pos中的1表示当前行可以放置的位置
        while(pos!=0)
        {
            p=pos& -pos;//p取出pos中最右边的第一个1，即第一个可以放置的位置
            pos-=p;//移除刚选择的位置
            dfs(row+p,(ld+p)<<1,(rd+p)>>1);//row+p 把刚选上的位置所在的列标记，ld+p 要左移一位是因为左对角线对下一行的影响是往左边的一位，
        }
    }
    else sum++;
}
void init()
{
    for(int i=1;i<=10;i++)
    {
        upperlim=(1<<i)-1;
        sum=0;
        dfs(0,0,0);
        ans[i]=sum;
    }
}
int main()
{
    int n;
    init();
    while(scanf("%d",&n)==1&&n)
    {
        printf("%d\n",ans[n]);
    }
    return 0;
}