n后问题(回溯法)

末蓝、 2022-08-18 02:13 193阅读 0赞

一.问题描述:

在n\*n格子上放置n个皇后, 按照国际象棋规矩不可让皇后相互攻击, 即如何两个皇后不放在同一列同一行同一斜线上.

二.算法设计:

将问题转化为逐行放置皇后,即第一次放第1行,第二次放第2行,依次类推放至第n行皇后则放置完毕,如此每次放置只需考虑皇后的列冲突和斜线冲突.因为每次皇后都在新的一行放置.假设数组 x\[i\] 表示第i个皇后放的列数,如x\[3\] = 4; 表示第3个(第三行的)皇后放在第4列.

设第i行皇后放x\[i\]列,和第k行皇后放x\[k\]列,其中冲突情况有:

1.  列冲突, 即x\[k\] = x\[i\] 
2.  斜线冲突,由于在n\*n格子,则若有两个棋子属于同一斜线,则两棋子斜率为-1,可推出 | x\[i\]-x\[k\] | /| (i-k) |=1; 则 |i-k|= | (x\[i\]-x\[k\]) |

因此在此可以先定义检验函数bool Place(int k),该函数检验第k行皇后与之前的所有皇后有没有冲突,

函数代码如下:

bool Queen::Place(int k)
    {
    	for(int j=1;j<k;j++)
    		if(  ( abs(k-j)==abs(x[j]-x[k]) ) ||(x[j]==x[k])  )//斜线冲突和列冲突
    			return false;			//返回false
    	return true;	//注意这里不是else执行返回true,当k与之前所有皇后冲突检测通过后</span>才返回true
    }

三.解空间:

n后问题的解可以用一颗解空间树表示,其中从根节点开始对树进行深度优先搜索,

![Image 1][]

从第一个根节点开始搜索,如果找到第n+1层,则所有n后放置完毕,解决方案sum++;

四.源程序代码:

#include<iostream>
    #include<cmath>
    using namespace std;
    class Queen
    {
    	friend int nQueen(int);
    private:
    	bool Place(int k);
    	void Backtrack(int t);
    	int n,*x;
    	long sum;
    };
    
    bool Queen::Place(int k)
    {
    	for(int j=1;j<k;j++)
    		if(  ( abs(k-j)==abs(x[j]-x[k]) ) ||(x[j]==x[k])  )
    			return false;
    	return true;	//注意这里不是else执行返回true,当每一行都测试过没有冲突之后才返回true
    }
    
    void Queen::Backtrack(int t)
    {
    	if(t>n) sum++;
    	else
    		for(int i=1;i<=n;i++)
    		{
    			x[t]=i;
    			if(Place(t))Backtrack(t+1);
    		}
    }
    
    int nQueen(int n)
    {
    	Queen 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,s;//皇后个数,解决方案;
    	int t=4;
    	while(t--)
    	{
    		cout<<"请输入皇后个数:"<<endl;
    		cin>>n;
    		s=nQueen(n);
    		cout<<n<<"皇后问题解决方案个数为:"<<s<<endl;
    	}
    }

五.结果示例:

![20151205190104120][]

由于递归回溯法时间复杂度高,超过12的皇后个数请慎用.如果基数过大,回溯法的优势就不明显了.

所以关于该算法的改进还有另一种拉斯维加斯(Las Vegas)算法,结合了随机函数,提高了效率,今天先到这里,明天接着写.

参考资料:《计算机算法设计与分析》 (第四版) 电子工业出版社

[Image 1]: 
[20151205190104120]: /images/20220731/f46acb81988747b8b115dfbb90250076.png