遞歸與分治——N皇後問題 / 8皇後問題

題目概述：  在N×N格的國際象棋上擺放N個皇後，使其不能互相攻擊，即任意兩個皇後都不能處于同一行、同一列或同一斜線上，問有多少種擺法。

思路：對于此問題，可以将每列皇後的行号列舉出來，則問題轉化為1~n的一個全排列。

代碼一（暴力法）：

#include<stdio.h>
#include<stdbool.h>
#include<math.h>

int n,p[10],hashtable[10]={false};
int count=0;

int generatep(int index){
	if(index==n+1) {        //表示已經排列完畢，接下來判斷是否在同一條對角線上就可以 
		bool flag=true; 
		for(int i=1;i<=n;i++){                   //暴力枚舉 ，周遊任意兩個皇後
			for(int j=i+1;j<=n;j++){ 
				if(abs(i-j)==abs(p[i]-p[j])){    //同一對角線上 ：行差等于列差 
					flag=false;
				}
			} 
		}
		if(flag) count++;
		return count;
	}

	for(int x=1;x<=n;x++){          //枚舉1-n，試圖将x填入p[index] 
		if(hashtable[x]==false){    //如果x不在p[1]-p[index]中 
			p[index]=x;			    //将x填入到p[index]位置 
			hashtable[x]=true;	    //進行标記 
			generatep(index+1);     //處理後續的index+1
			hashtable[x]=false;     //處理完 p[index]為x的子問題後 ，對hashtable複原 
		}
	}
}
int main()
{
	printf("Input the Size of the Chess：");
	scanf("%d",&n);                 //問題規模
	generatep(1);     
	printf("Answer Number:%d\n",count);
	return 0;
}
           

代碼二（回朔法）：

#include<stdio.h>
#include<stdbool.h>
#include<math.h>

int n,p[10],hashtable[10]= {false};
int count=0;
int generatep(int index)
{
	if(index==n+1)//遞歸邊界，生成一個合法方案
	{
		count++;   //能到達這一步的都是合法的方案
		return count;
	}

	for(int x=1; x<=n; x++)//第x行
	{
		if(hashtable[x]==false) //第x行還沒有皇後
		{
			bool flag=true;//flag為true表示目前皇後和之前的皇後不會沖突
			for(int pre=1; pre<index; pre++) //周遊之前的皇後，第index列皇後行号為x，第pre列皇後的行号為p[pre]
			{
				if(abs(index-pre)==abs(x-p[pre]))   //處于同一對角線
				{
					flag=false;
					break;
				}
			}
			if(flag==true)//如果可以放置到同一對角線 
			{
				p[index]=x;			    //将x填入到p[index]位置
				hashtable[x]=true;	    //進行标記
				generatep(index+1);     //處理後續的index+1
				hashtable[x]=false;     //處理完 p[index]為x的子問題後 ，對hashtable複原
			}
		}
	}
}

int main()
{
	printf("Input the Size of the Chess：");
	scanf("%d",&n);
	generatep(1);
	printf("Answer Number:%d\n",count);
	return 0;
}
           

ps:回朔法可以避免很多不必要的計算。比如在放置完一部分皇後以後，可能剩餘的皇後無論怎麼放置都不合法，則沒必要繼續遞歸了，直接傳回上一層即可。