N皇后问题摆法算法描述 wxh zt

wxhwhmanshan

题目说明：
在一个Ｎ×Ｎ的国际象棋棋盘中摆Ｎ个皇后，使这Ｎ个皇后不能互相被对方吃掉。

题目要求：
（１）依次输出各种成功的放置方法。
（２）最好能画出棋盘的图形形式，并动态的演示试探过程。
（３）程序能方便的移植到其它规格的棋盘上。
例如：在一个４×４的棋盘可以摆放的棋位置｛（０，１）（１，３）（２，０）（３，２）｝，｛（０，２）（１，０）（２，３）（３，１）｝两种。

题目分析：
一、试探过程分析：
Ｎ×Ｎ皇后问题的求解过程就是一个试探回逆的过程。


１、首先查找第一行的可放位置，第一行全部可以放，那么我们就先将第一个皇后放在（０，０）点。


２、再查找第二行，由于第一行的（０，０）已经放了皇后，故第二行的（１，０）和（１，１）都能放皇后了，可放的就是（１，２）和（１，３）点，在（１，２）放上皇后。

３、再查找第三行，查找所以发现第三行没有可放的位置了，回逆到第二行讲皇后放到（１，３）再查找第３行。如果还不行，就回到第一行将第一行的皇后放人下一个可放的点，依次类推，查找Ｎ×Ｎ上的所以可放的位置，直到第一行所以位置被放完，输出结果。
４、根据上面的规律可以发现，对于一个皇后放在坐标（ｘ，ｙ），它的下一行位置为（ｘ－１，ｙ）（ｘ，ｙ）（ｘ＋１，ｙ）的坐标都不能再放皇后。我们用一个数组来存放本行能放皇后的点。用循环来查找上面行对本行的影响，将收到影响的点置ＦＡｌＳＥ。
５、计算公式为：
iPlaceOver[col - (column - i)] = false;
iPlaceOver[col] = false;
iPlaceOver[col + (column - i)] = false;
其中ｃｏｌ是上面行皇后的位置，ｃｏｌｕｍｎ是当前的第Ｎ行。
６、跌代过程：


for (i = 0 ; i < m_iCount ; i ++)
{       
        if (iPlaceOver)　//如果是可以放皇后的位置
        {
                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 = true;  
        }

// 将不能放棋子的点置False  
        for (i = 0 ; i < column ; i ++)  
        {
                col = m_piSaveQPlace;  
                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)  
                {
                        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.Place = m_pPlaceList.Place;   
                }
                delete[] m_pPlaceList;   
                m_pPlaceList = temlist;
           }
        int *iPlace = new int[m_iCount];
   
        for ( int i = 0 ; i < m_iCount ; i ++)   
        {
                iPlace = place;   
        }
        m_pPlaceList[m_iListNowSize++].Place = iPlace;   
}

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