nqueendlg.cpp

自己用MFC设计的N皇后问题演示程序

// NQueenDlg.cpp : implementation file
//

#include "stdafx.h"
#include "NQueen.h"
#include "NQueenDlg.h"
#include "DlgProxy.h"
#include "InputMessage.h"
#include "AboutDlg.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CNQueenDlg dialog

IMPLEMENT_DYNAMIC(CNQueenDlg, CDialog);

CNQueenDlg::CNQueenDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CNQueenDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CNQueenDlg)
		// NOTE: the ClassWizard will add member initialization here
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
	m_pAutoProxy = NULL;

	/*
	m_font.CreateFont(12,12,0,0,FW_LIGHT,   
		FALSE,FALSE,FALSE,   
		DEFAULT_CHARSET,   
		OUT_CHARACTER_PRECIS,CLIP_CHARACTER_PRECIS,   
		DEFAULT_QUALITY,DEFAULT_PITCH|FF_DONTCARE,"楷体_GB2312");   
	*/
	m_font.CreateFont(20,0,0,0,FW_NORMAL,   
                              FALSE,FALSE,FALSE,DEFAULT_CHARSET,   
                              OUT_RASTER_PRECIS,CLIP_DEFAULT_PRECIS,   
                              VARIABLE_PITCH|PROOF_QUALITY,FF_DONTCARE,"楷体_GB2312");   
  
}

CNQueenDlg::~CNQueenDlg()
{
	// If there is an automation proxy for this dialog, set
	//  its back pointer to this dialog to NULL, so it knows
	//  the dialog has been deleted.
	if (m_pAutoProxy != NULL)
		m_pAutoProxy->m_pDialog = NULL;
}

void CNQueenDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CNQueenDlg)
		// NOTE: the ClassWizard will add DDX and DDV calls here
		DDX_Control(pDX, IDC_STATIC1, m_mainboard);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CNQueenDlg, CDialog)
	//{{AFX_MSG_MAP(CNQueenDlg)
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_WM_CTLCOLOR()
	ON_WM_CANCELMODE()
	ON_WM_LBUTTONDOWN()
	ON_WM_CAPTURECHANGED()
	ON_BN_CLICKED(IDC_START, OnStart)
	ON_BN_CLICKED(IDC_SETSIZE, OnSetsize)
	ON_BN_CLICKED(IDC_END_STEP, OnEndStep)
	ON_BN_CLICKED(IDC_NEXT_STEP, OnNextStep)
	ON_BN_CLICKED(IDC_CLEAR, OnClear)
	ON_BN_CLICKED(IDC_EXIT, OnExit)
	ON_BN_CLICKED(IDC_ABOUT, OnAbout)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CNQueenDlg message handlers

BOOL CNQueenDlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// Set the icon for this dialog.  The framework does this automatically
	//  when the application's main window is not a dialog
	SetIcon(m_hIcon, TRUE);			// Set big icon
	SetIcon(m_hIcon, FALSE);		// Set small icon
	
	// TODO: Add extra initialization here
	CWnd   *pWnd   =   GetDlgItem(IDC_STATIC);   
	pWnd->SetFont(&m_font);   
	pWnd=GetDlgItem(IDC_QUEEN_SIZE);
	pWnd->SetFont(&m_font);
	
	((CButton *)GetDlgItem(IDC_AUTO_STEP))->SetCheck(1);
	GetDlgItem(IDC_NEXT_STEP)->EnableWindow(false);
	GetDlgItem(IDC_END_STEP)->EnableWindow(false);
	GetDlgItem(IDC_CLEAR)->EnableWindow(false);

	SetWindowText("N皇后问题");
	SetTimer(1,500,0);
	CRect rc;
	m_mainboard.GetClientRect(&rc);
	
	//默认为8	
	N=8;
	GetDlgItem(IDC_QUEEN_SIZE)->SetWindowText("8");
	int x = rc.right-rc.left;
	int y = rc.bottom-rc.top ;
	board = x >= y ? y : x;
	board = board - board % N;
    cell = board / N;
	auto_paint=false;
	man_paint=false;
	step=0;
	nways=0;
	for(int i=0;i<20;i++)
		for(int j=0;j<20;j++)
			queen[i][j]=0;
	return TRUE;  // return TRUE  unless you set the focus to a control
}

// If you add a minimize button to your dialog, you will need the code below
//  to draw the icon.  For MFC applications using the document/view model,
//  this is automatically done for you by the framework.

void CNQueenDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // device context for painting

		SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

		// Center icon in client rectangle
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// Draw the icon
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();
	}
	DrawGrid();
	DrawAllChess();
}

// The system calls this to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CNQueenDlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}

