本文共 1919 字，大约阅读时间需要 6 分钟。

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n , return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

Example:

Input: 4Output: [ [".Q..",  // Solution 1  "...Q",  "Q...",  "..Q."], ["..Q.",  // Solution 2  "Q...",  "...Q",  ".Q.."]]Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

题意：返回N皇后的具体方案。

思路：做过很多次的题目了，就是形成方案的时候有点麻烦。代码如下：

class Solution {
   public:    vector
   
     colNote;    //记录之前的每行(以1开始)的列号    vector
    
      colVis;    //记录列号是否被使用过    vector
     
      
       > ans;    //记录答案    string rowstr;          //记录每行的字符串答案    int endGame;    bool check(int row, int col) {
           for (int j = 0; j < row; ++j)             if (abs(col - colNote[j]) == abs(row - j))  //和前几行是否成对角线                return false;        return true;    }    void dfs(int row) {
           if (row >= endGame) {
                vector
       
         tmp;            for (int i = 0; i < colNote.size(); ++i) {
    //得到每行的列号                tmp.push_back(rowstr);                    tmp[i][colNote[i]] = 'Q'; //原来记录的行列都从1开始            }            ans.push_back(tmp);            return;        }        for (int i = 0; i < endGame; ++i) {
               if (!colVis[i] && check(row, i)) {
    //和前几行的列号是否相等或者成对角线                colNote[row] = i;                 colVis[i] = true;                dfs(row + 1);                colVis[i] = false;            }        }    }    vector
        
         
          > solveNQueens(int n) { if (n == 0 || n == 2 || n == 3) return vector
          
           
            >(); colNote.resize(n, 0); colVis.resize(n, false); endGame = n; rowstr.resize(n, '.'); dfs(0); //从第0行开始 return ans; }};
           
          
         
        
       
      
     
    
   

感觉写的不咋地，但还是比Python快得多：

转载地址：https://memcpy0.blog.csdn.net/article/details/108395562 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！