回溯算法n皇后问题c_n皇后问题贪心算法

2024年 6月 29日下午6:04 • 激活谷笔记

“发光并非太阳的专利，你也可以发光。”
你好，我是梦阳辰！期待与你相遇！

【问题描述】1．设计算法求解N皇后问题，要求给出测试用例，并给出你的程序运行该测试案例之后得到的结果。
N皇后问题研究的是如何将 N个皇后放置在 N×N 的棋盘上，并且使皇后彼此之间不能相互攻击。

(1) 给定一个整数N，返回所有不同的N皇后问题的解决方案。

(2) 如果只让求解N皇后问题不同解法的数目，又该如何设计算法。

（1）算法的描述：
1.定义解空间：
n皇后问题要求每一个皇后在不同行、不同列、不同斜线，因此我们可以使用不同行、不同列作为显约束，隐约束选择不同斜线。这样选择可以将解空间大大缩小。从根到叶子的路径就是一个解空间树。

（2）搜索解空间
1.约束条件：在第i行第j列放置第i个皇后时不能 `前i-1个皇后在同一斜线。根据行列与斜线的映射关系可知，该位置所在斜线的标号，若标记数组中该位置为false表示此斜线还可以放置皇后，否则该位置不能放。

2．限界条件：该问题不存在放置方案好坏的问题，所以不需要设置限界条件。

3．搜索过程：搜索过程从根开始，以深度优先方式进行搜索，根结点是活结点，并且是当前的扩展结点。在搜索过程中，当前的扩展结点沿纵深方向移向一个新结点，判断该新结点是否满足隐约束。如果满足，则新结点成为活结点，继续深一层的搜索；如果不满足，则换到该新结点的兄弟结点继续搜索；如果新结点没有兄弟结点。或者其他兄弟结点已经全部搜索完毕，则扩展结点成为死结点，搜索回溯到其父结点处继续进行。搜索过程直到找到问题的根结点变为死结点为止。

#include<iostream> #include<vector> #include<algorithm> using namespace std; vector<unsigned>nd; int n, num; bool p;//选择是否输出所有排列方式 vector<bool>l_r, r_l;//标记列，从左到右的斜线，和从右到左的斜线是否已经访问过 //不能放置物品为false 否则为true inline void init() { 
    nd.resize(n); l_r.assign(2 * n - 1, true); r_l.assign(2 * n - 1, true); for (int i = 0; i < n; i++)nd[i] = i; num = 0; } inline void mapping(int cur, int& _l_r, int &_r_l) { 
    _l_r = cur + nd[cur]; _r_l = (n - 1 - cur) + nd[cur]; } inline bool judge(int cur)//判断当前位置能否放置皇后 { 
    int lr, rl; mapping(cur, lr, rl); return l_r[lr] && r_l[rl]; } void dfs(int cur,int k)//排列树优化 { 
    int i, lr, rl; if (cur == n)//找到一种放置方法 { 
    num++; if (p) { 
    cout << "---------------------------------------------------" << endl; cout << "第" << num << "个满足要求的皇后位置：" << endl; i = 0; for (auto it : nd)//打印符合要求的位置 { 
    cout << "(" << i++ << "," << it << ") "; } cout << "\n--------------------------------------------------" << endl; cout << "---------------------------------------------------" << endl; cout << "第" << num+1 << "个满足要求的皇后位置：" << endl; i = 0; for (auto it : nd)//打印符合要求的位置 { 
    cout << "(" << i++ << "," << n-1-it << ") "; } cout << "\n--------------------------------------------------" << endl; } num++; } else { 
    for (i = cur; i <k; i++) { 
    swap(nd[cur], nd[i]);//依次和后面的第cur-k个素交换位置 if (judge(cur))//判断隐约束是否满足要求 { 
    mapping(cur, lr, rl);//得到映射关系 //标记 l_r[lr] = false; r_l[rl] = false; if (cur == 0 && n % 2 != 0 && nd[cur] == n / 2) { 
    dfs(cur + 1, (n + 1) / 2); } else dfs(cur + 1, n); //回退 l_r[lr] = true; r_l[rl] = true; } swap(nd[cur], nd[i]); } } } int main() { 
    //freopen("debug.txt", "r", stdin); int N; cout << "请输入测试数据个数:"; cin >> N; while (N--) { 
    cout << "请输入皇后的个数："; cin >> n; cout << "请选择是否要输出所有排列（’1‘ or ‘0’,‘1’表示输出，‘0’表示不输出）：" << endl; cin >> p; init(); dfs(0,(n+1)/2); cout << "共有" << num<< "种方案" << endl; } return 0; }

测试用例及运行结果：
皇后的个数：2 5
方案个数：0 10

“别人能做到的事，我一定也能做到”

关注公众号【轻松玩编程】回复关键字“电子书”，“计算机资源”，“Java从入门到进阶”，”JavaScript教程“，“算法”，“Python学习资源”，“人工智能”等即可获取学习资源

回溯算法n皇后问题c_n皇后问题贪心算法

相关推荐