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

VC++
用 auto_ptr 类模板帮助动态内存管理
走近 STL
一步一步学STL标准模板库
使用 <multimap> 库创建重复键关联容器
使用 <map> 库创建关联容器
用 vectors 改进内存的再分配
用函数模板实现和优化抽象操作
STL 字符串类与 UNICODE 及其它......
如何在Dll中导出STL类
再谈“在STL列表（Lists）中插入不同类型的对象”
使用::std::vector<>作为管理动态数组的优先选择
三种常见中文内码的转换方法
JNI 中文处理问题小结
构建 GB2312 汉字库的 unicode 码表
正则表达式简介
在非MFC程序中引用CString
UTF-8与GB2312之间的互换
宽字符标量L"xx"在VC6.0/7.0和GNU g++中的不同实现
用VC++设计语法编辑器
C语言中对时间和日期的处理

No. « 8 9 10 11 »

技术文章搜索

关键字

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

出处:互联网   整理: 软晨网（RuanChen.com）   发布: 2009-10-30   浏览: 58 ::
收藏到网摘: 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 -