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

n皇后问题解法与改进算法探讨

常规问题一：回溯法解法

回溯法思路

传统的n皇后问题可以通过回溯法解决。具体步骤如下：

回溯法代码实现

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;void Backtracking(int N, int i, set
       
         col, set
        
          diag45, set
         
           diag135, vector
          
            placeResult, int &ans) { int j = 1; while (i <= N && i > 0) { while (j <= N) { if (!col.count(j) && !diag45.count(i + j) && !diag135.count(i - j)) { placeResult[i] = j; col.insert(j); diag45.insert(i + j); diag135.insert(i - j); i++; j = 1; break; } j++; } if (j > N) { j = Erase(i, col, diag45, diag135, placeResult); } if (i == N + 1) { ans++; for (int row = 1; row <= N; row++) { for (int col = 1; col <= N; col++) { if (col == placeResult[row]) { printf("√"); } else if (col != N) { printf(" "); } else { printf("\n"); } } } printf("\n"); } }}void Erase(int &i, set
           
             col, set
            
              diag45, set
             
               diag135, vector
              
                placeResult) { i--; int k = placeResult[i]; placeResult[i] = 0; col.erase(k); diag45.erase(i + k); diag135.erase(i - k); return k + 1;}// 该函数将皇后随机放置在前stepVegas行，后面的皇后按传统回溯法解决bool QueenLV(int N, set
               
                 col, set
                
                  diag45, set
                 
                   diag135, vector
                  
                    placeResult, int stepVegas) { int i = 1; int LP = 0; �� Coronation:
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

常规问题二：全排列枚举法

全排列枚举思路

使用全排列算法，生成所有可能的皇后位置排列。只需验证对角线约束即可。

全排列枚举代码

#include 
   
    #include 
    
     using namespace std;void generateP(vector
     
       &P, vector
      
        &isLegal, int n, int &ans, int index) {    if (index == n + 1) {        ans++;        return;    }    for (int i = 1; i <= n; i++) {        if (!isLegal[i]) {            bool flag = true;            for (int pre = 1; pre < index; pre++) {                if (abs(index - pre) == abs(i - P[pre])) {                    flag = false;                    break;                }            }            if (flag) {                P[index] = i;                isLegal[i] = true;                generateP(P, isLegal, n, ans, index + 1);                isLegal[i] = false;            }        }    }}int main() {    int n = 8;    vector
       
         P(n + 1);    vector
        
          isLegal(n + 1); int ans = 0; generateP(P, isLegal, n, ans, 1); printf("有%d种放置可能\n", ans); return 0;}
        
       
      
     
    
   

另一类问题：Las Vegas思想优化

优化思路

前stepVegas行采用随机放置，剩余行用传统回溯法解决。

优化结果分析

实验表明，stepVegas取略小于N的值时效果较好，步长如下：N = 8时，stepVegas = 7N = 15时，stepVegas = 13

这种方法相比纯回溯方法平均所需时间较少。

运行示例

如N=8，stepVegas=7与stepVegas=8的对比结果表明，stepVegas=7的平均首次成功所需时间更短。

扩展阅读