N?皇后！

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

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

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

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

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

輸入：n = 4
輸出：[[".Q..","...Q","Q...","..Q."],
["..Q.","Q...","...Q",".Q.."]]
解釋?zhuān)? 皇后問(wèn)題存在兩個(gè)不同的解法。
我覺(jué)得你應(yīng)該能夠結(jié)合視頻動(dòng)畫(huà)和保姆級(jí)別的代碼注釋把這道題目弄清楚。

class?Solution?{

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

????public?List>?solveNQueens(int?n)?{
??????
??????//?attack?用來(lái)表示皇后的攻擊范圍
??????int[][]?attack?=?new?int[n][n];
??????//?queen?用來(lái)記錄皇后的位置
??????char[][]?queen?=?new?char[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);
??????}

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

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

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

????????//?如果發(fā)現(xiàn)在棋盤(pán)的最后一行放置好了皇后，那么就說(shuō)明找到了一組符合要求的解
????????if(k?==?n){
????????????//?由于?queen?為二維字符數(shù)組，所以需要轉(zhuǎn)換為字符串?dāng)?shù)組
????????????List?list?=?new?ArrayList<>();
????????????//?遍歷二維數(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(int?i?=?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?=?new?int[n][n];
????????????????
????????????????//?通過(guò)兩個(gè)?for?循環(huán)，把?attack?中的所有元素深度拷貝到?temp
????????????????for(int?l?=?0?;?l?????????????????????for(?int?m?=?0?;?m?????????????????????????temp[l][m]?=?attack[l][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
????private?void?checkQueenAttack(int?x?,int?y,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?的方向
????????int?dx[]?=?{?-1?,?-1?,?1?,?0??,??0?,??1??,?1?,?1?};
????????//?dy?表示?y?的方向
????????int?dy[]?=?{?-1?,?0??,?1?,?-1?,??1?,??-1?,?0?,?1?};

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

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

????????????????//?如果新位置的坐標(biāo)在?n?*?n?的棋盤(pán)范圍內(nèi)
????????????????if(nx?>=?0?