為了使腦袋不生銹，偶爾還是需要給腦子運(yùn)動(dòng)一下爬范。今天找了一個(gè)leetCode上的一個(gè)算法來(lái)運(yùn)動(dòng)一下。
題目是這樣的：
在 8 X 8 的網(wǎng)格中弱匪，放入八個(gè)皇后（棋子）青瀑，滿(mǎn)足的條件是，任意兩個(gè)皇后（棋子）都不能處于同一行萧诫、同一列或同一斜線(xiàn)上斥难，問(wèn)有多少種擺放方式？
如果有興趣的同學(xué)可以先自己思考一下帘饶，這個(gè)題目應(yīng)該如何做哑诊。在看可能會(huì)更有體會(huì)。因?yàn)橹饕皇谴a及刻，看的還是思路 所以就沒(méi)有優(yōu)化代碼了镀裤，可能代碼比較粗糙。進(jìn)入正題：
題目描述的大概意思是缴饭，如何擺放八顆棋子是每顆棋子的上下左右 以及兩邊的正斜對(duì)角線(xiàn)上沒(méi)有棋子出現(xiàn)暑劝。用圖來(lái)描述就是
圖1表示的是一個(gè)正確的，圖二因?yàn)橛蚁碌男本€(xiàn)上出現(xiàn)了同樣的一個(gè)所以是不符合條件颗搂。
首先說(shuō)一下解題思路担猛。因?yàn)槭且粋€(gè)8*8的格子，又同時(shí)需要放八個(gè)棋子丢氢。所以我們第一個(gè)得到的信息是每一行有且僅有一個(gè)棋子毁习。因?yàn)樾本€(xiàn)部分影響的因素很多所以暫時(shí)是不能得到什么有效的訊息。如果我們首先就將斜線(xiàn)的部分都考慮進(jìn)去的話(huà)卖丸。這個(gè)干擾因素就會(huì)越來(lái)越多到最后我們只能選擇放棄纺且。既然不能一下從全局解決這個(gè)問(wèn)題那就只能將復(fù)雜問(wèn)題簡(jiǎn)單化，先從局部開(kāi)始著手稍浆。
首先我們從第一行開(kāi)始分析载碌，因?yàn)槭堑谝粋€(gè)棋子所以在第一行什么位置都是可以的猜嘱。但是為了后面的統(tǒng)一化，我們都是將棋子從最左邊開(kāi)始放嫁艇。比如我們將第一個(gè)棋子放在（0朗伶，0）位置。注意我這里是將整個(gè)棋盤(pán)看成一個(gè)長(zhǎng)度為8的二維數(shù)組步咪。左上角為（0论皆，0）位置。接下來(lái)我們?cè)诘诙械淖钭筮叿诺诙€(gè)棋子猾漫。注意這時(shí)候我們需要判斷這個(gè)位置是否符合條件点晴。也就是上下左右以及斜面都不能有棋子。就這樣以此類(lèi)推悯周。這個(gè)復(fù)雜的問(wèn)題就是：我在第每行放棋子的時(shí)候進(jìn)行以此判斷粒督，如果不符合條件自動(dòng)水平往右移動(dòng)一位，繼續(xù)判斷禽翼。直到我在第八行找到合適的位置時(shí)屠橄，表示已經(jīng)找到了一個(gè)符合條件的正確解。分析到這里闰挡，這個(gè)復(fù)雜的問(wèn)題是不是就已經(jīng)分解成锐墙，我只需要每次放棋子的時(shí)候判斷棋子的位置時(shí)候符合條件的一個(gè)遞歸問(wèn)題了。同時(shí)這個(gè)遞歸結(jié)束的條件就是在第八行找到合適的位置放下棋子就表示這一次尋找結(jié)束了长酗。
注意
這里我們要注意一個(gè)問(wèn)題：就是我們可能第一次放棋子的位置不對(duì)導(dǎo)致找不到最優(yōu)解贮匕。這時(shí)我們還需要考慮 回溯問(wèn)題 就是回退到上一個(gè)我們的位置繼續(xù)尋找。這樣才能保證找到所有的最優(yōu)解花枫。 接下來(lái)就是代碼來(lái)演示了：
/**
在 8 X 8 的網(wǎng)格中刻盐，放入八個(gè)皇后（棋子），
滿(mǎn)足的條件是劳翰，任意兩個(gè)皇后（棋子）都不能處于同一行敦锌、同一列或同一斜線(xiàn)上，問(wèn)有多少種擺放方式佳簸？
*/
public class Def {
public static int[][] checkerboard = new int[8][8];//棋盤(pán)
// 打印符合條件的棋子位置
public static void print(){
for(int i=0;i<checkerboard.length;i++){
for(int j=0;j<checkerboard[i].length;j++){
if(checkerboard[i][j] == 0){
System.out.print(checkerboard[i][j]+" ");
}else{
System.out.print(checkerboard[i][j]+" ");
}
}
System.out.println();
}
}
// 檢查當(dāng)前棋子的位置是否符合條件
public static Boolean check2(int x,int y){
if(x>7 || x<0 || y<0 || y >7) return false;
if(checkerboard[x][y] != 0 ) return false;
for(int i=0;i<8;i++){
if(checkerboard[x][i] != 0) return false;
}
for(int i=0;i<8;i++){
if(checkerboard[i][y] != 0) return false;
}
if(!recursion2(x-1,y-1,"leftTop")) return false;
if(!recursion2(x-1,y+1,"leftDown")) return false;
if(!recursion2(x+1,y+1,"rightDown")) return false;
if(!recursion2(x+1,y-1,"rightTop")) return false;
return true;
}
// 對(duì)斜線(xiàn)上的位置進(jìn)行檢查
public static Boolean recursion2(int x,int y,String direction){
Boolean flag = true;
switch (direction) {
case "leftTop":
while (x>=0 && y>=0){
if(checkerboard[x][y]!=0) {
flag = false;
return flag;
}
x--;
y--;
}
break;
case "leftDown":
while (x>=0 && y<=7){
if(checkerboard[x][y]!=0) {
flag = false;
return flag;
}
x--;
y++;
}
break;
case "rightTop":
while (x<=7 && y>=0){
if(checkerboard[x][y]!=0) {
flag = false;
return flag;
}
x++;
y--;
}
break;
case "rightDown":
while (x<=7 && y<=7){
if(checkerboard[x][y]!=0) {
flag = false;
return flag;
}
x++;
y++;
}
break;
}
return flag;
}
public static int count = 0;
public static void add2(int x){
// 滿(mǎn)足條件的棋子條件
if(x == 8) {
count++;
print();
System.out.println("=============================");
return;
}
for(int i=0;i<8;i++){
if(check2(x,i)){
checkerboard[x][i] = 1;
x++;// 這里++是推動(dòng)下一行
add2(x);
x--;// 注意這里很重要 這就是處理 回溯問(wèn)題 需要會(huì)到上一次的位置
checkerboard[x][i] = 0;//將上一次的記錄抹掉
}
}
}
public static void main(String[] args) {
add2(0);
System.out.println(count);
}
}
整個(gè)過(guò)程大概就是這樣了乙墙。代碼部分的注釋比較清楚，不明白的可以去看一下注釋生均。
