eightqueendlg.cpp

八皇后问题:在8行8列的棋盘上放置8个皇后

// EightQueenDlg.cpp : implementation file
//

#include "stdafx.h"
#include "EightQueen.h"
#include "EightQueenDlg.h"
#include "QueenPanel.h"

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

/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// Dialog Data
	//{{AFX_DATA(CAboutDlg)
	enum { IDD = IDD_ABOUTBOX };
	//}}AFX_DATA

	// ClassWizard generated virtual function overrides
	//{{AFX_VIRTUAL(CAboutDlg)
	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
	//}}AFX_VIRTUAL

// Implementation
protected:
	//{{AFX_MSG(CAboutDlg)
	virtual BOOL OnInitDialog();
	//}}AFX_MSG
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
	//{{AFX_DATA_INIT(CAboutDlg)
	//}}AFX_DATA_INIT
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAboutDlg)
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
	//{{AFX_MSG_MAP(CAboutDlg)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CEightQueenDlg dialog

CEightQueenDlg::CEightQueenDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CEightQueenDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CEightQueenDlg)
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CEightQueenDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CEightQueenDlg)
	DDX_Control(pDX, IDC_QUEEN_PANEL, m_panel);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CEightQueenDlg, CDialog)
	//{{AFX_MSG_MAP(CEightQueenDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDC_START, OnStart)
	ON_BN_CLICKED(IDC_PAUSE, OnPause)
	ON_BN_CLICKED(IDC_CONTINUE, OnContinue)
	ON_WM_CLOSE()
	ON_BN_CLICKED(IDC_STEP_BY, OnStepBy)
	ON_BN_CLICKED(IDC_ABOUT, OnAbout)
	ON_BN_CLICKED(IDC_STOP, OnStop)
	ON_BN_CLICKED(IDC_NO_INT, OnNoInt)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CEightQueenDlg message handlers

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

	// Add "About..." menu item to system menu.

	// IDM_ABOUTBOX must be in the system command range.
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// 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 her
	this_mutex = CreateMutex(NULL,FALSE,NULL);
	pause_event = CreateEvent( 
            NULL,     // no security attributes
            TRUE,    // manual-reset event
            FALSE,     // initial state is signaled
            NULL);  
	GetDlgItem(IDC_BOARD_SIZE)->SetWindowText("8");
	m_panel.SetSize(8);
	CButton *step = (CButton *)GetDlgItem(IDC_STEP_BY);
	m_step = (step->GetCheck()==BST_CHECKED)?TRUE:FALSE;
	CButton *no_int = (CButton *)GetDlgItem(IDC_NO_INT);
	m_no_int = (step->GetCheck()==BST_CHECKED)?TRUE:FALSE;
	canceling = running = FALSE;		
	UpdateUI();	
	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CEightQueenDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// 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 CEightQueenDlg::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();
	}
}

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

void CEightQueenDlg::OnStart() 
{
	// TODO: Add your control notification handler code here
	DWORD dwThreadId; 
    HANDLE hThread;    
	
	CString str;
	GetDlgItem(IDC_BOARD_SIZE)->GetWindowText(str);
	int newn = atoi(str);
	if(newn<=0) {
		MessageBox("大小不能小于1", "警告", MB_OK);
		return;
	}
	else {
		n = newn;
	}
	m_panel.SetSize(n);
	step = m_step;
	no_int = m_no_int;
	running = TRUE;
	pausing = canceling = FALSE;
	UpdateUI();
    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 );
   }
   
}

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

void WINAPI CEightQueenDlg::Go() {    
    count = 0;
    queen = new int[n];
    rk = new BOOLEAN[2 * n - 1];
    lk = new BOOLEAN[2 * n - 1];
    mk = new BOOLEAN[n];
    for (int i = 0; i < n; i++) {
      queen[i] = -1;	  
    }    
	memset(rk, 0, (2*n-1)*sizeof(BOOLEAN));
	memset(lk, 0, (2*n-1)*sizeof(BOOLEAN));
	memset(mk, 0, n*sizeof(BOOLEAN));
	ResetEvent(pause_event);
    Step(0);
	delete [] queen;
	delete [] rk;
	delete [] lk;
	delete [] mk;
	if(!canceling) {
		TCHAR msg[30];
		sprintf(msg, "找到%d种组合。", count);
		MessageBox(msg, "八皇后", MB_OK);
	}
	count = 0;
	canceling = running = FALSE;
	UpdateUI();
  }

  /**
   * 安排皇后的递归算法：   
   */

