回溯算法——八皇后问题-蒲公英云

回溯算法——八皇后问题

八皇后问题（链接）

努比亚和苏丹没有子女，所以他要从一些有集成资格的继承者中挑选一个出来继承王位。他希望这个继承者足够聪明，所以他准备了一个西洋棋盘，上面的每个格子中均有一个 1 − 99 1-99 1−99 的数字。他又准备了 8 8 8 个皇后棋子。

8 8 8 皇后的规则就是不能有任何棋子同行或者同列或者同斜线，在满足这个规则的同时，王位继承者还需要让 8 8 8 个皇后所在的位置的数字的和是最大的。

输入格式

输入一个数字 k ( k ≤ 20 ) k(k\leq 20) k(k≤20)，代表棋盘的数量。

接下来有 k k k 个棋盘，每个棋盘有 64 64 64 个数字，分成 8 8 8 行 8 8 8 列出入，具体可见样例，每一个数字均小于 100 100 100。
输出格式

每一个棋盘对应输出最大的数值，一共输出 k k k 行。

源码如下

#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<algorithm>
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
int const Max = 1e2 + 5;
int lst[Max][Max];
int const Inf = 1e8 + 5;
vector<int> vec;
int sum;
int cur[Max];//记录每一行皇后所在列
void dfs(int h)//第h行
{ 
    if (h == 9)//临界条件
    { 
        sum = 0;
        for (int i = 1; i <= 8; i++) sum += lst[i][cur[i]];
        vec.push_back(sum);  //把每次结果加入vec
        return;
    }
    for (int i = 1; i <= 8; i++)//把每一列尝试一遍
    { 
        int flag = 1;
        for (int j = 1; j < h; j++)
        { 
            if (i == cur[j] || i + h == cur[j] + j || h - i == j - cur[j])//检查是否和前面的皇后冲突
            { 
                flag = 0;
                break;
            }
        }
        cur[h] = i;//记录
        if (flag) dfs(h + 1);//符合条件则进入下一行
        cur[h] = 0;//抹除记录，这个问题里不写也可
    }
}
int main()
{ 
    int n;
    cin >> n;
    while (n--)
    { 
        vec.clear();
        for (int i = 1; i <= 8; i++)
        { 
            for (int j = 1; j <= 8; j++) cin >> lst[i][j];
        }
        dfs(1);
        sort(vec.begin(), vec.end(), greater<int>());//递减排序
        cout << vec[0] << endl;
    }
}