N皇后问题摆法算法描述

核心提示：二、程序动态显示试探结果说明：为了显示试探过程，把视图指针传为递归函数，N皇后问题摆法算法描述(2)，用来在得到真确的结果的时候可以刷新视图显示结果，在显示的时候为了防止过分闪动，供大家一起交流，如果代码中有什么不妥当或不构完美的地方，使用了内存ＤＣ将位图直接帖到视图中，三、类结构规划：class CQueen{pri

二、程序动态显示试探结果说明：

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

三、类结构规划：

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;　
}

用户使用：

（图２－１）

程序运行结果：

（图３－１）

结束语

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