N Queens

NQueens.md

#N Queens

##DFS

N皇后非常经典，传统的DFS在N非常大的时候会TLE，DFS代码如下：

    void placeQueens(int currentRow, int n, vector<int>& place, int& result)
    {
    	if(currentRow == n)
    	{
    		++result;
    		return;
    	}
    
    	for(int col = 0; col < n; col++)
    	{
    		place[currentRow] = col;
    		if(check(currentRow,place))
    		{
    			placeQueens(currentRow+1,n,place,result);
    		}
    	}
    }
    bool check(int row, vector<int>& place)
    {
    	for(int i = 0; i < row; i++)
    	{
    		int diff = abs(place[row] - place[i]);
    		if(diff == 0 || diff == row - i)
    		{
    			return false;
    		}
    	}
    	return true;
    }
    int totalNQueens(int n)
    {
    	vector<int> place(n,0);
    	int result = 0;
    	placeQueens(0,n,place,result);
    	return result;
    }

##位运算

和普通算法一样，这是一个递归函数，程序一行一行地寻找可以放皇后的地方。函数带三个参数row、ld和rd，分别表示在纵列和两个对角线方向的限制条件下这一行的哪些地方不能放。位于该行上的冲突位置就用row、ld和rd中的1来表示。把它们三个并起来，得到该行所有的禁位，取反后就得到所有可以放的位置（用pos来表示）。

    p = pos & (~pos+1)

其结果是取出最右边的那个1。这样，p就表示该行的某个可以放子的位置，把它从pos中移除并递归调用。

    void placeQueensBits(long n, long row, long ld, long rd, int& result)
    {
    	if(row != n)
    	{
    		//get available pos
    		long pos = n & ~(row | ld | rd);
    		while(pos)
    		{
    			//get rightest bit 1
    			//pos &(~pos + 1)
    			long p = pos & -pos;
    			//clear rightest bit 1
    			pos -= p;
    			//
    			placeQueensBits(n,row | p,(ld | p) << 1,(rd | p) >> 1,result);
    		}
    	}
    	else
    	{
    		result++;
    	}
    }
    int totalNQueensBits(int num)
    {
    	long n = (1 << num) - 1;
    	int result = 0;
    	placeQueensBits(n,0,0,0,result);
    	return result;
    }

##Testing