当前位置: 首页 > 图文教程 > 开发语言 > VC++ > N皇后问题摆法算法描述

VC++
在类VC的界面实现中加入目录树
软件换肤技术在 BCB 中的实现
利用非模窗口生成MDI介面
报表输出轻松搞定
Windows 中不规则窗体的编程实现
解说Win32的窗口子类化
使用测试优先方法开发用户界面
一个简单的登录对话框的实现
一个简单的日记本程序
从资源中加载皮肤
一个在RichEdit中添加表情图象的类
ActiveSkin 4.3 软件换肤在VC中的实现
一种另类“关于(About)”对话框的动态显示方法
对话框打印预览及打印
关于如何换肤、子类化的解决方案
制作 MSN、QQ 的消息提示窗口
如何对 BCGControlBarPro 进行换肤
定制个性化的对话框窗口类
改变窗口中的光标形状
更新MFC中的视图，跟踪.NET Framework中的事件

No. « 20 21 22 23 »

技术文章搜索

关键字

VC++ 中的 N皇后问题摆法算法描述

出处:互联网   整理: 软晨网（RuanChen.com）   发布: 2009-10-30   浏览: 48 ::
收藏到网摘: n/a

N皇后问题摆法算法描述

作者：赵宏伟

代码下载

题目说明：
在一个Ｎ×Ｎ的国际象棋棋盘中摆Ｎ个皇后，使这Ｎ个皇后不能互相被对方吃掉。

题目要求：
（１）依次输出各种成功的放置方法。
（２）最好能画出棋盘的图形形式，并动态的演示试探过程。
（３）程序能方便的移植到其它规格的棋盘上。
例如：在一个４×４的棋盘可以摆放的棋位置｛（０，１）（１，３）（２，０）（３，２）｝，｛（０，２）（１，０）（２，３）（３，１）｝两种。

题目分析：
一、试探过程分析：
Ｎ×Ｎ皇后问题的求解过程就是一个试探回逆的过程。如图－１

　　
（图１－１） 

１、首先查找第一行的可放位置，第一行全部可以放，那么我们就先将第一个皇后放在（０，０）点。

 
（图１－２）

２、再查找第二行，由于第一行的（０，０）已经放了皇后，故第二行的（１，０）和（１，１）都能放皇后了，可放的就是（１，２）和（１，３）点，在（１，２）放上皇后。
　
（图１－３）

３、再查找第三行，查找所以发现第三行没有可放的位置了，回逆到第二行讲皇后放到（１，３）再查找第３行。如果还不行，就回到第一行将第一行的皇后放人下一个可放的点，依次类推，查找Ｎ×Ｎ上的所以可放的位置，直到第一行所以位置被放完，输出结果。
４、根据上面的规律可以发现，对于一个皇后放在坐标（ｘ，ｙ），它的下一行位置为（ｘ－１，ｙ）（ｘ，ｙ）（ｘ＋１，ｙ）的坐标都不能再放皇后。我们用一个数组来存放本行能放皇后的点。用循环来查找上面行对本行的影响，将收到影响的点置ＦＡｌＳＥ。
５、计算公式为：
iPlaceOver[col - (column - i)] = false; iPlaceOver[col] = false;iPlaceOver[col + (column - i)] = false;

其中ｃｏｌ是上面行皇后的位置，ｃｏｌｕｍｎ是当前的第Ｎ行。
６、跌代过程： 

for (i = 0 ; i < m_iCount ; i ++){	if (iPlaceOver[i])　//如果是可以放皇后的位置	{	m_piSaveQPlace[column] = i;//保存位置	ComputQueenPlace(column + 1);//递归搜索下一行	} }
７、为了动态保存计算结果，程序使用了一个整形的数组指针存放每次结果中每行的位置。为了方便和清晰的显示，我使用了一个结构保存。
８、增加了一个位图保存函数，用来保存希望保存为位图的结果。

二、程序动态显示试探结果说明：
　　为了显示试探过程，把视图指针传为递归函数，用来在得到真确的结果的时候可以刷新视图显示结果。在显示的时候为了防止过分闪动，使用了内存ＤＣ将位图直接帖到视图中。

三、类结构规划：
class CQueen{private:	struct PlaceList {	int	*Place; };	PlaceList * m_pPlaceList; int	m_iListMaxSize;	int	m_iListNowSize;	int	m_iCount;	CSize	m_sizeView;	bool	m_bRuning;	int	*m_piSaveQPlace; // 存每行中皇后的位置	int	m_iNowCol;	CBitmap *m_pGridBitmap;	int	m_iDrawIndex;public:	void DrawQueenN(CDC *pDC);	void DrawList(int index);	void ComputQueenPlace(int column , CView *view = NULL); // 皇后问题求解函数	CSize GetQueenGridSize();	int GetQueenPlace(int row);	int GetListSize();	int GetDrawIndex();	void SetRow(int row);	void SaveToBMPFile();	CQueen(int row);	CQueen();	~CQueen();private:	void DrawGird(CDC *pDC);	void DrawQueen(CDC *pDC);	void AddPlace(int *place);	void FreeList();};
代码分析：
１、递归代码
void CQueen::ComputQueenPlace(int column , CView *view) {	int row = 0;	int i ;	int col ;	m_iNowCol = column;	if (column == m_iCount) // 相等说明全部递归完成	{	AddPlace(m_piSaveQPlace);	m_bRuning = false;	return;	}	m_bRuning = true;	int *iPlaceOver = new int[m_iCount];	for ( i = 0 ; i < m_iCount ; i ++)// 初始化为都能放棋子	{	iPlaceOver[i] = true;	}// 将不能放棋子的点置False	for (i = 0 ; i < column ; i ++)	{	col = m_piSaveQPlace[i];	if ((col - (column - i)) >= 0)	{	iPlaceOver[col -