Uva 167 The Sultan's Successors

#八皇后 #The Sultan's Successors #Uva167
題目：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=103

算是八皇后問題之一，只是一直錯在遞迴的地方...昨天一直debug不出來...

寫這題的時候，順便回去複習了一下八皇后

======================八皇后解法======================

先橫向逐行放置皇后
將位置存至M[ i ] = j;
表示第 i 行的 的皇后在第 j 列

這樣皇后一定不會縱向攻擊，我們再來一一判斷是否會橫向攻擊或是對角線攻擊

位置(x,y) 的 y-x 表示了主對角線

位置(x,y) 的 x+y 表示了副對角線

如果x y 會混淆的話  也可以把上圖的x 、y 替代成 i 、j 


假如說我們已經放到第三行的皇后了，讓我們只要在判斷她和前面兩行的皇后有沒有衝突，code如下

//C表示，目前排到的行數

	for(int j = 0;j<目前的行數;j++)
	if(橫向衝突 || 主對角線衝突 || 副對角線衝突 ){
	flag = false;break;
	}
	if(flag) Search(C+1);

view raw 2.cpp hosted with ❤ by GitHub

	for(int j = 0;j<C;j++)
	if(M[C] == M[j] || C-M[C] == j-M[j] || C+M[C] == j+M[j] ){
	flag = false;break;
	}
	if(flag) Search(C+1);

view raw 2.cpp hosted with ❤ by GitHub

如果都沒有衝突的話，就接下去擺下一行的皇后。
直到皇后擺完8個，就可以將M[ ]的資料copy到Answer[ ][ ]裡面，等下比較好計算

	if(C==8){
	for(int i = 0;i<8;i++)
	answer[total][i] = M[i];
	total++;
	return;
	}

view raw 2.cpp hosted with ❤ by GitHub

等到92種排法都找到後，就可以讀入測資，並計算最大值了

完整程式碼：

	#include <cstdio>
	int answer[96][8],total = 0,M[8];
	bool flag;
	void Search(int C){
	if(C==8){
	for(int i = 0;i<8;i++)
	answer[total][i] = M[i];
	total++;
	return;
	}
	for(int i = 0 ; i<8;i++){
	M[C] = i;
	flag = true;
	for(int j = 0;j<C;j++)
	if(M[C] == M[j] || C-M[C] == j-M[j] || C+M[C] == j+M[j] ){
	flag = false;break;
	}
	if(flag)
	Search(C+1);
	}
	}
	int main(){
	int T,Max,sum,Empress[8][8];
	scanf("%d",&T);
	Search(0);
	while(T--){
	for(int i=0;i<8;i++){
	for(int j = 0;j < 8;j++){
	scanf("%d",&Empress[i][j]);
	}
	}
	Max = -1;
	for(int i = 0;i<92;i++){
	sum = 0;
	for(int j = 0;j < 8; j++)
	sum+=Empress[j][answer[i][j]];
	if(Max < sum) Max = sum;
	}
	printf("%5d\n",Max);
	}
	}

view raw uva167.cpp hosted with ❤ by GitHub