n皇后问题MFC人机界面程序流程图.ppt

小组成员： 陈华鑫、黄燕舞、刘建福、 王志兴、贾卓、商贵宝、 郭云梅、林岩 八皇后问题是一个古老而著名的问题，它是回溯算法的典型例题。该问题是十九世纪德国著名数学家高斯于1850年提出的：在8行8列的国际象棋棋盘上摆放着八个皇后。使他们之间不能互相攻击。若两个皇后位于同一行、同一列或同一对角线上，则它们之间就可以互相攻击。后来人们从8皇后问题延伸到了n皇后问题 一、在一个n * n的棋盘中放置最多的皇后，使这些皇后互相之间无法攻击对方。 二、求出在n*n的棋盘中总共有多少种符合要求放置皇后的方法。 问题求解与博弈 由于每行、每列最多只能放置一个皇后，所以，在n * n的棋盘上最多只能放置n个皇后。 由于每行只能放置一个皇后，我们不妨从第一列开始放置皇后，从第二列开始依次判断所要放置皇后之前所在的行、列、对角线上是否存在皇后。 我们选择使用回溯法即经典的递归法来求解n皇后问题，这个算法将在棋盘上一列一列地摆放皇后直到n个皇后在不相互攻击的情况下都被摆放在棋盘上，算法便终止。当一个新加入的皇后因为与已经存在的皇后之间相互攻击而不能被摆在棋盘上时，算法便发生回溯。一旦发生这种情况，就试图把最后放在棋盘上的皇后移动到其他地方。这样做是为了让新加入的皇后能够在不与其它皇后相互攻击的情况下被摆放在棋盘的适当位置上。 例如图中所示的情况，尽管第7个皇后不会与已经放在棋盘上的任何一皇后放生攻击，但仍然需要将它移除并发生回溯，因为无法为第8个皇后在棋盘上找到合适的位置。 算法的回溯部分将尝试移动第7个皇后到第7列的另外一个位置来为第8个皇后在第8列寻找一个合适的位置。如果第7个皇后由于在第7列找不到合适的位置而无法被移动，那么算法就必须去掉它然后回溯到第6列的皇后。最终算法不断重复着摆放皇后和回溯的过程直到找到问题的解为止。 总体流程图 类及其实现 在本程序中主要的是两个类即CEightQueenDlg 和 QueenPanel 。在下面表格中给出了这两个类的相关成员变量和函数。表一是CEightQueenDlg类的相关成员变量和函数 表一 表二为QueenPanel成员函数及变量 表二 * 初始化数据 取n值 执行DrwaBoard(CDC *PDC,int Size,int cell) 设置画板大小 SetQueen(int *new q)来设置皇后的位置 OnPaint( )打印皇后 结束 开始 private pubilc void UpdateQPanel(int *queen); void WINAPI Go(); void WINAPI Step(int i); void DoPause(); virtual void OnCancel(); void UpdateQPanel(int row, int col); virtual void OnOK(); static DWORD WINAPI ThreadGo( LPVOID lpParam ) ; void UpdateUI(); int count; int n; BOOLEAN step, no_int; BOOLEAN *mk; BOOLEAN *lk; BOOLEAN *rk; int *queen; BOOLEAN m_step, m_no_int; private void SetQueen(int row, int col)； void SetQueen(int *newq); void SetSize(int size); int n; virtual ~QueenPanel(); int *queen; QueenPanel(int size); void DrawBoard(CDC *pDC, int size, int cell); QueenPanel(); private public *