算法设计与分析——回溯法——n皇后问题

灰太狼 2022-10-20 12:15 192阅读 0赞

一、什么是N皇后问题？

在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于再n×n的棋盘上放置n个皇后，任何2个皇后不妨在同一行或同一列或同一斜线上。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]  
问题解析：用n元数组x\[1:n\]表示n后问题的解。其中，x\[i\]表示皇后i放在棋盘的第i行的第x\[i\]列。由于不允许将2个皇后放在同一列上，所以解向量中的x\[i\]互不相同。如果将n\*n的棋盘看做是二维方阵，其行号从上到下，列号从左到右依次编号为1,2，……n。设两个皇后的坐标分别为(i,j)和(k,l)。若两个皇后在同一斜线上，那么这两个皇后的坐标连成的线为1或者-1。因此有：  
![在这里插入图片描述][20210619153110991.png]

由此约束条件剪去不满足行、列和斜线约束的子树。程序的递归回溯实现如下：

递归回溯

#include<iostream>
    using namespace std;
    class Queen{
        
    	public:
    		bool Place(int k);
    		void Backtrack(int t);
    		
    		int n;//皇后的个数 
    		int *x;//当前的解 
    		 
    		long sum;//当前已找到的可行方案数 
    		
    };
    
    bool Queen::Place(int k)//剪枝函数 
    {
        
    	for(int j=1;j<k;j++)
    	{
        
    		if((abs(k-j) == abs(x[k]-x[j]))||(x[k] == x[j]))//同一对角线上，同一列上的不符合条件 
    			return false;
    	}
    	return true;
     } 
    void Queen::Backtrack(int t)
    {
        
    	if(t>n)//如果到达了叶子结点，则说明这是一个解 
    	{
        
    		sum++;
    		for(int i=1;i<=n;i++)
    		{
        
    		cout<<x[i]; 
    		} 
    		cout<<endl;
    	}
    	else
    	{
        
    		for(int i=1;i<=n;i++)// 遍历这一行的每一个位置 
    		{
        
    			x[t]=i;//先假设，这一行进入的是第i个 
    			if(Place(t))//判断一下这个点是否满足n皇后问题的要求 
    				Backtrack(t+1);//如果满足了则进入下一步 
    		}
    	}
     } 
    int nQueen(int n)
    {
        
    	Queen X;
    	//初始化X;
    	X.n=n;
    	X.sum=0;
    	int *p = new int [n+1];
    	
    	for(int i=0;i<=n;i++)
    	{
        
    		p[i]=0;
    	 }
    	 X.x = p;
    	 X.Backtrack(1);
    	 delete[]p;
    	 return X.sum; 
     } 
     
    int main()
    {
        
    	int n;
    	cout<<"输入n皇后的问题中皇后的个数n:";
    	cin>>n; 
    
    	cout<<n<<"皇后的问题解共"<<endl;
    	cout<<nQueen(n)<<"个解"<<endl;
     }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 1]  
迭代回溯：

#include<iostream>
    using namespace std;
    class Queen{
        
    	public:
    		bool Place(int k);
    		void Backtrack(int t);
    		
    		int n;//皇后的个数 
    		int *x;//当前的解 ，也表示当前的列。因为列就是的顺序就是最终的解 
    		 
    		long sum;//当前已找到的可行方案数 
    		
    };
    
    bool Queen::Place(int k)//剪枝函数 
    {
        
    	for(int j=1;j<k;j++)
    	{
        
    		if((abs(k-j) == abs(x[k]-x[j]))||(x[k] == x[j]))//同一对角线上，同一列上的不符合条件 
    			return false;
    	}
    	return true;
     } 
    void Queen::Backtrack(int t)
    {
        //k表示当前的行，x[k]表示当前的列 
    	x[1]=0;//初始化第一行，0表示所有位置均没有放"后";
    	int k=1;//初始化第一行 
    	while(k>0)
    	{
        
    		x[k]+=1;//移动到下一列	
    		while((x[k]<=n)&&!(Place(k)))//在第k行找到一个可以放后的位置 
    		{
        
    			x[k]+=1;		
    		}
    		if(x[k]<=n)//如果找到可以放后的位置 
    		{
        
    			if(k == n)//如果当前行是最后一行，找到可行解 
    			{
        
    				sum++;
    			for(int i=1;i<=n;i++)
    			{
        
    				cout<<x[i];
    			}
    			cout<<endl;
    			}
    			else//如果当前解不是最后一行，找到可行解 
    		  {
        
    			k++;
    			x[k]=0;
    		  }
    		}
    		else
    			k--;//如果第k行没有找到可以放后的位置，此时行号减一
    			//返回到第k-1行 
    		
    	 } 
    	
     } 
    int nQueen(int n)
    {
        
    	Queen X;
    	//初始化X;
    	X.n=n;
    	X.sum=0;
    	int *p = new int [n+1];
    	
    	for(int i=0;i<=n;i++)
    	{
        
    		p[i]=0;
    	 }
    	 X.x = p;
    	 X.Backtrack(1);
    	 delete[]p;
    	 return X.sum; 
     } 
     
    int main()
    {
        
    	int n;
    	cout<<"输入n皇后的问题中皇后的个数n:";
    	cin>>n; 
    
    	cout<<n<<"皇后的问题解共"<<endl;
    	cout<<nQueen(n)<<"个解"<<endl;
     }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 2]

五、N皇后问题解的个数  
n solution(n)  
1 1  
2 0  
3 0  
4 2  
5 10  
6 4  
7 40  
8 92  
9 352  
10 724  
11 2680  
12 14200  
13 73712  
14 365596  
15 2279184  
16 14772512  
17 95815104  
18 666090624  
19 4968057848  
20 39029188884  
21 314666222712  
22 2691008701644  
23 24233937684440  
24 227514171973736  
25 2207893435808352

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]: /images/20221020/b0e05558d5f84a2fb7dd0b39dc810633.png
[20210619153110991.png]: /images/20221020/7808b31c4ede43e583455938350d2cb1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 1]: /images/20221020/e6d603d819dd42048ee630fb10221635.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 2]: /images/20221020/4cea45dfe56d4cc1ba6f9b0ef66b4a06.png