n_queensdemoview.cpp

一个解决国际象棋中的八皇后问题的回溯算法.

// N_QueensDemoView.cpp : implementation of the CN_QueensDemoView class
//

#include "stdafx.h"
#include "N_QueensDemo.h"

#include "MainFrm.h"

#include "N_QueensDemoDoc.h"
#include "N_QueensDemoView.h"

#include "N_Queens.h"
#include "SettingDialog.h"

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

/////////////////////////////////////////////////////////////////////////////
// CN_QueensDemoView

IMPLEMENT_DYNCREATE(CN_QueensDemoView, CView)

BEGIN_MESSAGE_MAP(CN_QueensDemoView, CView)
	//{{AFX_MSG_MAP(CN_QueensDemoView)
	ON_COMMAND(ID_EXEC, OnExec)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CN_QueensDemoView construction/destruction

CN_QueensDemoView::CN_QueensDemoView()
{
	// TODO: add construction code here
	m_v = NULL;
	m_flag = NULL;
	m_n = 8;

	m_d = 75;
	m_pDlgInfo = NULL;
}

CN_QueensDemoView::~CN_QueensDemoView()
{
}

BOOL CN_QueensDemoView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: Modify the Window class or styles here by modifying
	//  the CREATESTRUCT cs

	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CN_QueensDemoView drawing

void CN_QueensDemoView::OnDraw(CDC* pDC)
{
	CN_QueensDemoDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	// TODO: add draw code for native data here
	DrawChessBoard(pDC);
	DrawAllChesses(pDC);
}

/////////////////////////////////////////////////////////////////////////////
// CN_QueensDemoView diagnostics

#ifdef _DEBUG
void CN_QueensDemoView::AssertValid() const
{
	CView::AssertValid();
}

void CN_QueensDemoView::Dump(CDumpContext& dc) const
{
	CView::Dump(dc);
}

CN_QueensDemoDoc* CN_QueensDemoView::GetDocument() // non-debug version is inline
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CN_QueensDemoDoc)));
	return (CN_QueensDemoDoc*)m_pDocument;
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CN_QueensDemoView message handlers

UINT N_QueensFunc( LPVOID pParam );

void CN_QueensDemoView::OnExec() 
{
	// TODO: Add your command handler code here
	CSettingDialog dlg;
	if(IDOK == dlg.DoModal())
	{
		ReleaseSolveV();
		m_n = dlg.m_nQueenNum;

		m_d = WIDTH/m_n;
		((CMainFrame*)AfxGetMainWnd())->ResizeWindow(m_d*m_n,m_d*m_n);
		Invalidate(false);
		UpdateWindow();

		AfxBeginThread(N_QueensFunc,(LPVOID)this);
	}
}

UINT N_QueensFunc( LPVOID pParam )
{
	CN_QueensDemoView* pView = (CN_QueensDemoView*)pParam;
	pView->ShowWaitInfo();
	N_Queens queens(pView->m_n);
	queens.N_QueensIter();
	pView->HideWaitInfo();
	if(queens.IsSolve())
	{
		pView->GetSolveV(queens.GetSolveV(),queens.GetQueensNum());
		//start demo
		pView->ShowDemo();
	}
	else
	{
		//output "No solve"
		pView->MessageBox("No solve!");
	}
	return 0;
}

void CN_QueensDemoView::GetSolveV(int* v,int n)
{
	m_v = new int[n];
	m_flag = new bool[n];
	for(int i=0; i<n; i++)
	{
		m_v[i] = v[i];
		m_flag[i] = false;
	}
}

void CN_QueensDemoView::ReleaseSolveV()
{
	if(m_v != NULL)
	{
		delete []m_v;
		m_v = NULL;
		m_n = 0;
	}
	if(m_flag != NULL)
	{
		delete []m_flag;
		m_flag = NULL;
	}
}

void CN_QueensDemoView::DrawChessBoard(CDC* pDC)
{
	int i,j;
	for(i=0; i<m_n; i++)
	{
		for(j=0; j<m_n; j++)
		{
			if((i+j)%2 == 0)
			{
				//white
				CBrush WhiteBrush(RGB(255,255,255)),*pBrush;
				pBrush = pDC->SelectObject(&WhiteBrush);
				pDC->Rectangle(j*m_d,i*m_d,(j+1)*m_d,(i+1)*m_d);
				pDC->SelectObject(pBrush);
				WhiteBrush.DeleteObject();
			}
			else
			{
				//black
				CBrush BlackBrush(RGB(0,0,0)),*pBrush;
				pBrush = pDC->SelectObject(&BlackBrush);
				pDC->Rectangle(j*m_d,i*m_d,(j+1)*m_d,(i+1)*m_d);
				pDC->SelectObject(pBrush);
				BlackBrush.DeleteObject();
			}
		}
	}
}

void CN_QueensDemoView::DrawChess(CDC* pDC, int i, int j)
{
	CPen pen(PS_SOLID,2,RGB(0,0,255)),*poldPen;
	CBrush brush(RGB(0,0,255)),*poldBrush;
	poldPen = pDC->SelectObject(&pen);
	int x = m_d*j;
	int y = m_d*i;
	int d1 = m_d/25;
	int d2 = m_d*4/25;
	pDC->Ellipse(x+d1,y+d1,x+m_d-d1,y+m_d-d1);
	poldBrush = pDC->SelectObject(&brush);
	pDC->Ellipse(x+d2,y+d2,x+m_d-d2,y+m_d-d2);
	pDC->SelectObject(poldPen);
	pDC->SelectObject(poldBrush);
	pen.DeleteObject();
	brush.DeleteObject();
}

void CN_QueensDemoView::DrawAllChesses(CDC* pDC)
{
	if(m_flag == NULL) 
		return ;
	for(int i=0; i<m_n; i++)
	{
		if(m_flag[i])
		{
			DrawChess(pDC,i,m_v[i]);
		}
	}
}

void CN_QueensDemoView::ShowDemo()
{
	CClientDC dc(this);
	for(int i=0; i<m_n; i++)
	{
		Sleep(500);
		DrawChess(&dc,i,m_v[i]);
		m_flag[i] = true;
	}
}

void CN_QueensDemoView::ShowWaitInfo()
{
	m_pDlgInfo = new CDialog();
	m_pDlgInfo->Create(IDD_DIALOG_WAIT,AfxGetMainWnd());
	m_pDlgInfo->CenterWindow();
	m_pDlgInfo->ShowWindow(SW_SHOW);
	m_pDlgInfo->UpdateWindow();
}

void CN_QueensDemoView::HideWaitInfo()
{
	if(m_pDlgInfo != NULL)
	{
		m_pDlgInfo->DestroyWindow();
		delete m_pDlgInfo;
		m_pDlgInfo = NULL;
	}
}