// Automation servers should not exit when a user closes the UI
//  if a controller still holds on to one of its objects.  These
//  message handlers make sure that if the proxy is still in use,
//  then the UI is hidden but the dialog remains around if it
//  is dismissed.

//DEL void CNQueenDlg::OnClose() 
//DEL {
//DEL 	if (CanExit())
//DEL 		CDialog::OnClose();
//DEL }

//DEL void CNQueenDlg::OnOK() 
//DEL {
//DEL 	
//DEL }

//DEL void CNQueenDlg::OnCancel() 
//DEL {
//DEL 	if (CanExit())
//DEL 		CDialog::OnCancel();
//DEL }

//DEL BOOL CNQueenDlg::CanExit()
//DEL {
//DEL 	// If the proxy object is still around, then the automation
//DEL 	//  controller is still holding on to this application.  Leave
//DEL 	//  the dialog around, but hide its UI.
//DEL 	if (m_pAutoProxy != NULL)
//DEL 	{
//DEL 		ShowWindow(SW_HIDE);
//DEL 		return FALSE;
//DEL 	}
//DEL 
//DEL 	return TRUE;
//DEL }

/************

画类似象棋棋盘

*************/

void CNQueenDlg::DrawGrid()
{
	CDC *pDC = m_mainboard.GetDC();
	CRect rc ;
	m_mainboard.GetClientRect(&rc);	
	

	int i, j;
	CBrush w_brush, b_brush;
	b_brush.CreateSolidBrush(RGB(0, 0, 0));	
	w_brush.CreateSolidBrush(RGB(255, 255, 255));
	w_brush.CreateStockObject(0);
	b_brush.CreateStockObject(BLACK_BRUSH);
	for(i=0; i<N; i++) {
		for(j=0; j<N; j++) {
			w_brush.CreateStockObject(0);
			b_brush.CreateStockObject(BLACK_BRUSH);
			if((i+j)%2 ==0 ) {
				if(queen[i][j]==2 && man_paint==true)
					b_brush.CreateStockObject(DKGRAY_BRUSH);
				pDC->FillRect(CRect(i*cell, j*cell+6, (i+1)*cell, (j+1)*cell+6), &b_brush);
			} 
			else {
				if(queen[i][j]==2 && man_paint==true)
					w_brush.CreateStockObject(HOLLOW_BRUSH);
				pDC->FillRect(CRect(i*cell, j*cell+6, (i+1)*cell, (j+1)*cell+6), &w_brush);
			}
		}
	}
	
}

void CNQueenDlg::DrawChess(CPoint point)
{
	CDC *pDC = m_mainboard.GetDC();
	CRect rc ;
	m_mainboard.GetClientRect(&rc);
	int x=point.x;
	int y=point.y-19;
	
	int i=x/cell;
	int j=y/cell;
	if(i>N-1 || j>N-1 || queen[i][j]!=0)
		return ;
	
	step++;      //步数加１
	DisableXY(i,j);
	CPen b_pen(PS_SOLID, 1, RGB(0, 0, 255));
	CBrush y_brush;
	y_brush.CreateSolidBrush(RGB(255, 0, 0));	
	pDC->SelectObject(b_pen);
	pDC->SelectObject(y_brush);

	pDC->Ellipse(i*cell+cell/6,j*cell+6+cell/6,(i+1)*cell-cell/6,(j+1)*cell+6-cell/6);
	queen[i][j]=1;
	Invalidate();

}

void CNQueenDlg::DrawChess(int i,int j)
{
	CDC * pDC = m_mainboard.GetDC();
	if (queen[i][j] == 0)
		return;	
	
	CPen b_pen(PS_SOLID, 1, RGB(0, 0, 255));
	CBrush y_brush;
	y_brush.CreateSolidBrush(RGB(255, 0, 0));	
	pDC->SelectObject(b_pen);
	pDC->SelectObject(y_brush);
	pDC->Ellipse(i*cell+cell/6,j*cell+6+cell/6,(i+1)*cell-cell/6,(j+1)*cell+6-cell/6);

}

void CNQueenDlg::DrawAllChess()
{
	for (int i = 0 ; i <20 ; i++ )
		for (int j= 0; j<20 ; j++ )
		{
			if (queen[i][j] == 1)
			{
					DrawChess(i,j);
			}

		}
}


HBRUSH CNQueenDlg::OnCtlColor(CDC* pDC, CWnd* pWnd, UINT nCtlColor) 
{
	HBRUSH hbr = CDialog::OnCtlColor(pDC, pWnd, nCtlColor);
	pDC->SetBkMode(TRANSPARENT);
	if (nCtlColor !=  CTLCOLOR_EDIT &&  nCtlColor !=  CTLCOLOR_LISTBOX) 
		hbr = ::CreateSolidBrush(RGB(128,128,200));

	return hbr;
}