void WINAPI CEightQueenDlg::Step(int i) {
    for (int j = 0; j < n; j++) {
		WaitForSingleObject(this_mutex, INFINITE);
		if(canceling) {
			return;
		}
		ReleaseMutex(this_mutex);
      if (!mk[j] && !rk[i + j]  && !lk[n - 1 + i - j] ) {
        queen[i] = j;
        rk[i + j] = TRUE;
        lk[n - 1 + i - j] = TRUE;
        mk[j] = TRUE;
        if (i == n - 1) {
          count++;          
          UpdateQPanel(i, queen[i]);		  
		  WaitForSingleObject(this_mutex,INFINITE);
		  if(!step&&!no_int) {
			  ReleaseMutex(this_mutex);
			  UpdateUI();
			  DoPause();			  
		  }
		  else {
			  ReleaseMutex(this_mutex);
		  }
          //System.exit(0);
        }
        else {
          UpdateQPanel(i, queen[i]);
          Step(i + 1);
        }
        queen[i] = -1;
        rk[i + j] = FALSE;
        lk[i + n - 1 - j] = FALSE;
        mk[j] = FALSE;
        UpdateQPanel(i, queen[i]);
      }
    }
  }

void CEightQueenDlg::OnPause() 
{
	// TODO: Add your control notification handler code here
	WaitForSingleObject(this_mutex,INFINITE);	
	step = TRUE;
	if(pausing) {
		SetEvent(pause_event); 
	}
	ReleaseMutex(this_mutex);    	
	UpdateUI();
}

void CEightQueenDlg::OnContinue() 
{
	// TODO: Add your control notification handler code here
	WaitForSingleObject(this_mutex,INFINITE);
	step = FALSE;	
	if(pausing) {
		SetEvent(pause_event); 
	}
	ReleaseMutex(this_mutex);	
	UpdateUI();
}

void CEightQueenDlg::OnClose() 
{
	// TODO: Add your message handler code here and/or call default
	if(running) {
		this->MessageBox("正在运行，请先按“停止”按钮停止。", "警告");
	} else
		CDialog::EndDialog(0);
}

void CEightQueenDlg::OnStepBy() 
{
	// TODO: Add your control notification handler code here
	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->SetCheck(FALSE);
		m_no_int = FALSE;
	}
}

void CEightQueenDlg::UpdateUI()
{
	WaitForSingleObject(this_mutex, INFINITE);
	GetDlgItem(IDC_BOARD_SIZE)->EnableWindow(!running&&!canceling);
	GetDlgItem(IDC_NO_INT)->EnableWindow(!running&&!canceling);
	GetDlgItem(IDC_STEP_BY)->EnableWindow(!running&&!canceling);
	GetDlgItem(IDC_START)->EnableWindow(!running&&!canceling);

	GetDlgItem(IDC_PAUSE)->EnableWindow(running&&!canceling);
	GetDlgItem(IDC_CONTINUE)->EnableWindow(running&&!canceling&&pausing);
	GetDlgItem(IDC_STOP)->EnableWindow(running&&!canceling);	
	ReleaseMutex(this_mutex);
}

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

void CEightQueenDlg::UpdateQPanel(int *queen) {
	m_panel.SetQueen(queen);
	WaitForSingleObject(this_mutex, INFINITE);
	if(step) {
		ReleaseMutex(this_mutex);
		DoPause();
	} 
	else {
		ReleaseMutex(this_mutex);
	}
}

void CEightQueenDlg::UpdateQPanel(int row, int col) {
	m_panel.SetQueen(row, col);
	if(step) {
		ReleaseMutex(this_mutex);		
		DoPause();
	} 
	else {
		ReleaseMutex(this_mutex);
	}
}

void CEightQueenDlg::DoPause() {
	WaitForSingleObject(this_mutex, INFINITE);
	pausing = TRUE;
	ReleaseMutex(this_mutex);
	UpdateUI();
	WaitForSingleObject(pause_event,INFINITE);
	ResetEvent(pause_event);
	WaitForSingleObject(this_mutex, INFINITE);
	pausing  = FALSE;
	ReleaseMutex(this_mutex);
	UpdateUI();
}

void CEightQueenDlg::OnStop() 
{
	// TODO: Add your control notification handler code here
	WaitForSingleObject(this_mutex, INFINITE);
	step = FALSE;
	canceling = TRUE;	
	if(pausing) {
		SetEvent(pause_event); 
	}
	ReleaseMutex(this_mutex);	
	UpdateUI();
}


void CEightQueenDlg::OnNoInt() 
{
	// TODO: Add your control notification handler code here
	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;
	}
}

BOOL CAboutDlg::OnInitDialog() 
{
	CDialog::OnInitDialog();
	
	// TODO: Add extra initialization here
	GetDlgItem(IDC_COPY_RIGHT)->SetWindowText("版权所有 Yuan Yq( [e-mail] )");	
	return TRUE;  // return TRUE unless you set the focus to a control
	              // EXCEPTION: OCX Property Pages should return FALSE
}

void CEightQueenDlg::OnOK ()
{
}
void CEightQueenDlg::OnCancel()
{
}