回溯算法經(jīng)典題目之N皇后

提到回溯算法那肯定離不開 n 皇后這道算法題，它實(shí)在是太經(jīng)典了。

所謂n 皇后問(wèn)題，指的是如何將n個(gè)皇后放置在n×n的棋盤上，并且使皇后彼此之間不能相互攻擊。

皇后彼此不能相互攻擊，也就是說(shuō)：任何兩個(gè)皇后都不能處于同一條橫行、縱行或斜線上。

給你一個(gè)整數(shù)n，返回所有不同的n 皇后問(wèn)題的解決方案。

每一種解法包含一個(gè)不同的n 皇后問(wèn)題的棋子放置方案，該方案中'Q'和'.'分別代表了皇后和空位。

輸入：n = 4
輸出：[[".Q..","...Q","Q...","..Q."],
["..Q.","Q...","...Q",".Q.."]]
解釋：4 皇后問(wèn)題存在兩個(gè)不同的解法。

我覺(jué)得你應(yīng)該能夠結(jié)合視頻動(dòng)畫和保姆級(jí)別的代碼注釋把這道題目弄清楚。

classSolution{

//保存所有符合要求的解
List>res=newArrayList<>();

publicList>solveNQueens(intn){

//attack用來(lái)表示皇后的攻擊范圍
int[][]attack=newint[n][n];
//queen用來(lái)記錄皇后的位置
char[][]queen=newchar[n][n];

//初始化二維數(shù)組queen中所有的元素為'.'
for(char[]c:queen){
Arrays.fill(c,'.');
}

//初始化二維數(shù)組attack中所有的元素為0
//0代表沒(méi)有皇后能攻擊得到
//1代表出于任意一個(gè)皇后的攻擊范圍內(nèi)
for(int[]c:attack){
Arrays.fill(c,0);
}

//從棋盤的第0行第0列處理n皇后的情況
backtrack(0,n,queen,attack);

//最后，返回所有符合要求的解
returnres;
}

//很顯然，每一行只能放置一個(gè)皇后，所以我們每一行每一行的來(lái)放置皇后
//k表示當(dāng)前處理的行
//n表示需要放置多少個(gè)皇后，同時(shí)也代表棋盤的大小為n*n
//queen用來(lái)記錄皇后的位置
//attack用來(lái)表示皇后的攻擊范圍
privatevoidbacktrack(intk,intn,char[][]queen,int[][]attack){

//如果發(fā)現(xiàn)在棋盤的最后一行放置好了皇后，那么就說(shuō)明找到了一組符合要求的解
if(k==n){
//由于queen為二維字符數(shù)組，所以需要轉(zhuǎn)換為字符串?dāng)?shù)組
Listlist=newArrayList<>();
//遍歷二維數(shù)組queen
//取出queen的每一行字符數(shù)組c
for(char[]c:queen){
//把字符數(shù)組c中的所有字符轉(zhuǎn)換為字符串的形式進(jìn)行拼湊
//比如['.','Q','.','.',]
//轉(zhuǎn)換為'.Q..'
//把這個(gè)字符串加入到list中
list.add(String.copyValueOf(c));
}

//list即為一組符合要求的解，把它加入到結(jié)果數(shù)組中
res.add(list);
//由于遍歷完了所有的行，無(wú)需再遍歷下去，所以返回
return;
}

//每一行只能放置一個(gè)皇后
//并且每一列也只能放置一個(gè)皇后
//所以在k行中，從0列到n-1列，判斷皇后應(yīng)該放置到哪個(gè)位置
for(inti=0;i//如果發(fā)現(xiàn)attack[k][i]==0
//說(shuō)明這個(gè)位置不在任何一個(gè)皇后的攻擊范圍內(nèi)
//所以可以考慮放置皇后
if(attack[k][i]==0){

//如果在(k,i)位置放置了皇后，那么就需要考慮在k+1行應(yīng)該怎么放置其它的皇后了
//由于有可能在(k,i)位置放置了皇后之后，在后續(xù)的其它行會(huì)無(wú)法再放置其它的皇后
//那么就需要回到(k,i)的狀態(tài)，考慮能不能在(k,i+1)的位置放置
//為了能夠回到(k,i)的狀態(tài)，所以需要先記錄此時(shí)的attack
//使用一個(gè)臨時(shí)的二維數(shù)組，深度拷貝attack
//如果不使用深度拷貝，而是直接使用int[][]temp=c
//會(huì)導(dǎo)致attack發(fā)生改變是temp也會(huì)發(fā)生改變
//這樣也就無(wú)法保存之前的狀態(tài)了
int[][]temp=newint[n][n];

//通過(guò)兩個(gè)for循環(huán)，把a(bǔ)ttack中的所有元素深度拷貝到temp
for(intl=0;lfor(intm=0;m//queen用來(lái)記錄皇后的位置
//那么(k,i)的位置queen[k][i]='Q'
queen[k][i]='Q';

//由于新放置了一個(gè)皇后，所以攻擊范圍又更多了
//所以需要更新attack數(shù)組
//新放置皇后的坐標(biāo)為(k,i)，同樣的需要更新它的八個(gè)方向
checkQueenAttack(k,i,attack);

//如果在(k,i)位置放置了皇后，那么就需要考慮在k+1行應(yīng)該怎么放置其它的皇后
//遞歸的調(diào)用backtrack在k+1行放置皇后
backtrack(k+1,n,queen,attack);

//遞歸結(jié)束后，拿走皇后，恢復(fù)attack的狀態(tài)，考慮能不能在(k,i+1)的位置放置
attack=temp;

//恢復(fù)queen的狀態(tài)，說(shuō)明此時(shí)皇后不放置在(k,i)位置
queen[k][i]='.';
}
}


}

//坐標(biāo)(x,y)為皇后所處的位置
//更新attack
privatevoidcheckQueenAttack(intx,inty,int[][]attack){

//對(duì)于每一個(gè)坐標(biāo)(x,y)來(lái)說(shuō)，都有上、下、左、右、左上、左下、右上、右下八個(gè)方向
//【左上】的坐標(biāo)為(x-1,y-1)
//【上】的坐標(biāo)為(x-1,y)
//【右上】的坐標(biāo)為(x+1,y+1)
//【左】的坐標(biāo)為(x,y+1)
//【右】的坐標(biāo)為(x,y-1)
//【左下】的坐標(biāo)為(x+1,y-1)
//【下】的坐標(biāo)為(x+1,y)
//【右下】的坐標(biāo)為(x+1,y+1)
//通過(guò)兩個(gè)一維數(shù)組可以表示這八個(gè)方向
//dx表示x的方向
intdx[]={-1,-1,-1,0,0,1,1,1};
//dy表示y的方向
intdy[]={-1,0,1,-1,1,-1,0,1};

//皇后所處的坐標(biāo)肯定是皇后能攻擊的位置，設(shè)置為1
attack[x][y]=1;

//以坐標(biāo)(x,y)為中心，去更新它八個(gè)方向的坐標(biāo)
for(intj=0;j8;j++){
//由內(nèi)向外的進(jìn)行更新
for(inti=1;i//新的位置的坐標(biāo)行為x+i*dx[j]
intnx=x+i*dx[j];
//新的位置的坐標(biāo)列為y+i*dy[j]
intny=y+i*dy[j];

//如果新位置的坐標(biāo)在n*n的棋盤范圍內(nèi)
if(nx>=0&&nx=0&&ny//那么這些位置就是在坐標(biāo)為（x，y）的皇后的攻擊范圍內(nèi)，更新為1
attack[nx][ny]=1;
}

}
}
}
}