N 皇后！

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

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

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

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

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

輸入：n = 4
輸出：[[".Q..","...Q","Q...","..Q."],
["..Q.","Q...","...Q",".Q.."]]
解釋：4 皇后問題存在兩個不同的解法。
我覺得你應該能夠結合視頻動畫和保姆級別的代碼注釋把這道題目弄清楚。

class?Solution?{

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

????public?List>?solveNQueens(int?n)?{
??????
??????//?attack?用來表示皇后的攻擊范圍
??????int[][]?attack?=?new?int[n][n];
??????//?queen?用來記錄皇后的位置
??????char[][]?queen?=?new?char[n][n];

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

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

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

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

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

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

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

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

????????????????//?如果在?(?k?,?i?)?位置放置了皇后，那么就需要考慮在?k? ?1?行應該怎么放置其它的皇后了
????????????????//?由于有可能在(?k?,?i?)??位置放置了皇后之后，在后續(xù)的其它行會無法再放置其它的皇后
????????????????//?那么就需要回到?(?k?,?i?)??的狀態(tài)，考慮能不能在?(?k?,?i? ?1?)的位置放置
????????????????//?為了能夠回到?(?k?,?i?)??的狀態(tài)，所以需要先記錄此時的?attack
????????????????//?使用一個臨時的二維數(shù)組，深度拷貝?attack
????????????????//?如果不使用深度拷貝，而是直接使用?int[][]?temp?=?c
????????????????//?會導致?attack?發(fā)生改變是?temp?也會發(fā)生改變
????????????????//?這樣也就無法保存之前的狀態(tài)了
????????????????int[][]?temp?=?new?int[n][n];
????????????????
????????????????//?通過兩個?for?循環(huán)，把?attack?中的所有元素深度拷貝到?temp
????????????????for(int?l?=?0?;?l?????????????????????for(?int?m?=?0?;?m?????????????????????????temp[l][m]?=?attack[l][m];
????????????????????}
????????????????}

????????????????//?queen?用來記錄皇后的位置
????????????????//?那么?(?k?,?i?)??的位置?queen[k][i]?=?'Q'
????????????????queen[k][i]?=?'Q';

????????????????//?由于新放置了一個皇后，所以攻擊范圍又更多了
????????????????//?所以需要更新?attack?數(shù)組
????????????????//?新放置皇后的坐標為?(?k?,?i?)?，同樣的需要更新它的八個方向
????????????????checkQueenAttack(k,i,attack);
????????????????
????????????????//?如果在?(?k?,?i?)??位置放置了皇后，那么就需要考慮在?k? ?1?行應該怎么放置其它的皇后
????????????????//?遞歸的調(diào)用?backtrack?在?k? ?1?行放置皇后
????????????????backtrack(k? ?1,n,queen,attack);
????????????????
????????????????//?遞歸結束后，拿走皇后，恢復?attack?的狀態(tài)，考慮能不能在?(?k?,i? ?1?)的位置放置
????????????????attack?=?temp;

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


????}

????//?坐標?(?x?,?y)?為皇后所處的位置
????//?更新?attack
????private?void?checkQueenAttack(int?x?,int?y,int[][]?attack){

????????//?對于每一個坐標?(x,y)?來說，都有上、下、左、右、左上、左下、右上、右下?八個方向
????????//【左上】的坐標為?(x?-?1,?y?-?1)
????????//【上】的坐標為?(x?-?1,?y?)
????????//【右上】的坐標為?(x? ?1,?y? ?1)
????????//【左】的坐標為?(x,?y? ?1)
????????//【右】的坐標為?(x?,?y?-?1)
????????//【左下】的坐標為?(x? ?1,?y?-?1)
????????//【下】的坐標為?(x? ?1,?y)
????????//【右下】的坐標為?(x? ?1,?y? ?1)
????????//?通過兩個一維數(shù)組可以表示這八個方向
????????//?dx?表示?x?的方向
????????int?dx[]?=?{?-1?,?-1?,?1?,?0??,??0?,??1??,?1?,?1?};
????????//?dy?表示?y?的方向
????????int?dy[]?=?{?-1?,?0??,?1?,?-1?,??1?,??-1?,?0?,?1?};

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

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

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