void CNQueenDlg::OnCancelMode() 
{
	CDialog::OnCancelMode();
	
	// TODO: Add your message handler code here
	
}

void CNQueenDlg::OnLButtonDown(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default
	if(!man_paint)
		return ;
	
	DrawChess(point);
	if(step==N)
		MessageBox("恭喜你成功！\n\n你可以点击重新开始新的布局，也可以结束此次下棋。", "小提示", MB_OK);


	CDialog::OnLButtonDown(nFlags, point);
}

void CNQueenDlg::OnCaptureChanged(CWnd *pWnd) 
{
	// TODO: Add your message handler code here
	
	CDialog::OnCaptureChanged(pWnd);
}



void CNQueenDlg::OnStart() 
{
	DWORD dwThreadId; 
    HANDLE hThread;   

	if(((CButton *)GetDlgItem(IDC_AUTO_STEP))->GetCheck() == 1)
	{
		//选择自动
		auto_paint=true;
		canceling=false;
		nways=0;
		hThread = CreateThread( 
			NULL,                        // default security attributes 
			0,                           // use default stack size  
			ThreadGo,                  // thread function 
			this,                // argument to thread function 
			0,                           // use default creation flags 
			&dwThreadId);                // returns the thread identifier 
		
		// Check the return value for success. 
		
		if (hThread == NULL) 
		{     
			MessageBox( NULL, "CreateThread failed.", MB_OK );
		}
		GetDlgItem(IDC_NEXT_STEP)->EnableWindow(true);
	}
	else
	{
		//选择手动
		man_paint=true;
		step=0;
		GetDlgItem(IDC_CLEAR)->EnableWindow(true);
		
		
	}

	GetDlgItem(IDC_SETSIZE)->EnableWindow(false);
	GetDlgItem(IDC_END_STEP)->EnableWindow(true);
	GetDlgItem(IDC_START)->EnableWindow(false);
	Invalidate();
	// TODO: Add your control notification handler code here
	
}

//DEL void CNQueenDlg::OnAutoStep() 
//DEL {
//DEL 	// TODO: Add your control notification handler code here
//DEL 	((CButton *)GetDlgItem(IDC_AUTO_STEP))->SetCheck(1);
//DEL 	
//DEL }

//DEL void CNQueenDlg::OnChangeQueenSize() 
//DEL {
//DEL 	// TODO: If this is a RICHEDIT control, the control will not
//DEL 	// send this notification unless you override the CDialog::OnInitDialog()
//DEL 	// function and call CRichEditCtrl().SetEventMask()
//DEL 	// with the ENM_CHANGE flag ORed into the mask.
//DEL 	
//DEL 	// TODO: Add your control notification handler code here
//DEL 
//DEL 	//}
//DEL }

BOOL CNQueenDlg::PreTranslateMessage(MSG* pMsg) 
{
	// TODO: Add your specialized code here and/or call the base class
	if(pMsg->message   ==   WM_KEYDOWN)   
	{   
		switch(pMsg->wParam)   
		{   
		case   VK_RETURN://屏蔽回车   
		
			//   OnKeyDown(VK_SPACE,   LOWORD(pMsg   ->lParam),   HIWORD(pMsg->lParam));     
			return   TRUE;   
		case   VK_ESCAPE://屏蔽Esc   
			return   TRUE;   
		}   
	}   
	

	return CDialog::PreTranslateMessage(pMsg);
}

/*

  当更新了皇后N的大小时，视图必须更新，窗格等都得重新计算

*/
void CNQueenDlg::OnOK()
{
	CDC *pDC = m_mainboard.GetDC();
	CRect rc ;
	m_mainboard.GetClientRect(&rc);
	CString str;
	GetDlgItem(IDC_QUEEN_SIZE)->GetWindowText(str);
	
	int newn = atoi(str);
	N = newn;
	
	int x = rc.right-rc.left;
	int y = rc.bottom-rc.top ;
	board = x >= y ? y : x;
	board = board - board % N;
    cell = board / N;
	
	Invalidate();
}

void CNQueenDlg::OnSetsize() 
{
	// TODO: Add your control notification handler code here
	/*
	**
	输入对话框，输入N
	**
	*/
	InputMessage input;
	if(input.DoModal()==IDOK)
	{
			
		GetDlgItem(IDC_QUEEN_SIZE)->SetWindowText(input.size);
		OnOK();
	}

}

