分类:
2008-10-13 16:55:48
N皇后问题摆法算法描述
作者:
iPlaceOver[col - (column - i)] = false; iPlaceOver[col] = false; iPlaceOver[col + (column - i)] = false;
其中col是上面行皇后的位置,column是当前的第N行。
6、跌代过程:
for (i = 0 ; i < m_iCount ; i ++) { if (iPlaceOver[i]) //如果是可以放皇后的位置 { m_piSaveQPlace[column] = i;//保存位置 ComputQueenPlace(column + 1);//递归搜索下一行 } }7、为了动态保存计算结果,程序使用了一个整形的数组指针存放每次结果中每行的位置。为了方便和清晰的显示,我使用了一个结构保存。
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; }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; }