N皇后问题2

源代码：

#include<cstdio>
int n,Ans(0),i[17];
void DFS(int T,int L,int D1,int D2) //T表示皇后数。
{
    if (T==n+1)
    {
        Ans++;
        return;
    }
    int S=((1<<n)-1)&(~(i[T]|L|D1|D2));
    while (S)
    {
        int t=S&(-S); //传说中的lowbit()，输出的是二进制数中最后1的位置数。
        DFS(T+1,L+t,(D1+t)<<1,(D2+t)>>1); //层次化的对角线与下一行。
        S-=t; //去掉这个1，相当于枚举所有情况。
    }
}
int main() //位运算优化N皇后问题。
{
    scanf("%d",&n);
    for (int a=1;a<=n;a++)
      for (int b=1;b<=n;b++)
      {
        int t;
        scanf("%d",&t);
        i[a]+=t<<(b-1);
      }
    DFS(1,0,0,0);
    printf("%d",Ans);
    return 0;
}

/*
    位运算是玄学中的玄学！
        举个例子，读入：1 0 1 1
        则对应的i[]为：1101 --> 13
        进入DFS()，S=(10000-1 --> 1111)&(~1101|0000|0000|0000 --> ~1101 --> ...0010)
        即S=0010 --> 2
        进入while()后，经过lowbit()，t=10 --> 2 
        DFS(T+1,0010 --> 2,0100 --> 4,0001 --> 1)
        由于S=0，结束循环，并进入下一层。
    然后一层一层地搜索。
*/