算法程式設計(JAVA)--八皇後問題

題目：在一個8×8國際象棋盤上，有8個皇後，每個皇後占一格；

要求皇後間不會出現互相“攻擊”的現象，即不能有兩個皇後處在同一行、同一列或同一對角線上。

問共有多少種不同的方法？

解題思路：通過一個int[8][8]的二位數組建構棋盤，初始化為0，我們可以定義如果該位置擺放了皇後那麼該位置對應的二維數組被置為-1。因為皇後之間不能互相攻擊，是以我們要明确指出該皇後的影響範圍，于是我們采用将該皇後能影響到的棋盤位置全部+1,比如：

-11111111
11000000
10100000
10010000
10001000
10000100
10000010
10000001
           

這樣我們就可以判斷，隻要是0的地方就可以放置皇後，隻要是-1就是皇後的位置，隻要是大于0的地方就是被皇後影響的地方。這樣做有個什麼好處呢，就是我們再回溯時隻需要通過簡單的對皇後的影響範圍進行-1就可以取消她的影響範圍了。下面直接貼出代碼，後面有注釋。如果讀者有什麼疑惑可以給我留言~~

<pre name="code" class="java">public class Main {
	static int[][] Arr = new int[8][8];
	static int Count=0;
	
	public static void main(String[] args){
		Cal(0,0);//遞歸函數，傳入目前選中位置是第幾行第幾列
		System.out.println(Count);
	}
	public static void Cal(int a,int b){
		if(a==8){
			Count++;
			for(int j=0;j<8;j++){//尋找第8行已經擺放了的皇後的位置
				if(Arr[7][j]==-1){
					Sub(7,j);//找到後拿掉皇後，并且取消掉該皇後的影響
					return;
				}
			}
		}
		else{
			boolean Flag=true;//設定一個标志位，用來判斷該行是否還有可以擺放皇後的位置
			for(int i=0;i<8;i++){
				if(Arr[a][i]==0){
					Flag=false;//若有可以擺放皇後的位置，将标志位置為false
					Add(a,i);//擺放這個皇後，并且添加該皇後的影響
					Cal(a+1,i);//将下一個狀态帶入狀态方程
				}
			}
			if(Flag==true){//如果沒有找到可以擺放皇後的位置，就取消掉上一層的皇後的位置，并且消除該皇後的影響
				Sub(a-1,b);
				return;
			}
			if(Flag==false&&a>0){//如果有改層有可以擺放皇後的位置，就要在回溯時拿掉該皇後，并且取消該皇後的影響
				for(int i=0;i<8;i++){
					if(Arr[a-1][i]==-1){
						Sub(a-1,i);
						return;
					}
				}
			}
			return;
		}
		
	}
	public static void Add(int x,int y){//添加皇後，并且添加該皇後的影響
		Arr[x][y]=-1;
		for(int i=0;i<8;i++){
			if(i!=y)
			Arr[x][i]=Arr[x][i]+1;
		}
		for(int i=0;i<8;i++){
			if(i!=x)
			Arr[i][y]=Arr[i][y]+1;
		}
		for(int i=-7;i<8;i++){//左上到右下
			if((i+x)>=0&&(i+x)<8&&i!=0&&(i+y)>=0&&(i+y)<8){
				Arr[x+i][y+i]=Arr[x+i][y+i]+1;
			}
		}
		for(int i=-7;i<8;i++){//左下到右上
			if((x-i)>=0&&(x-i)<8&&i!=0&&(i+y)>=0&&(i+y)<8){
				Arr[x-i][y+i]=Arr[x-i][y+i]+1;
			}
		}
	}
	public static void Sub(int x,int y){//消去該皇後的影響
		Arr[x][y]=0;
		for(int i=0;i<8;i++){
			if(i!=y)
			Arr[x][i]=Arr[x][i]-1;
		}
		for(int i=0;i<8;i++){
			if(i!=x)
			Arr[i][y]=Arr[i][y]-1;
		}
		for(int i=-7;i<8;i++){//左上到右下
			if((i+x)>=0&&(i+x)<8&&i!=0&&(i+y)>=0&&(i+y)<8){
				Arr[x+i][y+i]=Arr[x+i][y+i]-1;
			}
		}
		for(int i=-7;i<8;i++){//左下到右上
			if((x-i)>=0&&(x-i)<8&&i!=0&&(i+y)>=0&&(i+y)<8){
				Arr[x-i][y+i]=Arr[x-i][y+i]-1;
			}
		}
	}
}