/*
** http://blog.csdn.net/hackbuteer1/article/details/6657109
** 目前最快的N皇后遞歸解決方法
** N Queens Problem
** 試探-回溯算法，遞歸實現
*/
#include <cstdio>  
#include <cstdlib>  
  
const int N=20;   //最多放皇后的個數  
int q[N];         //各皇后所在的行號  
int cont = 0;     //統計解得個數  
//輸出一個解  
void print(int n)  
{  
    int i,j;  
    cont++;  
    printf("第%d個解：",cont);  
    for(i=1;i<=n;i++)  
        printf("(%d,%d) ",i,q[i]);  
    printf("\n");  
    for(i=1;i<=n;i++)        //行  
    {                  
        for(j=1;j<=n;j++)    //列  
        {  
            if(q[i]!=j)  
                printf("x ");  
            else   
                printf("Q ");   
        }  
        printf("\n");  
    }  
}  
//檢驗第i行的k列上是否可以擺放皇后  
int find(int i,int k)    
{  
    int j=1;  
    while(j<i)  //j=1~i-1是已經放置了皇后的行  
    {  
        //第j行的皇后是否在k列或(j,q[j])與(i,k)是否在斜線上  
        if(q[j]==k || abs(j-i)==abs(q[j]-k))   
            return 0;  
        j++;  
    }  
    return 1;  
}  
//放置皇后到棋盤上  
void place(int k,int n)    
{  
    int j;  
    if(k>n)  
        print(n);  
    else  
    {  
        for(j=1;j<=n;j++)   //試探第k行的每一個列  
        {  
            if(find(k,j))  
            {  
                q[k] = j;  
                place(k+1,n);  //遞歸總是在成功完成了上次的任務的時候才做下一個任務  
            }  
        }  
    }  
}  
  
int main(void)  
{  
    int n;  
    printf("請輸入皇后的個數(n<=20),n=:");  
    scanf("%d",&n);  
    if(n>20)  
        printf("n值太大，不能求解!\n");  
    else  
    {  
        printf("%d皇后問題求解如下(每列的皇后所在的行數):\n",n);  
        place(1,n);        //問題從最初狀態解起  
        printf("\n");  
    }  
    //system("pause");  
    return 0;  
}


**************************************************************


/*
** http://blog.csdn.net/hackbuteer1/article/details/6657109
** 目前最快的N皇后遞歸解決方法
** N Queens Problem
** 試探-回溯算法，遞歸高速實現
*/
#include <iostream>
#include <cstdlib>
#include <cstdio>
// #include <ctime>

using namespace std;

// sum用來記錄皇后放置成功的不同佈局數；upperlim用來標記所有列都已經放置好了皇后。
long sum = 0, upperlim = 1;     

// 試探算法從最右邊的列開始。
void test(long row, long ld, long rd)
{
	if (row != upperlim)
	{
		// row，ld，rd進行“或”運算，求得所有可以放置皇后的列,對應位為0，
		// 然後再取反後“與”上全1的數，來求得當前所有可以放置皇后的位置，對應列改為1
		// 也就是求取當前哪些列可以放置皇后
		long pos = upperlim & ~(row | ld | rd); 
		while (pos)    // 0 -- 皇后沒有地方可放，回溯
		{
			// 拷貝pos最右邊為1的bit，其餘bit置0
			// 也就是取得可以放皇后的最右邊的列
			long p = pos & -pos;                                              

			// 將pos最右邊為1的bit清零
			// 也就是為獲取下一次的最右可用列使用做準備，
			// 程序將來會回溯到這個位置繼續試探
			pos -= p;                           

			// row + p，將當前列置1，表示記錄這次皇后放置的列。
			// (ld + p) << 1，標記當前皇后左邊相鄰的列不允許下一個皇后放置。
			// (ld + p) >> 1，標記當前皇后右邊相鄰的列不允許下一個皇后放置。
			// 此處的移位操作實際上是記錄對角線上的限制，只是因為問題都化歸
			// 到一行網格上來解決，所以表示為列的限制就可以了。顯然，隨著移位
			// 在每次選擇列之前進行，原來N×N網格中某個已放置的皇后針對其對角線
			// 上產生的限制都被記錄下來了
			test(row + p, (ld + p) << 1, (rd + p) >> 1);                              
		}
	}
	else   
	{
		// row的所有位都為1，即找到了一個成功的佈局，回溯
		sum++;
	}
}

int main(int argc, char *argv[])
{
	time_t tm;
	int n = 8;

	if (argc != 1)
		n = atoi(argv[1]);
	tm = time(0);

	// 因為整型數的限制，最大只能32位，
	// 如果想處理N大於32的皇后問題，需要
	// 用bitset數據結構進行存儲
	if ((n < 1) || (n > 32))                 
	{
		printf(" 只能計算1-32之間\n");
		exit(-1);
	}
	printf("%d 皇后\n", n);

	// N個皇后只需N位存儲，N列中某列有皇后則對應bit置1。
	upperlim = (upperlim << n) - 1;         

	test(0, 0, 0);
	printf("共有%ld種排列, 計算時間%d秒 \n", sum, (int) (time(0) - tm));
	// system("pause");
	return 0;
}