我今天好不容易上了一次課，然后數(shù)據(jù)結(jié)構(gòu)老師給我們留大作業(yè)也拜，喪心病狂以舒，先解決一個(gè)叫八皇后的問題。
題目背景：
【問題描述】
在一個(gè)８×８的棋盤里放置８個(gè)皇后慢哈，要求每個(gè)皇后兩兩之間不相"沖"（在每一橫列豎列斜列只有一個(gè)皇后）蔓钟。
【問題分析】
數(shù)組a、b卵贱、c分別用來標(biāo)記沖突滥沫，a數(shù)組代表列沖突，從a[0]~a[7]代表第0列到第7列键俱，如果某列上已經(jīng)有皇后兰绣，則為1，否則為0编振；
數(shù)組b代表主對角線沖突缀辩，為b[i-j+7]，即從b[0]~b[14]踪央，如果某條主對角線上已經(jīng)有皇后臀玄，則為1，否則為0畅蹂；
數(shù)組c代表從對角線沖突健无，為c[i+j]，即從c[0]~c[14]液斜，如果某條從對角線上已經(jīng)有皇后累贤，則為1募胃，否則為0；
【基本要求】
[if !supportLists]（1）?[endif]用遞歸算法實(shí)現(xiàn)
[if !supportLists]（2）?[endif]輸出所有棋盤狀態(tài)畦浓，其中空的地方為“*”痹束，放置皇后的地方為“@”
11．最小生成樹求解
【問題描述】
在n個(gè)城市之間建設(shè)網(wǎng)絡(luò)，只需保證連通即可讶请，求最經(jīng)濟(jì)的架設(shè)方法祷嘶。
【基本要求】
（1）假設(shè)已知n個(gè)城市之間的網(wǎng)絡(luò)是一個(gè)帶權(quán)連通無向圖。
（2）用鄰接矩陣COST表示給定的帶權(quán)連通無向圖夺溢。知陣元素定義為
（3）利用普里姆或克魯斯卡爾算法求圖的最小生成樹论巍。
然后我們現(xiàn)在工具問題的描述進(jìn)行分析：
首先，可歸納問題的條件為风响，8皇后之間需滿足：
???????????? 1.不在同一行上
?????????????2.不在同一列上
???????????? 3.不在同一斜線上
???????????? 4.不在同一反斜線上
???? 這為我們提供一種遍歷的思路嘉汰，我們可以逐行或者逐列來進(jìn)行可行擺放方案的遍歷，每一行（或列）遍歷出一個(gè)符合條件的位置状勤，接著就到下一行或列遍歷下一個(gè)棋子的合適位置鞋怀，這種遍歷思路可以保證我們遍歷過程中有一個(gè)條件是絕對符合的——就是下一個(gè)棋子的擺放位置與前面的棋子不在同一行（或列）。接下來持搜，我們只要判斷當(dāng)前位置是否還符合其他條件密似，如果符合，就遍歷下一行（或列）所有位置葫盼，看看是否繼續(xù)有符合條件的位置残腌，以此類推，如果某一個(gè)行（或列）的所有位置都不合適贫导，就返回上一行（或列）繼續(xù)該行（或列）的其他位置遍歷抛猫，當(dāng)我們順利遍歷到最后一行（或列），且有符合條件的位置時(shí)孩灯，就是一個(gè)可行的8皇后擺放方案闺金，累加一次八皇后可行方案的個(gè)數(shù)，然后繼續(xù)遍歷該行其他位置是否有合適的钱反，如果沒有掖看，則返回上一行，遍歷該行其他位置面哥，依此下去。這樣一個(gè)過程下來毅待，我們就可以得出所有符合條件的8皇后擺放方案了尚卫。這是一個(gè)深度優(yōu)先遍歷的過程，同時(shí)也是經(jīng)典的遞歸思路尸红。
????? 接下來吱涉，我們以逐列遍歷刹泄，具體到代碼，進(jìn)一步說明怎爵。
????????首先特石，從第一列開始找第一顆棋子的合適位置，我們知道鳖链，此時(shí)第一列的任何一個(gè)位置都是合適的姆蘸，當(dāng)棋子找到第一個(gè)合適的位置后，就開始到下一列考慮下一個(gè)合適的位置芙委，此時(shí)逞敷，第二列的第一行及第二行顯然就不能放第二顆棋子了，因?yàn)槠渑c第一個(gè)棋子一個(gè)同在一行灌侣，第二列第二行同在一條斜線上推捐。第二列第三行成為第二列第一個(gè)合適的位置，以此類推侧啼，第三列的第5行又會是一個(gè)合適位置牛柒，這個(gè)過程中，我們注意到痊乾，每一列的合適位置都是受到前面幾列的位置所影響焰络，歸納如下：
????? 假設(shè)前面1列的棋子放在第3行，那當(dāng)前列不能放的位置就一定是3行符喝，2行闪彼，4行。因?yàn)槿绻旁谶@三行上就分別跟前一列的棋子同在一行协饲、同在斜線畏腕、同在反斜線上，不符合我們的要求≤猿恚現(xiàn)在我們用cols數(shù)組來表示8個(gè)列棋子所放的行數(shù)描馅，數(shù)組下標(biāo)從0開始，其中數(shù)組下標(biāo)表示列數(shù)而线，數(shù)組的元素值表示該列棋子所在行數(shù)铭污，當(dāng)前列為N（N>=0,N<8），即cols[N-1]=3,則有：
????????????????????? cols[N] != cols[N-1]（=3膀篮，表示不在同一行）
???????????????????? ?cols[N] != cols[N-1]-1（=3-1=2嘹狞，表示不在同一斜線上)
???????????????????? ?cols[N]!=cols[N-1]+1(=3+1,表示不在同一反斜線上)
????? 這里我們注意到，如果N-2列存在的話誓竿，那么我們還要考慮當(dāng)前列N不與N-2列的棋子同行磅网，同斜線，同反斜線筷屡。把當(dāng)前列N的前面的某一列設(shè)為m,則m的所有取值為｛m>=0,m
??????????????????? cols[N] != cols[m]（與第m列的棋子不在同一行）
??????????????????? cols[N] != cols--[m] -（N-m）(>=0 ,與第m列的棋子不在同一斜線上)
??????????????????? cols[N] != cols--[m]?+ (N-m)? (<=8-1,與第m列的棋子不在同一反斜線上) ? ? ? ? ?
?????????? 具體到代碼涧偷，很顯然簸喂，取m的所有值只需要一句循環(huán)，同時(shí)我們?yōu)槊恳涣卸x一個(gè)長度為8的布爾數(shù)組row[],下標(biāo)同樣是從0開始燎潮，我們規(guī)定當(dāng)row[i]=true時(shí)喻鳄，表示該列第i行不能放棋子。這樣我們就能寫成下列程序段了：
增加一點(diǎn)：你其實(shí)也可以這樣子想确封，我某一行和下面一行的橫坐標(biāo)數(shù)字相差不能超出集合下標(biāo)的差除呵。因?yàn)槟氵@樣子想，我兩行最多相差16隅肥，因?yàn)槊看味际窍缺闅v第一行后再遍歷第二行竿奏，所以不能超出這個(gè)范圍。
第二點(diǎn)是：不能出現(xiàn)重復(fù)元素腥放。重復(fù)了還玩?zhèn)€球球泛啸。就是集合表示的元素。
public static int num =0; //累計(jì)方案總數(shù)
public static final int MAXQUEEN =8;//皇后個(gè)數(shù)秃症，同時(shí)也是棋盤行列總數(shù)
public static int[]cols =new int[MAXQUEEN]; //定義cols數(shù)組候址，表示8列棋子擺放情況
public Queen8() {//核心函數(shù)
? ? getArrangement(0);
? ? System.out.print("/n");
? ? System.out.println(MAXQUEEN+"皇后問題有"+num+"種擺放方法。");
}
public void? getArrangement(int n) {
//遍歷該列所有不合法的行种柑，并用rows數(shù)組記錄岗仑，不合法即rows[i]=true
? ? boolean[] rows =new boolean[MAXQUEEN];
? ? for (int i =0; i < n; i++) {
rows[cols[i]] =true;
? ? ? ? int d = n - i;
? ? ? ? if (cols[i] - d >=0) rows[cols[i] - d] =true;
? ? ? ? if (cols[i] + d <=MAXQUEEN -1) rows[cols[i] + d] =true;
? ? }
for (int i =0; i
//判斷該行是否合法
? ? ? ? if (rows[i])continue;
? ? ? ? //設(shè)置當(dāng)前列合法棋子所在行數(shù)
? ? ? ? cols[n] = i;
? ? ? ? //當(dāng)前列不為最后一列時(shí)
? ? ? ? if (n
getArrangement(n +1);
? ? ? ? }else {//累計(jì)方案個(gè)數(shù)
? ? ? ? ? ? num++;
? ? ? ? ? ? //打印棋盤信息
? ? ? ? ? ? printChessBoard();
? ? ? ? }
}
}
public void printChessBoard(){
System.out.print("\n"+"第"+num+"種走法 "+"\n");
? ? for(int i=0;i
for(int j=0;j
if(i==cols[j]){
System.out.print("0 ");
? ? ? ? ? ? }else
? ? ? ? ? ? ? ? System.out.print("+ ");
? ? ? ? }
System.out.print("\n");
? ? }
}
public static void main(String args[]){
Queen8 queen =new Queen8();
? ? queen.printChessBoard();
}
????????思路嘛其實(shí)很簡單，就是為了避免兩個(gè)棋子有相互接觸的空間聚请，然后先遍歷第一行荠雕，然后得到位置以后放到數(shù)組里面，然后遍歷第二行驶赏，獲取位置放到數(shù)組炸卑，然后進(jìn)行比對，看是否合適煤傍，合適繼續(xù)遍歷盖文，不合適就重新返回第一行重新規(guī)劃位置，繼續(xù)遍歷蚯姆。
? ? ? ? 這種題目屬于深度優(yōu)先遍歷的算法五续，當(dāng)然也很無聊。就是平常下棋的時(shí)候的用的招數(shù)龄恋，只是平常沒有想到還可以做算法疙驾，不過作為鍛煉思維，倒是一種很好的玩具篙挽。這個(gè)算法可以運(yùn)用到遞歸荆萤，不斷判斷然后return，繼續(xù)遍歷铣卡。
OK链韭，介紹完畢。
