文章目錄

• N 皇后
• • 初始算法 ：
  • 修改后的算法
  • 優(yōu)化后的算法：
• 總結(jié)

---

N 皇后

??????題目鏈接：https://leetcode-cn.com/problems/n-queens/

??????題目描述：n 皇后問題 研究的是如何將 n 個皇后放置在 n×n 的棋盤上，并且使皇后彼此之間不能相互攻擊。

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

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

初始算法 ：

??????基于回溯的思想，一個較為粗略的程序如下：solve 函數(shù)中，每次選擇一個合適的位置（flag 為 false）來設(shè)置為 Q，然后更新當前棋盤上已有皇后的活動區(qū)域（設(shè)置為 true），然后繼續(xù)下一個位置的查找，直到 Q 的個數(shù) num 等于 n，即表示找到了一種正確的結(jié)果，保存并返回。 其中 flag 數(shù)組表示棋盤上已有的 Q 的活動區(qū)域。

List<List<String>> ans=new LinkedList<>();public List<List<String>> solveNQueens(int n) {char[][] tmp=new char[n][n];boolean[][] flag=new boolean[n][n];//用來標記棋盤上已有皇后的占領(lǐng)區(qū)域。for(int i=0;i<n;i++)for(int j=0;j<n;j++)tmp[i][j]='.';solve(tmp,n,flag,0);return ans;}public void solve(char[][] tmp,int n,boolean[][] flag,int num){if(num==n){ //成功時保存，且程序返回save(ans,tmp,n);return;}for(int i=0;i<n;i++)for(int j=0;j<n;j++){if(flag[i][j]==false){tmp[i][j]='Q';setDomin(flag,n,i,j,true);solve(tmp,n,flag,num+1);setDomin(flag,n,i,j,false);//需要采用別的方法恢復(fù)flag到上一個狀態(tài)。它和 setDomin(true)不是可逆的。tmp[i][j]='.';}}}public void setDomin(boolean[][] flag,int n,int i,int j,boolean status){for(int k=0;k<n;k++){//水平 豎直 方向flag[i][k]=status;flag[k][j]=status;}for(int k=1;k<n;k++){if(i+k<n&&j+k<n)//右下flag[i+k][j+k]=status;if(i-k>=0&&j-k>=0)//左上flag[i-k][j-k]=status;if(i-k>=0&&j+k<n)//左下flag[i-k][j+k]=status;if(i+k<n&&j-k>=0)//右上flag[i+k][j-k]=status;}}public void save(List<List<String>> ans,char[][] tmp,int n){ //將 char[][] 轉(zhuǎn)化為 List<String> 并保存List<String> t=new LinkedList<>();for(int i=0;i<n;i++)t.add(new String(tmp[i]));ans.add(t);}

??????上面代碼在回溯時出現(xiàn)問題，因為它不能恢復(fù) flag 到上一個狀態(tài)，所以需要修改，擬采用的解決方法為重新繪制除之間的所有 Q 的活動區(qū)域，而不包括當前的 Q ，當然，這需要保存之前的 Q 坐標，修改后的算法如下：

修改后的算法

?????? 1，增加變量 chosen 記錄了已經(jīng)選取的 Q 位置，方便我們重新設(shè)置 flag 數(shù)組（在將 flag 數(shù)組回退到上一個狀態(tài)時）。2，修改變量 ans 的類型為 Set ，因為在執(zhí)行的時候發(fā)現(xiàn)，雖然此算法的正確性沒有問題，但是需要優(yōu)化（包括剪枝），在 n 為 4 ，使用 List 存儲答案的情況下，得到的最終結(jié)果有 48 個， 而每 24 個一摸一樣，所以目前先建立了一個 Set 來去掉重復(fù)的元素，保證可以得到正確的結(jié)果。

Set<List<String>> ans=new HashSet<>();public List<List<String>> solveNQueens(int n) {char[][] tmp=new char[n][n];boolean[][] flag=new boolean[n][n];//用來標記棋盤上已有皇后的占領(lǐng)區(qū)域。for(int i=0;i<n;i++)for(int j=0;j<n;j++)tmp[i][j]='.';LinkedList<int[]> chosen=new LinkedList<>();//用來保存已有的皇后坐標。solve(tmp,n,flag,0,chosen);List<List<String>> re=new LinkedList<>();re.addAll(ans);return re;}public void solve(char[][] tmp,int n,boolean[][] flag,int num,LinkedList<int[]> chosen){if(num==n){ //成功時保存，且程序返回save(ans,tmp,n);return;}for(int i=0;i<n;i++)for(int j=0;j<n;j++){if(flag[i][j]==false){tmp[i][j]='Q';chosen.addLast(new int[]{i,j});setDomin(flag,n,i,j,true);solve(tmp,n,flag,num+1,chosen);chosen.removeLast();//刪除當前 Q 的位置cancel(flag,n,chosen);// 重新設(shè)置 flag 數(shù)組到上一個狀態(tài)。tmp[i][j]='.';}}}public void cancel(boolean[][] flag,int n,LinkedList<int[]> chosen){for(int i=0;i<n;i++)Arrays.fill(flag[i],false);for(int[] t:chosen)setDomin(flag,n,t[0],t[1],true);}public void setDomin(boolean[][] flag,int n,int i,int j,boolean status){for(int k=0;k<n;k++){//水平 豎直 方向flag[i][k]=status;flag[k][j]=status;}for(int k=1;k<n;k++){if(i+k<n&&j+k<n)//右下flag[i+k][j+k]=status;if(i-k>=0&&j-k>=0)//左上flag[i-k][j-k]=status;if(i-k>=0&&j+k<n)//左下flag[i-k][j+k]=status;if(i+k<n&&j-k>=0)//右上flag[i+k][j-k]=status;}}public void save(Set<List<String>> ans,char[][] tmp,int n){List<String> t=new LinkedList<>();for(int i=0;i<n;i++)t.add(new String(tmp[i]));ans.add(t);}

?????? 上面算法屬于暴力枚舉，其時間復(fù)雜度很高。對它進行優(yōu)化如下：

優(yōu)化后的算法：

??????參考對應(yīng)官方題解，由于上述暴力枚舉的時間復(fù)雜度非常高，需要利用限制條件加以優(yōu)化。

??????需要說明的是，下面算法仍然和之前的算法類似，大體的回溯框架沒有變化。唯一變化的是如何判斷標記棋盤上已有皇后的占領(lǐng)區(qū)域，或者說是下一個皇后可以放置的位置區(qū)域。它采用了 3 個集合來降低之前算法進行標記的時間復(fù)雜度。

??????將之前的二維數(shù)組表示皇后位置轉(zhuǎn)化為只用一個數(shù)組 queens 來表示，比如對于 queens[0]=1 ，表示在第0行第1列放置一個皇后。一旦 queens 數(shù)組被填滿元素，那么我們就得到了一個放置結(jié)果。

??????當在 queens 數(shù)組放置新元素時(即在下一行填充新的皇后位置時)：因為肯定是不同行，所以需要關(guān)心的是新皇后位置和已有的皇后位置是否在相同列；和已有的皇后位置是否在同一條左上右下斜線上；和已有的皇后位置是否在同一條右上左下斜線上。而 3 個集合的功能就是用來分別判斷這三種情況的。

??????columns 數(shù)組保存已有皇后的列下標（判斷 columns 中是否已經(jīng)包含了新位置的列下標）
??????diagonals1 數(shù)組保存已有皇后的左上右下斜線位置，比如位置(1,2)，由于經(jīng)過(1,2)的此斜線上所有點(x,y)滿足" 1-2 == x-y “關(guān)系，那么這一條斜線就可以用 -1(1-2) 來表示，即保存 -1 到diagonals1 中（判斷 diagonals1 是否已經(jīng)包含的新位置所在左上右下斜線，即新位置的行下標減去列下標的值）
??????diagonals2 數(shù)組保存已有皇后的右上左下斜線位置，比如位置(1,2)，由于經(jīng)過(1,2)的此斜線上所有點(x,y)滿足” 1+2 == x+y "關(guān)系，那么這一條斜線就可以用 3(1+2) 來表示，即保存 3 到diagonals2 中（判斷 diagonals2 是否已經(jīng)包含的新位置所在左上右下斜線，即新位置的行下標加上列下標的值）

??????如下面算法所示：（每行代碼的功能已經(jīng)注明，可參考理解）

public List<List<String>> solveNQueens(int n) {List<List<String>> solutions=new ArrayList<>();int[] queens=new int[n]; //保存每一行中成功放置皇后的下標。Arrays.fill(queens,-1);Set<Integer> columns=new HashSet<>();//記錄每一列是否可以放置新的皇后Set<Integer> diagonals1=new HashSet<>();//記錄左上右下斜線上是否可以放置新的皇后Set<Integer> diagonals2=new HashSet<>();//記錄右上左下斜線上是否可以放置新的皇后backtrack(solutions,queens,n,0,columns,diagonals1,diagonals2); // row 表示已經(jīng)放置了多少行的皇后return solutions;}public void backtrack(List<List<String>> solutions,int[] queens,int n,int row,Set<Integer> columns,Set<Integer> diagonals1,Set<Integer> diagonals2){if(row==n){List<String> board=generateBoard(queens,n);solutions.add(board);}else{for(int i=0;i<n;i++){//上述三個判斷語句如果有任意一個為 true，即表示當前位置(row,i)不能被放置新的皇后，所以需要跳過。//并且使用 Set 來存儲，可以順帶著去重。比如columns中不同的兩行但是列下標相同，就沒必要存儲了；diagonals1中同一條斜線上的元素也沒必要存儲了...if(columns.contains(i))continue;int diagonal1=row-i;//左上右下一條斜線上元素的行下標與列下標之差相等。if(diagonals1.contains(diagonal1))continue;int diagonal2=row+i;//右上左下一條斜線上元素的行下標與列下標之和相等。if(diagonals2.contains(diagonal2))continue;queens[row]=i; //此時在位置(row,i)上找到了一個可以放置新皇后的位置columns.add(i);//將該列下標加入columns。diagonals1.add(diagonal1);//將 (row,i) 表示的對應(yīng)方向的斜線加入 diagonals1diagonals2.add(diagonal2);//將 (row,i) 表示的對應(yīng)方向的斜線加入 diagonals2backtrack(solutions,queens,n,row+1,columns,diagonals1,diagonals2); //回溯判斷每一種放置的可能性。queens[row]=-1; //恢復(fù)到在此位置放置新皇后之前的狀態(tài)。columns.remove(i);diagonals1.remove(diagonal1);diagonals2.remove(diagonal2);}}}public List<String> generateBoard(int[] queens,int n){ //將已經(jīng)找到符合條件的 queens 數(shù)組轉(zhuǎn)換為標準的返回值(List<String>類型)List<String> board=new ArrayList<>();for(int i=0;i<n;i++){char[] row=new char[n];Arrays.fill(row,'.');row[queens[i]]='Q';board.add(new String(row));}return board;}

總結(jié)

??????目前來看，這道題的整體思路和代碼框架是很容易實現(xiàn)的，關(guān)鍵的問題在于如何描述新皇后的可選位置區(qū)域這塊，并盡可能地降低時間復(fù)雜度。

總結(jié)

以上是生活随笔為你收集整理的LeetCode算法题9：递归和回溯-N皇后问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。