算法设计与分析——分支限界法——n皇后问题

秒速五厘米 2022-10-08 14:21 356阅读 0赞

**一、问题描述**

*问题描述：在n*n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n皇后问题等价于在n\*n的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。

*算法设计：设计一个解n皇后问题的队列式分支限界法，计算在n*n个方格上放置彼此不受攻击的n个皇后的一个放置方案。

\*数据输入：由文件input.txt给出输入数据。第一行有1个正整数n。

\*结果输出：将计算的彼此不受攻击的n个皇后的一个放置方案输出到文件output.txt。文件的第一行是n个皇后的放置方案。

输入文件：

input.txt

output.txt

1 3 5 2 4

**二、问题分析**  
1.题目分析：

对于每一个放置点而言，它需要考虑四个方向上是否已经存在皇后。分别是行列，45度斜线和135度斜线。

行：每一行只放一个皇后，直到我们把最后一个皇后放到最后一行的合适位置，则算法结束。

列：列相同的约束条件，只需判断j是否相等即可。

45度斜线和135度斜线：约束条件——当前棋子和已放置好的棋子不能存在行数差的绝对值等于列数差的绝对值的情况，若存在则说明两个棋子在同一条斜线上

2.算法选择：

用分支限界法来解决n皇后问题。对于该问题它满足两种树结构。这里由于每一个合适的放置点出现最优解的概率是相等的，因此不需要使用优先队列。编译器提供了一个已经封装好的队列queue。

A.子集树。我们把行约束条件和其它约束条件放在一起，即认为每一行，棋子都有n个位置可以放置。于是它的空间结构如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]  
假设n=3，这个图只画出了两层）

B.排列树。我们把行约束条件单独拿出来，也就是我们认为总共有八个皇后，这八个皇后必须都要放上去，但是放的位置不同，显然这是一个排列树。于是它的空间结构如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 1]  
这里由于我们还存在着其他的约束条件，并且行约束条件和这些条件完全可以放在一起，于是我就选择了相对容易理解的子集树作为解空间结构。

#include<iostream>
    #include<queue>
    #include<cmath>
    #include<vector>
    #include<fstream>
    #include<sstream>
    using namespace std;
     
    //定义一个节点类
    struct Node{
        
    	int number;
    	vector<int>x;//保存当前解 
    }; 
     
    //定义一个Queen的类 
    class Queen{
        
    	friend int nQueen(int);
    	public:
    		bool Place(Node q,int n);
    		void Research();
    		int n;//皇后个数
    		int *bestx;//最优解
    }; 
     
    //判断是否能够放置的函数 
    bool Queen::Place(Node q,int n)
    {
        
    	for(int j=1;j<n;j++)
    	  if((abs(n-j)==abs(q.x[j]-q.x[n]))||(q.x[j]==q.x[n])) return false;
    	return true;
    }
     
    void Queen::Research()
    {
        
    	queue<Node>Q;//活节点队列
    	Node sign;
    	sign.number=-1;
    	Q.push(sign);//同层节点尾部标志
    	int t=1;//当前节点所处的层
    	Node Ew;//当前扩展节点 
    	Ew.number=0; 
    	//搜索子集空间树
    	while(1){
        	
    	   //检查所有的孩子节点 
    	   for(int k=1;k<=n;k++){
        
    		//把当前扩展节点的值赋给下一个节点 
    		Node q;
    	        q.number=t; 
    	        q.x.push_back(0);//第一个位置为0 
        	        for(int i=1;i<t;i++) q.x.push_back(Ew.x[i]);
        	        q.x.push_back(k);
    		if(Place(q,t))
        	    	Q.push(q);
        	    }	 
    		//取下一扩展节点,取出，赋值给Ew 
    		Ew=Q.front();
    		Q.pop();
    		if(Ew.number==-1){
        
    		    //同层节点尾部标记
    		    t++;//进入下一层 
    		    Q.push(sign);//增加标记
    		    //继续往下去下一个节点 
    		    Ew=Q.front();
    		    Q.pop();
    		}		
    		if(Ew.number==n){
        //找到最后一层的节点 
    		   for(int i=0;i<=n;i++) bestx[i]=Ew.x[i];
    		   break;
    		} 
    	}
    }
     
    int nQueen(int n)
    {
        
    	Queen X;
    	X.n=n;	
    	X.bestx=new int[n+1];
    	for(int i=0;i<=n;i++) X.bestx[i]=0;
    	X.Research();
    	for(int i=1;i<=n;i++){
        
    		cout<<X.bestx[i]<<" ";
    	}
    }
     
    int main(){
        
    	int N;
    	cout<<"输入方格的行数："; 
    	cin>>N;	
    	cout<<"输出计算的彼此不受攻击的n个皇后的一个方案："; 
    	nQueen(N);
    	
    	
    	return 0;
    }

![在这里插入图片描述][20210621223838839.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]: /images/20221005/ac582d5f2f1c4dd0bdc1d57264225606.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 1]: /images/20221005/71a0061664344a1781010d9afa02784a.png
[20210621223838839.png]: /images/20221005/bf255efa30c14b2189a99927a7d849b7.png