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

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

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

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

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

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

我覺得你應該能夠結合視頻動畫和保姆級別的代碼注釋把這道題目弄清楚。

classSolution{

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

publicList>solveNQueens(intn){

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

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

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

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

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

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

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

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

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

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

//通過兩個for循環，把attack中的所有元素深度拷貝到temp
for(intl=0;lfor(intm=0;m//queen用來記錄皇后的位置
//那么(k,i)的位置queen[k][i]='Q'
queen[k][i]='Q';

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

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

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

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


}

//坐標(x,y)為皇后所處的位置
//更新attack
privatevoidcheckQueenAttack(intx,inty,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)
//通過兩個一維數組可以表示這八個方向
//dx表示x的方向
intdx[]={-1,-1,-1,0,0,1,1,1};
//dy表示y的方向
intdy[]={-1,0,1,-1,1,-1,0,1};

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

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

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

}
}
}
}