N皇后问题摆法算法描述

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

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 - (column - i)] = false;  

		}

		

		if ((col   (column - i)) < m_iCount)  

		{

			iPlaceOver[col   (column - i)] = false;  

		}

		iPlaceOver[col] = false;

  	}



// 递归调用每一次的可能  

	for (i = 0 ; i < m_iCount ; i   )  

	{

		if (iPlaceOver[i])  

		{

			m_piSaveQPlace[column] = i;  

			if (view != NULL && m_iDrawIndex == -1)  

			{

				CDC *pDC = view->GetDC();  

				DrawQueenN(pDC);

				view->ReleaseDC(pDC);

				Sleep(20);

			}

			ComputQueenPlace(column   1 , view);  

		}

	}

	m_bRuning = false;  

	delete[] iPlaceOver;  

	m_iNowCol = 0;  

}

２、保存找到的点代码

void CQueen::AddPlace(int *place)

  {

	if (m_iListNowSize == m_iListMaxSize)   

	{

		m_iListMaxSize  = 10;   

		PlaceList *temlist = new PlaceList[m_iListMaxSize];   

		for ( int i = 0 ; i < m_iListNowSize; i   )   

		{

			temlist[i].Place = m_pPlaceList[i].Place;   

		}

		delete[] m_pPlaceList;   

		m_pPlaceList = temlist;

   	}

	int *iPlace = new int[m_iCount];

   

	for ( int i = 0 ; i < m_iCount ; i   )   

	{

		iPlace[i] = place[i];   

	}

	m_pPlaceList[m_iListNowSize  ].Place = iPlace;   

}

用户使用：

（图２－１）

程序运行结果：


（图３－１）

结束语
　　这段时间有些空，写点数据结构课程设计上面的题目。以后将陆续发点这方面的代码，供大家一起交流，如果代码中有什么不妥当或不构完美的地方，也请大家不吝赐教。
下载本文示例代码

输入您的搜索字词 提交搜索表单