八皇后-经典搜索

不到30行代码解八皇后问题：
https://blog.csdn.net/csyifanZhang/article/details/105704431
↑更好的阅读体验

先来看一看洛谷的八皇后问题，

有了这个图就显得比较清晰了，就是在8*8或者6*6的棋盘上放置8或者6个棋子，使得棋子所在行列个不相交。建议直接学数独游戏，基本上搜索难不过八数码和数独毕竟我做的题少，没遇到过 。这道题打眼一看就要来搜索，那么我们就要确定搜索的状态是什么？如何进行搜索？

如果我们使用dfs进行搜索，那么首先要保证的是条件：==每行每列每条对角线都没有连个皇后==，行和列还比较好处理，一旦给某个位置加上一个皇后，那么我们标记该行该列即可，比较麻烦的就是对角线的记录：

对角线的元素有如下的性质：

• 对于一条从右上到左下的对角线，其上的棋子坐标应满足x+y为一定值；（比如1,6，6,1）
• 对于一条从左上到右下的对角线，其上的棋子坐标应满足x-y为一定值，为了避免负数的产生，代码中用x-y+n来储存数字，(比如1,1，6,6)
• 而且上述两种方案在每条对角线上得到的值各不相同，因此可以用于标识对角线是否存在元素。

下面这一段搜索足够解决的n皇后问题，如果，则使用vector存储历史路径即可当然也有其他解决方案。

void dfs(ll x, string s) {//对第x行进行搜索
    if (x == n + 1) { res++; v.push_back(s); return; }//成功凑成n皇后
    for (int i = 1; i <= n; i++) {//尝试第一行的每个位置
        if (!row[x] && !col[i] && !eye1[x + n - i] && !eye2[x + i]) {
            row[x] = col[i] = eye1[x + n - i] = eye2[x + i] = 1; 
            s += i + '0';
            dfs(x + 1, s);//x行有了皇后 继续到下一行
            s.erase(s.end()-1);
            row[x] = col[i] = eye1[x + n - i] = eye2[x + i] = 0;//回溯
        }
    }
}

到这里这道题已经非常容易了，只需要指定n=8，然后输入b，直接输出v[b-1]即可。

//a:棋盘当前的状态  row[i]:第i行有元素  col[i]:第j列有元素
//eye1：主对角线(x+n-y定值)  eye2：次对角线(x+y定值)
ll row[MAX], col[MAX], eye1[MAX * 3], eye2[MAX * 3], n = 8, res = 0, b;
vector<string> v;

void dfs(ll x, string s) {//对第x行进行搜索
    if (x == n + 1) { res++; v.push_back(s); return; }//成功凑成n皇后
    for (int i = 1; i <= n; i++) {//尝试第一行的每个位置
        if (!row[x] && !col[i] && !eye1[x + n - i] && !eye2[x + i]) {
            row[x] = col[i] = eye1[x + n - i] = eye2[x + i] = 1; 
            s += i + '0';
            dfs(x + 1, s);//x行有了皇后 继续到下一行
            s.erase(s.end()-1);
            row[x] = col[i] = eye1[x + n - i] = eye2[x + i] = 0;//回溯
        }
    }
}

int main(){
    while (cin >> b) {
        res = 0; string s; v.clear();
        dfs(1, s);
        sort(v.begin(), v.end());
        cout << v[b - 1] << endl;
    }
}