n皇后问题MFC人机界面课程设计

1、福建工程学院课程设计课程：VC+面向对象程序设计题目皇后问题专业：电子科学与技术班级：0902座号：202012年3月15日、实践目的与要求：要求在一个nXn的棋盘上放置n个皇后，要求放置的n个皇后不会互相吃掉对方；皇后棋子可以吃掉任何它所在的那一行、那一列，以及那两条对角线上的任何棋子。熟悉visualC+编程环境二、实践工具与准备在开始实验前，应回顾或复习相关内容。需要一台计算机，其中安装有VisualC+6.0集成开发环境软件。课题分析三、课题分析八皇后问题是一个古老而著名的问题，它是回溯算法的典型例题。该问题是十九世纪德国著名数学家高斯于1850年提出的：在8行8列的国际象棋棋盘上摆放

2、着八个皇后。使他们之间不能互相攻击。若两个皇后位于同一行、同一列或同一对角线上，则它们之间就可以互相攻击。后来人们从8皇后问题延伸到了n皇后问题，问题的重点即使每两个皇后都不能在同一行、同一列、同一对角线上。在分析这个问题时，我们不妨从第一列开始放置皇后。这里我们选择使用回溯法即经典的递归法来求解n皇后问题，这个算法将在棋盘上一列一列地放置皇后直到n个皇后在不相互攻击的情况下都被摆放在棋盘上，算法便终止。当一个新加入的皇后因为与已经存在的皇后之间相互攻击而不能被摆在棋盘上时，算法便发生回溯。一旦发生这种情况，就试图把最后放在棋盘上的皇后移动到其他地方。这样做是为了让新加入的皇后能够在不与其它皇

3、后相互攻击的情况下被摆放在棋盘的适当位置上。如图所示是两种满足要求摆放皇后的图。會四、设计流程打开visualC+新建一个MFCAPPwizrd(exe)工程，由于该n皇后问题是由8皇后问题衍变而来的，我们为了纪念高斯这位伟大的数学家，我们把工程命名为EightQueen。按如图为窗体放置相应的组件，将窗体的名称改成“皇后问题”并按以下表格设置好相关的ID和属性标题ID属性分组框开始IDCSTART暂停/单步IDCPAUSEn值IDCBOARDSIZE单步IDCSTEPBY不中断IDCNOINT继续IDCCONTINUE停止IDCSTOPQueenpanelIDCQUEENPANEL关于IDC

4、ABOUT按Ctrl+W为IDC_QUEEN_PANEL添加一个Type为QueenPanel的成员变量m_panel为组件画板新建一个名为QueenPanel的类，并添加以下成员:publicprivateQueenPanel。；voidDrawBoard(CDC*pDC,intsize,intcell);QueenPanel(intsize);int*queen;virtualQueenPanel。；intn;voidSetSize(intsize);HANDLEqueenmutex;voidSetQueen(int*newq);voidSetQueen(introw,intcol)为CE

5、ightQueenDlg类添加以下变量及函数pubilcprivatevoidUpdateUI();staticDWORDWINAPIThreadGo(LPVOIDlpParam);voidWINAPIGo();voidUpdateQPanel(int*queen);virtualvoidOnOK();voidUpdateQPanel(introw,intcol);virtualvoidOnCancel();voidDoPause();voidWINAPIStep(inti);BOOLEANmstep,mnoint;intcount;intn;int*queen;BOOLEAN*rk;BOOL

6、EAN*lk;BOOLEAN*mk;BOOLEANstep,noint;HANDLEpauseevent,thismutex;BOOLEANcanceling,running,pausing;五、程序代码：为单步单选框控件添加BN_CLICKED消息映射，代码如下：CButton*step=(CButton*)GetDlgItem(IDC_STEP_BY);m_step=(step-GetCheck()=BST_CHECKED)?TRUE:FALSE;if(m_step)CButton*autoBtn=(CButton*)GetDlgItem(IDC_NO_INT);autoBtn-SetCh

7、eck(FALSE);m_no_int=FALSE;为不中断单选框控件添加BN_CLICKED消息映射，代码如下CButton*autoBtn=(CButton*)GetDlgItem(IDC_NO_INT);m_no_int=(autoBtn-GetCheck()=BST_CHECKED)?TRUE:FALSE;if(m_no_int)CButton*step=(CButton*)GetDlgItem(IDC_STEP_BY);step-SetCheck(FALSE);m_step=FALSE;为开始按钮控件添加BN_CLICKED消息映射，代码如下：DWORDdwThreadId;HAND