//结束此演示
void CNQueenDlg::OnEndStep() 
{
	// TODO: Add your control notification handler code here
	int i,j;
	
	if(auto_paint)
	{
		for(i=0;i<20;i++)
			a[i]=-1;
		GetDlgItem(IDC_NEXT_STEP)->EnableWindow(false);
		auto_paint=false;
		next_step=true;
		canceling=true;
	}
	else
	{
		man_paint=false;
	}
	GetDlgItem(IDC_END_STEP)->EnableWindow(false);
	GetDlgItem(IDC_START)->EnableWindow(true);
	GetDlgItem(IDC_SETSIZE)->EnableWindow(true);
	GetDlgItem(IDC_CLEAR)->EnableWindow(false);
	for( i=0;i<20;i++)
		for( j=0;j<20;j++)
			queen[i][j]=0;
	Invalidate();
}

//自动时下一摆法
void CNQueenDlg::OnNextStep() 
{
	// TODO: Add your control notification handler code here
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			queen[i][j]=0;
	next_step=true;
	Invalidate();
	
}

//手动检测不符合规则，不符合就将位置标记
void CNQueenDlg::DisableXY(int i, int j)
{
	int temp1,temp2;
	for(int k=0;k<N;k++)
	{
		if(k!=j)
			queen[i][k]=2;
		if(k!=i)
			queen[k][j]=2;
	}
	temp1=i;
	temp2=j;
	while(temp1>0 && temp2>0)
	{
		temp1--;
		temp2--;
		queen[temp1][temp2]=2;
	}
	temp1=i;
	temp2=j;
	while(temp1>0 && temp2<N-1)
	{
		temp1--;
		temp2++;
		queen[temp1][temp2]=2;
	}
	temp1=i;
	temp2=j;
	while(temp1<N-1 && temp2>0)
	{
		temp1++;
		temp2--;
		queen[temp1][temp2]=2;
	}
	temp1=i;
	temp2=j;
	while(temp1<N-1 && temp2<N-1)
	{
		temp1++;
		temp2++;
		queen[temp1][temp2]=2;
	}
	
}

//清除所有已画棋子重画
void CNQueenDlg::OnClear() 
{
	// TODO: Add your control notification handler code here
	step=0;
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			queen[i][j]=0;
	Invalidate();
}

DWORD WINAPI CNQueenDlg::ThreadGo(LPVOID lpParam)
{
	CNQueenDlg *dlg=(CNQueenDlg *)lpParam;
	dlg->Go();
	return 0;
}

void WINAPI CNQueenDlg::Go()
{

	SetQueen(0);
	if(!canceling) {
		TCHAR msg[30];
		sprintf(msg, "找到%d种组合。", nways);
		MessageBox(msg, "N皇后问题", MB_OK);
	}
	OnEndStep();
	Invalidate();
}

int CNQueenDlg::CanSetQueen(int i, int j)
{
	int j1,ok1,i1;
	j1=j;
	i1=i;
	ok1=1;  //检查第i行上能否放棋子
	while( (j1>0) && ok1)
	{
		j1--;     
		ok1=a[j1]!=i ;
	}

	j1=j; i1=i;    //检查对角线上能否放棋子
	while( (j1>0)&&(i1>0)&&ok1) 
    {
		j1--;
		i1--; 
		ok1=a[j1]!=i1 ;
	} 

    j1=j; i1=i;     //检查另一对角线上能否放棋子
    while( (j1>0)&&(i1<N-1)&&ok1) 
    {
		j1--; 
		i1++;
		ok1=a[j1]!=i1 ;
	}
    return  ok1;
}

//DEL void WINAPI CNQueenDlg::SetQueen(int i)
//DEL {
//DEL 
//DEL }

void WINAPI CNQueenDlg::SetQueen(int j)
{
	if (j>N-1) 
    {
		//WaitForSingleObject(this_mutex, INFINITE);
		for (int i=0;i<=N-1;i++) 
			queen[i][a[i]]=1;
		next_step=false;
		nways++;
		Invalidate();

		while(!next_step)
		{}
        
    }    
	else  
		for(int i=0; i<=N-1;i++)
		{
			if(canceling)
				return ;
			if(CanSetQueen(i,j))  //检查(i,j)上能否放棋子
			{
				//WaitForSingleObject(this_mutex, INFINITE);
				a[j]=i; //在(i,j)上放一个棋子				
				SetQueen(j+1);
				//ReleaseMutex(this_mutex);
			} 
		}

}

void CNQueenDlg::OnExit() 
{
	// TODO: Add your control notification handler code here
	exit(0);
}

void CNQueenDlg::OnAbout() 
{
	// TODO: Add your control notification handler code here
	CAboutDlg dlgAbout;
	dlgAbout.DoModal();	
}