USACO/checker

来自NOCOW

[编辑] 分析

[编辑] DFS+优化

因为要遍历整棵搜索树，所以用DFS，我们可以在搜索时加入剪枝，记录横行和两条斜线是否被攻击，每次只放在不受任意方向攻击的地方。这个剪枝过最后一个数据需要2s，超时。(准确的说，是1.2s -zst_0110)

[编辑] 考虑对称

如果n是偶数，第一行枚举前一半的数，这样每搜索出一种方案后，沿中线对称过来又是一种方案，并且因为第一行的数小于一半，对称过来的方案总大于原方案（即在搜索树中后被搜索到），不会出现重复的情况。

如果n是奇数，先在中间行和中间列放子，并且位置都不超过半数(<n div 2)，且中间行>中间列，这样每搜索出一种方案，把它对称旋转后一共有8种方案，因为中间行和中间列的的不出现重复，所以8种方案不重复。这样只需枚举原来的1/8就可以了。这样就完全可以过了。{注意放在正中间位置的时候}（个人感觉如果要求更严格，需要数学证明。我个人感觉上面上面的条件应该改为<=n/2,才对,而当中间行=中间列=(n+1)/2的时候，需要单独处理，如何单独处理呢，可以选择两种方法，一种是已经固定中间行和中间列然后进行枚举。一种是按照第一行的选择的列数小于(n+1)/2 枚举出来这个数然后乘以2。）

[编辑] 使用链表

还可以再优化，用链表（或用数组模拟）记录每行待选的位置，进行插入和删除，这样就不用记录横行是否被攻击了，并且每次枚举位置的个数减少。

[编辑] 简化问题

我们知道，每一行都只能填上一个皇后，并保证每行的皇后不相同就以行为阶段，来考虑列的放置那么，如何解决对角线的问题呢？

可证明的是，若在a行b列放上棋子，那么对于另一枚棋子x行y列

只需保证

x<>a,y<>b；
x+y<>a+b
x-y<>a-b

这样，就可以用三个极小的数组来储存禁止放置的情况（每次只需改变三个值）；

[编辑] 最后一位算出来

由于n行每一行都要有一个，那么所有的皇后的位置之和必然为n×(n+1)/2，在dfs的时候记录已经枚举的皇后位置之和，那么最后一个可以直接算出来。这样的话最后一个点0.907s。

经过测试，这种算法是不可行的。要看RP~

[编辑] 注意！

如果是C++，DFS使用数组储存的话--- 小心缓冲区漏洞，不然会输出各种匪夷所思的答案。

[编辑] 直接回溯

所有大神貌似各种各样神奇算法，但是这道题我貌似什么优化都没有…… 直接回溯就可以了：用三个vis数组分别记录‘|’、‘/’、‘\’三种列、对角线是否已经有皇后了然后就是回溯，毫无优化，但第一次就过了

void search(int cur) {

   if(cur==n)
   {
       num++;
       if(num<=3)
       {
           printf("%d",c[0]);
           for(int i=1;i<n;i++)
               printf(" %d",c[i]);
           printf("\n");
       }
       return;
   }
   for(int i=0;i<n;i++)
       if(!vis0[i]&&!vis1[i-cur+n-1]&&!vis2[cur+i])
       {
           c[cur]=i+1;
           vis0[i]=vis1[i-cur+n-1]=vis2[cur+i]=1;
           search(cur+1);
           vis0[i]=vis1[i-cur+n-1]=vis2[cur+i]=0;
       }

}

[编辑] DFS+位运算

可以考虑将问题分为两个子问题来处理:

a)求n皇后具体的方案;

b)求n皇后方案的个数;

对于问题a,因为只取前三个,用最简单的DFS即可办到.

对于问题b,可以考虑采用位运算,来递归模拟试放(考虑的条件与DFS类似),但不用储存具体方案.

用此方法通过全部数据耗时约0.4secs.源码
（根据位运算的具体操作细节时间还可以更快。我的是0.2左右--Ronice 23:23 2007年9月4日 (CST)）

详细的位运算细节见matrix67的Blog:http://www.matrix67.com/blog/archives/266 恩

[编辑] 全部细节位运算（DFS）

就是参照matrix67的Blog里求解的个数的算法，在输出前三个解这个要求上面加一点位运算技巧。连对称剪枝都不用最后一个点0.189秒杀！（还有倒数第二个0.027secs，其余全部0secs！）详细如下：对于matrix67的Blog所给的那个函数里(我写的C++版)

void test(int row,int ld,int rd)//row表示横行放皇后的情况，ld、rd分别是左右对角线的情况
{
     int pos,p;
     if(row!=upperlim)//upperlim表示全部都放上皇后的那种情况
     {
          pos=upperlim & ~(row|ld|rd);//pos表示还能在哪些位置上放皇后
          while(pos)
          {
                 p=pos & -pos;//p表示最右边的能放的那个位置
                 pos-=p;//放上这个位置
                 //***
                 test(row+p,(ld+p)<<1,(rd+p)>>1);//找下一个
          }
     }
     else
          sum++;
}

于是，如果要输出前三个解的话，需要记录，在每次递归调用test函数之前记录即可。而怎样从那仅有的五个（row,ld,rd,pos,p）中找出你所需要的那个位置是几呢？首先看，sum是当前已经有几个解了，所以在sum<3的情况下记录答案。其次看，USACO对那个输出的要求，仅需要输出列号，而在此函数中，那个p的二进制的唯一的那个一就表示这个列号，用log2（p）+1轻松取得。（需要<math.h>或者<cmath>）最后，那是第几行的呢？这个东西好像也可以在test函数中多加一个值传递进去，不过，用二进制怎么实现呢？再次从matrix67大牛的Blog上http://www.matrix67.com/blog/archives/264 找到求一个二进制数中1的个数的方法，废话不多说，我写的C++版：

inline int number(int row)
{
     row=(row&a[0])+((row>>1)&a[0]);
     row=(row&a[1])+((row>>2)&a[1]);
     row=(row&a[2])+((row>>4)&a[2]);
     row=(row&a[3])+((row>>8)&a[3]);
     row=(row&a[4])+((row>>16)&a[4]);
     return row;
}

其中const int a[]={0x55555555,0x33333333,0x0F0F0F0F,0x00FF00FF,0x0000FFFF}; 此时，我们就有了整个***处所要加的语句，如下

if(sum<3)
{
          int num=number(row),pnt=log2(p)+1;
          for(int i=sum;i<3;i++)
          list[i][num]=pnt;//list便是记录答案的数组，最节约的大小为list[3][13]
}

至此结束，位运算很神奇，是不？