8、LEhThread;CStringstr;GetDlgItem(IDC_BOARD_SIZE)-GetWindowText(str);intnewn=atoi(str);if(newnGo();return0;为暂停/单步按钮控件添加BN_CLICKED消息映射，代码如下：WaitForSingleObject(this_mutex,INFINITE);step=TRUE;if(pausing)SetEvent(pause_event);ReleaseMutex(this_mutex);UpdateUI();为继续按钮控件添加BN_CLICKED消息映射，代码如下WaitForSingleOb

9、ject(this_mutex,INFINITE);step=FALSE;if(pausing)SetEvent(pause_event);ReleaseMutex(this_mutex);UpdateUI();为停止按钮控件添加BN_CLICKED消息映射，代码如下WaitForSingleObject(this_mutex,INFINITE);step=FALSE;canceling=TRUE;if(pausing)SetEvent(pause_event);ReleaseMutex(this_mutex);UpdateUI();为QueenPanel.cpp添加如下代码QueenPane

10、l:QueenPanel()this-queen=NULL;n=0;queen_mutex=CreateMutex(NULL,FALSE,NULL);QueenPanel:QueenPanel(intsize)this-queen=NULL;n=0;SetSize(size);queen_mutex=CreateMutex(NULL,FALSE,NULL);QueenPanel:QueenPanel()析构函数，释放空间if(queen!=NULL)free(queen);BEGIN_MESSAGE_MAP(QueenPanel,CWnd)/AFX_MSG_MAP(QueenPanel)ON_

11、WM_PAINT()/AFX_MSG_MAPEND_MESSAGE_MAP()QueenPanelmessagehandlersvoidQueenPanel:OnPaint()CPaintDCdc(this);/devicecontextforpaintingif(n=0|queen=NULL)return;RECTrect;GetWindowRect(&rect);CDCMemDC;/定义一个显示设备对象CBitmapMemBitmap;/定义一个位图对象WaitForSingleObject(queen_mutex,INFINITE);intw=rect.right-rect.left;i

12、nth=rect.bottom-rect.top;intboard=w=h?h:w;board=board-board%n;intcell=board/n;/System.out.println(w:+w+h:+h+x:+x+y:+y+cell:+/cell+board:+board+rl:+rl);intcount=0;inti;CPenb_pen(PS_SOLID,1,RGB(0,0,255);CPenr_pen(PS_SOLID,1,RGB(255,0,0);CBrushy_brush,b_brush;y_brush.CreateSolidBrush(RGB(255,255,0);b_b

13、rush.CreateSolidBrush(RGB(255,255,255);MemDC.CreateCompatibleDC(&dc);/建立兼容的内存显示设备MemBitmap.CreateCompatibleBitmap(&dc,w,h);建立一个兼容的位图CBitmap*pOldBit=MemDC.SelectObject(&MemBitmap);MemDC.FillRect(CRect(0,0,w,h),&b_brush);if(cell7)MemDC.TextOut(0,h/2,太大，画不下了！);elseDrawBoard(&MemDC,n,cell);MemDC.SelectO

14、bject(b_pen);MemDC.SelectObject(y_brush);for(i=0;i=0)MemDC.Ellipse(queeni*cell+cell/6,i*cell+cell/6,queeni*cell+cell/6+cell*2/3,i*cell+cell/6+cell*2/3);count+;ReleaseMutex(queen_mutex);dc.BitBlt(0,0,w,h,&MemDC,0,0,SRCCOPY);voidQueenPanel:DrawBoard(CDC*pDC,intsize,intcell)inti,j;CBrushw_brush,b_brush

15、;b_brush.CreateSolidBrush(RGB(0,0,0);w_brush.CreateSolidBrush(RGB(255,255,255);for(i=0;isize;i+)for(j=0;jFillRect(CRect(i*cell,j*cell,(i+1)*cell-1,(j+1)*cell-1),&b_brush);elsepDC-FillRect(CRect(i*cell,j*cell,(i+1)*cell-1,(j+1)*cell-1),&w_brush);CPenb_pen(PS_SOLID,1,RGB(0,0,0);intboard=cell*size;pDC-

16、SelectObject(b_pen);pDC-MoveTo(0,0);pDC-LineTo(0,board-1);pDC-LineTo(board-1,board-1);pDC-LineTo(board-1,0);pDC-LineTo(0,0);voidQueenPanel:SetSize(intsize)WaitForSingleObject(queen_mutex,INFINITE);if(sizen)if(queen!=NULL)free(queen);queen=(int*)malloc(size*sizeof(int);for(inti=0;isize;i+)queeni=-1;n

17、=size;ReleaseMutex(queen_mutex);RedrawWindow();voidQueenPanel:SetQueen(int*newq)WaitForSingleObject(queen_mutex,INFINITE);inti;for(i=0;in;i+)queeni=newqi;ReleaseMutex(queen_mutex);RedrawWindow();voidQueenPanel:SetQueen(introw,intcol)WaitForSingleObject(queen_mutex,INFINITE);queenrow=col;ReleaseMutex(queen_mutex);RedrawWindow();在CEightQueenDlg.cpp中的顶部添加如下代码#includeQueenPanel.h将QueenPanel.h包含