n皇后问题，状态压缩

N皇后问题

Description

八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后。为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当 n = 1 或 n ≥ 4 时问题有解。

Input

一个数n，表示棋盘大小为n*n，有n个皇后。

Output

只有一个数字，为解的个数。当没有解时输出0。

Sample Input

Sample Output

AC 通道： http://oj.changjun.com.cn/problem/detail/pid/1099

这是一个经典的状态压缩题，用到了大量的位运算；

首先看到这题，我们的第一想法是，仍像8皇后问题那样开列数组与对角线的数组，采用搜索回溯法，但我们知道

搜索时,数组里面存的无非就是存当前位置有没有皇后,使用一个LL去存储当前的状态,然后通过存的状态去搜索即可,状态的修改通过位移以及位运算符进行修改即可,大大节约空间和时间（这也是节约能源啊）！

具体来说，初始化一个棋盘，默认为空，即全为0，连续的64个0，

假设棋盘放了皇后，放置成这样：

则用二进制表示为1(9个0)1(53个0)

如果要在某个位置放一个皇后，表达式为p=p|(1<<xx)

例如，在(7,6)处放置一个皇后，xx为8*(8-7)+(8-6),也就是将一个二维坐标转为1维然后存入一个数组中

下面看下代码实现。。。

//  I'm YinPengzhe    Congratulations!

 1 #include<cstdio>
 2 //#include<iostream>
 3 int N,Ans;
 4 void dfs(int Col,int Maindig,int assdig)// Col 列的情况  Maindig 主对角线  assdig 副对角线
 5 {
 6     if(Col==(1<<N)-1) {
 7         Ans++;
 8         return;
 9     }
10     int empty_col=((1<<N)-1) & (~ (Col|Maindig|assdig));
11     while(empty_col) {
12         int cal=empty_col & ((~ empty_col)+1);
13         empty_col &= ~cal;
14         dfs(Col|cal,(Maindig|cal) >> 1,(assdig|cal) << 1);
15     }
16     return;
17 }
18 int main() {
19     scanf("%d",&N);
20     Ans=0;
21     dfs(0,0,0);
22     printf("%d",Ans);
23     return 0;
24 }

View Code

中间一些位运算的操作具体时间这样的；

Col是表示列的拜访情况，如果到了终点状态，则左右的列上都会摆一个1，那么对应的2进制数为(1<<N)-1;

所以Col & ((1<<N)-1) 即为目标状态

empty_col 为当前状态下所有能拜1 的情况，即算出来后每一位能摆1 的都为 1 ,(Col|Maindig|assdig)为所有情况，~则把摆了的变为0，能摆的变为1；所以与全部都为1的((1<<N)-1) & 则为当前值；

cal=empty_col & ((~ empty_col)+1);这是取最末尾的1的值

我们想，e & （~e）肯定为0；

假设e 的从末尾数第一个为1的位值为First

则First后的全为0;当取反后，First变为了0，前面全为1,+1后一直进位到First，Firtst成为了1,她后面的全变为了0;

First前应为反了一次，所以 & e 肯定是0，First 后的也一定为0,所以得到的即是第一个1的值;//十分巧妙吧吐舌头

empty_col &= ~cal;  删去她;

此处推荐一个讲的很好的博客：  http://blog.csdn.net/txl199106/article/details/55505785

YEAH

我想要的我自然会认真.