專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

據澎湃新聞網報道，長沙童程童美少兒編程培訓機構一夜之間人去樓空。童程童美大家可能聽到的比較少，但如果說起達內教育，大家聽過的可能就比較多了。達內教育是2001年8月由加拿大海外專業人士在加拿大多倫多成立，在2015年推出少兒編程，2024年2月達內教育正式更名為童程童美。

達內教育最輝煌的時代可能是2008年到2015年，我曾經有不少同學在那里培訓過，剛開始的時候主要是以培訓java為主，2012，2013年移動互聯網火的一塌糊涂，他們又開始培訓Android和IOS，后來又搞大數據培訓和少兒編程培訓，沒想到這么快就不行了。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第51題：N 皇后。

問題描述

來源：LeetCode第51題

難度：困難

按照國際象棋的規則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n 皇后問題研究的是如何將 n 個皇后放置在 n×n 的棋盤上，并且使皇后彼此之間不能相互攻擊。

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

示例1：

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

示例2：

輸入：n = 1 輸出：[["Q"]]

• 1 <= n <= 9

問題分析

n皇后也就是在每行放一個皇后，并且每列以及斜對角都不能出現重復的皇后。放的時候也就是不斷嘗試的過程，所以它是一道經典的 回溯算法 題，關于回溯算法我在很久之前總結了一個模板，可以看下 。

對于每一行會有 n 個選擇，所以我們可以把它看作是一棵 n 叉樹，當然有些選擇可能會出現沖突，我們需要把它剪掉，如果放到最后一行沒有沖突，說明當前這個選擇是有效的，把它保存下來。當 n 等于 4 的時候會有兩種結果，如下圖所示，如果全部畫出來，圖會比較大，所以還一種被省略了。

JAVA：

public List
       
 > solveNQueens( int n) {      char[][] chess =  new  char[n][n];      // 初始化棋盤      for ( int i =  0; i < n; i++)          for ( int j =  0; j < n; j++)             chess[i][j] =  '.';     List > ans =  new ArrayList<>(); // 返回的結果     backtrack(ans, chess,  0); // 回溯算法      return ans; } private void backtrack(List > ans,  char[][] chess,  int row)  {      // 棋盤所有的行都遍歷完了，說明找到一個可行的解，把它加入到集合ans中      if (row == chess.length) {         ans.add(construct(chess));          return;     }      // 相當于一顆n叉樹      for ( int col =  0; col < chess.length; col++) {          // 判斷當前位置是否可以放皇后          if (valid(chess, row, col)) {              // 如果在當前位置放皇后不發生攻擊，就在當前位置放個皇后             chess[row][col] =  'Q';             backtrack(ans, chess, row +  1);  // 遞歸，下一行             chess[row][col] =  '.';  // 撤銷選擇         }     } } // row表示第幾行，col表示第幾列 private boolean valid(char[][] chess, int row, int col) {      // 判斷當前列有沒有皇后，因為他是一行一行往下走的，只需要檢查走過的行數即可      for ( int i =  0; i < row; i++) {          if (chess[i][col] ==  'Q')              return  false;     }      // 判斷當前坐標的右上角有沒有皇后      for ( int i = row -  1, j = col +  1; i >=  0 && j < chess.length; i--, j++) {          if (chess[i][j] ==  'Q')              return  false;     }      // 判斷當前坐標的左上角有沒有皇后      for ( int i = row -  1, j = col -  1; i >=  0 && j >=  0; i--, j--) {          if (chess[i][j] ==  'Q')              return  false;     }      return  true; } // 把數組轉為list private List   construct (char[][] chess)  {     List  path =  new ArrayList<>();      for ( char[] ches : chess)         path.add( new String(ches));      return path; }

C++：

public:
    vector

 > solveNQueens(int n) {         vector

  chess(n, string(n, '.')); // 初始化棋盤         vector

 > ans ;// 返回的結果         backtrack(ans, chess, 0);// 回溯算法         return ans;     }      void backtrack(vector

 > &ans, vector

 & chess, int row) {         // 棋盤所有的行都遍歷完了，說明找到一個可行的解，把它加入到集合ans中         if (row == chess.size()) {             ans.push_back(chess);             return;         }         // 相當于一顆n叉樹         for (int col = 0; col < chess.size(); col++) {             // 判斷當前位置是否可以放皇后             if (valid(chess, row, col)) {                 // 如果在當前位置放皇后不發生攻擊，就在當前位置放個皇后                 chess[row][col] = 'Q';                 backtrack(ans, chess, row + 1); // 遞歸，下一行                 chess[row][col] = '.'; // 撤銷選擇             }         }     }     // row表示第幾行，col表示第幾列      bool valid(vector

 & chess, int row, int col) {         // 判斷當前列有沒有皇后，因為他是一行一行往下走的，只需要檢查走過的行數即可         for (int i = 0; i < row; i++) {             if (chess[i][col] == 'Q')                 return false;         }         // 判斷當前坐標的右上角有沒有皇后         for (int i = row - 1, j = col + 1; i >= 0 && j < chess.size(); i--, j++) {             if (chess[i][j] == 'Q')                 return false;         }         // 判斷當前坐標的左上角有沒有皇后         for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {             if (chess[i][j] == 'Q')                 return false;         }         return true;     }

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。