如果你在第一章最后一题Checker卡住了,请看这里.
Chapter1最后一题Checker,即"n皇后".
DFS+位运算+剪枝.
即用位运算来进行状态判断.比如,在N=8时,要在某行的第4个位置放一个棋子,则可以表达为:00010000,也就是1<<4.这样的话,再加上适当的剪枝来搜索,就可以大大提高搜得效率.
那么又如何剪枝呢?我们可以考虑只枚举某些情况,其他情况可以通过枚举出来的情况通过对称,旋转等变换得到.
先看N为偶数的情况.为偶数的话,第一排只用枚举一半(1~N/2),剩下的一半可以由枚举出来的情况可以由前面的情况对称得到.
那么N为奇数的时候呢,就应该枚举中间列(第N div 2 +1 列)以及中间行(N div 3 + 1行)的前半部分(1~N div 2),并且,枚举时,中间列的枚举数应当大于中间行的枚举数,或者小于之.这样确定了后,就可以通过4种旋转*2种对称得到8种图形,并且是不重复的.剩下最后一种情况就是,刚好枚举点在最中心时,再全部枚举一遍.这样就找出所有方案数了.
方案数问题解决了后,就再写个裸搜,把前3种情况搜出来,便可以通过此题了.
经实验,通过N=13时,只需要0.2s.