分治法（n皇后问题）

### 使用分治法解决 N 皇后问题

对于 N 皇后问题，通常更常见的是采用回溯法来求解所有可行方案。然而，在某些特定场景下也可以尝试使用分治策略。需要注意的是，分治算法主要用于寻找单个最优解而非枚举全部可能性。

#### 分治法的核心思想

分治方法通过将大问题分解成若干个小规模子问题独立求解后再组合这些局部解形成全局解。具体到 N 皇后问题中：

- 将整个棋盘划分为多个区域
- 在每个区域内单独处理并放置一定数量的皇后
- 确保不同分区之间不存在相互攻击的情况
- 合并各部分的结果构成最终解答

但是由于皇后的特殊移动方式（横竖斜都可以走），很难严格意义上做到完全无交集地分割棋盘空间；因此实际应用时往往需要引入额外约束条件或辅助数据结构帮助验证合法性[^1]。

#### 实现细节

下面给出一种基于递归划分的思想框架用于指导编程实践:

#include <iostream>
using namespace std;

const int MAXN = 20;
bool col[MAXN], dpos[2 * MAXN], dneg[2 * MAXN];
vector<int> queens; // 存储每一行对应的列号

// 判断当前位置是否合法
bool isValid(int row, int column){
    return !col[column] && !dpos[row + column] && !dneg[row - column + MAXN];
}

void divideAndConquer(int startRow, int endRow, int n){
    if(startRow > endRow){ 
        // 当前行超过最后一行，则找到一组有效摆放方案
        cout << "Solution found:" ;
        for(auto q : queens)cout<<q<<" ";
        cout<<"\n";
        return;
    }
    
    for (int i=startRow;i<=endRow;++i){
        for (int j=1;j<=n;++j){
            if(isValid(i,j)){
                // 记录状态变化
                col[j]=true;dpos[i+j]=true;dneg[i-j+MAXN]=true;
                queens.push_back(j);
                
                // 继续向下一层探索
                divideAndConquer(i+1,endRow,n);

                // 清除标记恢复现场以便测试其他路径
                col[j]=false;dpos[i+j]=false;dneg[i-j+MAXN]=false;
                queens.pop_back();
            }
        }
    }
}

此代码片段展示了如何利用分而治之的原则逐步构建满足要求的状态序列。不过值得注意的是这段程序本质上还是采用了类似于深度优先搜索的方式来进行穷尽性查找，并不是传统意义上的纯粹分治模式[^3]。