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

问题分析

第一题

问题一要求在一个m x m的矩阵中放置m个皇后，使得它们互不攻击。技巧是从左到右逐行放置，但确认当前放置的位置不会与前面任何一行的位置在相同的列或对角线上。我们需要递归地为每一行寻找合适的列，直到所有皇后都放置完成。

第二题

问题二要求使用仅一维数组记录皇后放置的位置，因为行是固定的，不会出现同一行放置多个皇后的情况。只需确保每个行的列和对角线不冲突。这种方法能更高效地减少不必要的检查过程。

完整代码分析

第一题代码解析

#include 
   
    
#include 
    
     
using namespace std;
class Solution {
public:
    vector
     
      
       > vec;
    int col[50];
    void search(vector
       
        
         > vec, int row, int n) { if (row == n) { return; } for (int i = 0; i < n; ++i) { int j; for (j = 0; j < row; ++j) { if (i == col[j] || abs(i - col[j]) == abs(row - j)) { break; } } if (j == row) { col[row] = i; vec[row][i] = 'Q'; search(vec, row + 1, n); vec[row][i] = '.'; } } } vector
         
          
           > solveNQueens(int n) { vector
           
            
             > vec; string s(n, '.'); vec.push_back(s); search(vec, 0, n); return ans; } };
            
           
          
         
        
       
      
     
    
   

第一题使用了回溯算法，每个回溯步骤选择当前行的列位置，检查是否与前面各行的列和对角线冲突。通过递归逐步放置，确保满足条件，最终得到所有可能的布局。

第二题代码解析

#include 
   
    
using namespace std;
class Solution {
public:
    int ans = 0;
    int col[10];
    void search(int idx, int n) {
        if (idx == n) {
            ans++;
            return;
        }
        for (int i = 0; i < n; ++i) {
            int ok = 1;
            col[idx] = i;
            for (int j = 0; j < idx; ++j) {
                if (col[idx] == col[j] || abs(col[idx] - col[j]) == abs(idx - j)) {
                    ok = 0;
                    break;
                }
            }
            if (ok) {
                search(idx + 1, n);
            }
            col[idx] /= n;
        }
    }
    int totalNQueens(int n) {
        search(0, n);
        return ans;
    }
};
   

第二题同样采用了回溯算法，但通过记录列位置为一维数组，减少了检查次数，优化了性能。每个回溯步骤选择一个列位置，检查是否满足不与前面的位置产生冲突，然后递归放置。

总结

两道题都利用回溯算法解决n皇后问题。第一题逻辑清晰，逐行检查，但对角线检查较为繁琐。第二题通过一维数组记录列位置，减少了行冲突检查，增强了效率，适合稍大规模的问题。两者各有优劣，可根据需求选择使用。