分类: C/C++
2011-09-10 13:13:36
N皇后问题摆法算法描述 在一个N×N的国际象棋棋盘中摆N个皇后,使这N个皇后不能互相被对方吃掉。 题目要求: (1)依次输出各种成功的放置方法。 (2)最好能画出棋盘的图形形式,并动态的演示试探过程。 (3)程序能方便的移植到其它规格的棋盘上。 例如:在一个4×4的棋盘可以摆放的棋位置{(0,1)(1,3)(2,0)(3,2)},{(0,2)(1,0)(2,3)(3,1)}两种。 题目分析: 一、试探过程分析: N×N皇后问题的求解过程就是一个试探回逆的过程。如图-1 (图1-1) 1、首先查找第一行的可放位置,第一行全部可以放,那么我们就先将第一个皇后放在(0,0)点。 (图1-2) 2、再查找第二行,由于第一行的(0,0)已经放了皇后,故第二行的(1,0)和(1,1)都能放皇后了,可放的就是(1,2)和(1,3)点,在(1,2)放上皇后。 (图1-3) 3、再查找第三行,查找所以发现第三行没有可放的位置了,回逆到第二行讲皇后放到(1,3)再查找第3行。如果还不行,就回到第一行将第一行的皇后放人下一个可放的点,依次类推,查找N×N上的所以可放的位置,直到第一行所以位置被放完,输出结果。 4、根据上面的规律可以发现,对于一个皇后放在坐标(x,y),它的下一行位置为(x-1,y)(x,y)(x+1,y)的坐标都不能再放皇后。我们用一个数组来存放本行能放皇后的点。用循环来查找上面行对本行的影响,将收到影响的点置FAlSE。 5、计算公式为:iPlaceOver[col - (column - i)] = false; iPlaceOver[col] = false; iPlaceOver[col + (column - i)] = false; 其中col是上面行皇后的位置,column是当前的第N行。 8、增加了一个位图保存函数,用来保存希望保存为位图的结果。 二、程序动态显示试探结果说明: 为了显示试探过程,把视图指针传为递归函数,用来在得到真确的结果的时候可以刷新视图显示结果。在显示的时候为了防止过分闪动,使用了内存DC将位图直接帖到视图中。 三、类结构规划: 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(); }; 代码分析: 1、递归代码 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; } 2、保存找到的点代码 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; } 用户使用: (图2-1) 程序运行结果: (图3-1) 结束语 这段时间有些空,写点数据结构课程设计上面的题目。以后将陆续发点这方面的代码,供大家一起交流,如果代码中有什么不妥当或不构完美的地方,也请大家不吝赐教。 |