（回溯算法）求解N皇后问题

绝地灬酷狼 2023-02-19 01:26 20阅读 0赞

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

**【问题描述】1．设计算法求解N皇后问题，要求给出测试用例，并给出你的程序运行该测试案例之后得到的结果。  
N皇后问题研究的是如何将 N个皇后放置在 N×N 的棋盘上，并且使皇后彼此之间不能相互攻击。**  
![在这里插入图片描述][20200618193947150.png]  
(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  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYWh1YW5f_size_16_color_FFFFFF_t_70_pic_center]

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYWh1YW5f_size_16_color_FFFFFF_t_70_pic_center 1]

[20200618193947150.png]: https://img-blog.csdnimg.cn/20200618193947150.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYWh1YW5f_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200618194338214.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYWh1YW5f,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYWh1YW5f_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/2020061819510411.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYWh1YW5f,size_16,color_FFFFFF,t_70#pic_center