n皇后2进制算法

杭电的n皇后用测试数据比较多所以不打表就会超时，其实它的其他原理也没什么，就是一个dfs，不断的模拟棋子在棋盘上摆放的情况罢了，用一个二维数组就可以完成了，不过在这里我用类二进制的方法来计算这个问题，就是1代表放了棋子，0代表没放，所以用二进制可以直接模拟，当有一行都为1则是1<<n-1的值时，表示改行已经放慢，不用再遍历，这样要比直接拿数组来模拟来的方便，当在一行中方了一个棋子，这样对接下来每行都进行遍历摆放不能放棋子的位置，用左右移和或运算就可以完成。对某个位置是否放了棋子用&运算来判断。接下来就看下代码：

#include<iostream>#include<string.h>

using namespace std;

#define N 15

int f[N];int l[N],r[N],m[N];int CNT;

void closed(int row,int n,int len)//对摆放好棋子后产生的对其他位置影响进行遍历{ int i,temp;

 for (i=row;i<=n;i++) {  temp = l[i-1]<<1;  if (temp<len)   l[i] = temp;  else   l[i] = 0;  if (r[i-1]!=1 && r[i-1]!=0)   r[i] = r[i-1]>>1;  else   r[i] = 0;

  m[i] = m[i-1];  f[i] = f[i] | l[i] | r[i] | m[i]; }}

void dfs(int row,int n,int len){ int i,temp; int flag=0; int tempf[N];

 if (f[row]==len-1)//判断该行是否能放棋子  return ;

 for (i=0;i<n;i++) {  temp = 1<<i;// 该棋子要放在该行的位置    if ((f[row]&temp) ==0)// 判断该位置是否有棋子  {   if (row==n)//是否为最后一行   {    CNT ++;    continue;   }   memcpy(tempf,f,sizeof(f));   l[row] = r[row] = m[row] = temp;   f[row] = f[row] | temp;   closed(row+1,n,len);      dfs(row+1,n,len);      memcpy(f,tempf,sizeof(tempf));  }  } }

int main(){ int n,len; int res[N];

 for (n=1;n<=10;n++) {   len = 1<<n;  CNT = 0;  memset(f,0,sizeof(f));  memset(l,0,sizeof(l));  memset(r,0,sizeof(r));  memset(m,0,sizeof(m));

  dfs(1,n,len);

  res[n] = CNT;   } while (cin >> n && n!=0)  cout << res[n] << endl;

 return 0;}