ninegriddlg.cpp

八数码问题的C++程序代码。八数码问题是个典型的状态图搜索问题。搜索方式有两种基本的方式

// NineGridDlg.cpp : implementation file
//

#include "stdafx.h"
#include "NineGrid.h"
#include "NineGridDlg.h"
#include "NineGird.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)
	//}}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)
		// No message handlers
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CNineGridDlg dialog

CNineGridDlg::CNineGridDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CNineGridDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CNineGridDlg)
	m_s0_0 = 0;
	m_s0_1 = 0;
	m_s0_2 = 0;
	m_s0_3 = 0;
	m_s0_4 = 0;
	m_s0_5 = 0;
	m_s0_6 = 0;
	m_s0_7 = 0;
	m_s0_8 = 0;
	m_sg_0 = 0;
	m_sg_1 = 0;
	m_sg_2 = 0;
	m_sg_3 = 0;
	m_sg_4 = 0;
	m_sg_5 = 0;
	m_sg_6 = 0;
	m_sg_7 = 0;
	m_sg_8 = 0;
	m_strCaluResult = _T("");
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CNineGridDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CNineGridDlg)
	DDX_Control(pDX, IDC_EDIT_OUTPUT, m_output);
	DDX_Control(pDX, IDC_EDIT_CALU_RESULT, m_edtcntl_output);
	DDX_Text(pDX, IDC_EDIT0_S0, m_s0_0);
	DDV_MinMaxInt(pDX, m_s0_0, 0, 9);
	DDX_Text(pDX, IDC_EDIT1_S0, m_s0_1);
	DDV_MinMaxInt(pDX, m_s0_1, 0, 9);
	DDX_Text(pDX, IDC_EDIT2_S0, m_s0_2);
	DDV_MinMaxInt(pDX, m_s0_2, 0, 9);
	DDX_Text(pDX, IDC_EDIT3_S0, m_s0_3);
	DDV_MinMaxInt(pDX, m_s0_3, 0, 9);
	DDX_Text(pDX, IDC_EDIT4_S0, m_s0_4);
	DDV_MinMaxInt(pDX, m_s0_4, 0, 9);
	DDX_Text(pDX, IDC_EDIT5_S0, m_s0_5);
	DDV_MinMaxInt(pDX, m_s0_5, 0, 9);
	DDX_Text(pDX, IDC_EDIT6_S0, m_s0_6);
	DDV_MinMaxInt(pDX, m_s0_6, 0, 9);
	DDX_Text(pDX, IDC_EDIT7_S0, m_s0_7);
	DDV_MinMaxInt(pDX, m_s0_7, 0, 9);
	DDX_Text(pDX, IDC_EDIT8_S0, m_s0_8);
	DDV_MinMaxInt(pDX, m_s0_8, 0, 9);
	DDX_Text(pDX, IDC_EDIT0_SG, m_sg_0);
	DDV_MinMaxInt(pDX, m_sg_0, 0, 8);
	DDX_Text(pDX, IDC_EDIT1_SG, m_sg_1);
	DDV_MinMaxInt(pDX, m_sg_1, 0, 8);
	DDX_Text(pDX, IDC_EDIT2_SG, m_sg_2);
	DDV_MinMaxInt(pDX, m_sg_2, 0, 8);
	DDX_Text(pDX, IDC_EDIT3_SG, m_sg_3);
	DDV_MinMaxInt(pDX, m_sg_3, 0, 8);
	DDX_Text(pDX, IDC_EDIT4_SG, m_sg_4);
	DDV_MinMaxInt(pDX, m_sg_4, 0, 8);
	DDX_Text(pDX, IDC_EDIT5_SG, m_sg_5);
	DDV_MinMaxInt(pDX, m_sg_5, 0, 8);
	DDX_Text(pDX, IDC_EDIT6_SG, m_sg_6);
	DDV_MinMaxInt(pDX, m_sg_6, 0, 8);
	DDX_Text(pDX, IDC_EDIT7_SG, m_sg_7);
	DDV_MinMaxInt(pDX, m_sg_7, 0, 8);
	DDX_Text(pDX, IDC_EDIT8_SG, m_sg_8);
	DDV_MinMaxInt(pDX, m_sg_8, 0, 8);
	DDX_Text(pDX, IDC_EDIT_CALU_RESULT, m_strCaluResult);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CNineGridDlg, CDialog)
	//{{AFX_MSG_MAP(CNineGridDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDC_BUTTON_INI, OnButtonIni)
	ON_WM_CLOSE()
	ON_BN_CLICKED(IDC_BUTTON_BEGIN, OnButtonBegin)
	ON_BN_CLICKED(IDC_BUTTON_END, OnButtonEnd)
	//}}AFX_MSG_MAP
	ON_MESSAGE(WM_UPDATAMSG,OnReceThreadMsg)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CNineGridDlg message handlers

BOOL CNineGridDlg::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 here
	m_pNineGrid = new CNineGird();
	m_bCanRunThread = FALSE;
	m_pMeThread = NULL;
	
	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CNineGridDlg::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 CNineGridDlg::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 CNineGridDlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}

//产生随机数
void CNineGridDlg::OnButtonIni() 
{
	char * p;
	char c[2]= {1,2};
	p=c;

	m_pNineGrid->CreateIniStatus();

	m_s0_0 = m_pNineGrid->m_iIniChess[0];
	m_s0_1 = m_pNineGrid->m_iIniChess[1];
	m_s0_2 = m_pNineGrid->m_iIniChess[2];
	m_s0_3 = m_pNineGrid->m_iIniChess[3];
	m_s0_4 = m_pNineGrid->m_iIniChess[4];
	m_s0_5 = m_pNineGrid->m_iIniChess[5];
	m_s0_6 = m_pNineGrid->m_iIniChess[6];
	m_s0_7 = m_pNineGrid->m_iIniChess[7];
	m_s0_8 = m_pNineGrid->m_iIniChess[8];

	m_sg_0 = m_pNineGrid->m_iTargetChess[0];
	m_sg_1 = m_pNineGrid->m_iTargetChess[1];
	m_sg_2 = m_pNineGrid->m_iTargetChess[2];
	m_sg_3 = m_pNineGrid->m_iTargetChess[3];
	m_sg_4 = m_pNineGrid->m_iTargetChess[4];
	m_sg_5 = m_pNineGrid->m_iTargetChess[5];
	m_sg_6 = m_pNineGrid->m_iTargetChess[6];
	m_sg_7 = m_pNineGrid->m_iTargetChess[7];
	m_sg_8 = m_pNineGrid->m_iTargetChess[8];

	UpdateData(FALSE);

}

void CNineGridDlg::OnClose() 
{
	// TODO: Add your message handler code here and/or call default
	delete	m_pNineGrid;
	
	CDialog::OnClose();
}

//开始计算数据
void CNineGridDlg::OnButtonBegin() 
{

	if(JudgeIniDataValid() == FALSE)
	{
		AfxMessageBox("数据初始化状态有误!数据有重复或者数据超过0~8的范围,请确定!");
		return;
	}

	//把当前初始状态赋值给m_pNineGrid->m_iIniChess
	unsigned char m_iChess[9];
	UpdateData(TRUE);
	m_iChess[0] = m_s0_0;
	m_iChess[1] = m_s0_1;
	m_iChess[2] = m_s0_2;
	m_iChess[3] = m_s0_3;
	m_iChess[4] = m_s0_4;
	m_iChess[5] = m_s0_5;
	m_iChess[6] = m_s0_6;
	m_iChess[7] = m_s0_7;
	m_iChess[8] = m_s0_8;

	memcpy(m_pNineGrid->m_iIniChess , m_iChess , 9);

	if (!m_pNineGrid->EstimateUncoil(m_iChess))
	{
		unsigned char array[9] = {1,2,3,8,0,4,7,6,5};
		memcpy(m_pNineGrid->m_iTargetChess , array , 9);
	}
	else
	{
		unsigned char array[9] = {1,2,3,4,5,6,7,8,0};
		memcpy(m_pNineGrid->m_iTargetChess , array , 9);
	}

	m_s0_0 = m_pNineGrid->m_iIniChess[0];
	m_s0_1 = m_pNineGrid->m_iIniChess[1];
	m_s0_2 = m_pNineGrid->m_iIniChess[2];
	m_s0_3 = m_pNineGrid->m_iIniChess[3];
	m_s0_4 = m_pNineGrid->m_iIniChess[4];
	m_s0_5 = m_pNineGrid->m_iIniChess[5];
	m_s0_6 = m_pNineGrid->m_iIniChess[6];
	m_s0_7 = m_pNineGrid->m_iIniChess[7];
	m_s0_8 = m_pNineGrid->m_iIniChess[8];

	m_sg_0 = m_pNineGrid->m_iTargetChess[0];
	m_sg_1 = m_pNineGrid->m_iTargetChess[1];
	m_sg_2 = m_pNineGrid->m_iTargetChess[2];
	m_sg_3 = m_pNineGrid->m_iTargetChess[3];
	m_sg_4 = m_pNineGrid->m_iTargetChess[4];
	m_sg_5 = m_pNineGrid->m_iTargetChess[5];
	m_sg_6 = m_pNineGrid->m_iTargetChess[6];
	m_sg_7 = m_pNineGrid->m_iTargetChess[7];
	m_sg_8 = m_pNineGrid->m_iTargetChess[8];

	UpdateData(FALSE);


	if(!m_bCanRunThread)
	{
		m_bCanRunThread = TRUE;
		m_pMeThread = AfxBeginThread((AFX_THREADPROC)CaluPath,this);
	}
	/*
	//开始计算搜索
	m_pNineGrid->SearchTargetChess(m_pNineGrid->m_iIniChess,m_pNineGrid->m_iTargetChess);

	//输出路径
	CString strTmp,strOutput;
	int iLen=m_edtcntl_output.GetWindowTextLength();
	m_edtcntl_output.SetSel(0,iLen);
	m_edtcntl_output.ReplaceSel("");
	iLen=m_edtcntl_output.GetWindowTextLength();
	strOutput = "解的路径为:\r\n";
	if(!m_pNineGrid->m_PathList.IsEmpty())
	{
		Node *pNode = NULL;
		
		unsigned char aiChess[9];
		POSITION posList = m_pNineGrid->m_PathList.GetHeadPosition();
		for (int i = 0; i < m_pNineGrid->m_PathList.GetCount(); i++)
		{
			pNode = (Node *)m_pNineGrid->m_PathList.GetNext(posList);
			m_pNineGrid->DwordToArray(pNode->dwStatus,aiChess);
			strTmp.Format("%d %d %d %d %d %d %d %d %d ;\r\n",
				aiChess[0],aiChess[1],aiChess[2],aiChess[3],
				aiChess[4],aiChess[5],aiChess[6],aiChess[7],aiChess[8]);
			strOutput += strTmp;
		}
	}
	
	m_edtcntl_output.SetSel(iLen,iLen);
	m_edtcntl_output.ReplaceSel(strOutput);
	*/


}

//判定数据初始化状态的有效性
BOOL CNineGridDlg::JudgeIniDataValid(void)
{
	unsigned char m_iChess[9];

	UpdateData(TRUE);
	m_iChess[0] = m_s0_0;
	m_iChess[1] = m_s0_1;
	m_iChess[2] = m_s0_2;
	m_iChess[3] = m_s0_3;
	m_iChess[4] = m_s0_4;
	m_iChess[5] = m_s0_5;
	m_iChess[6] = m_s0_6;
	m_iChess[7] = m_s0_7;
	m_iChess[8] = m_s0_8;

	BOOL bFlag = TRUE;
	for(int i=0;i<9;i++)
	{
		if(m_iChess[i] > 8 || m_iChess[i] <0)
		{
			bFlag = FALSE;
			break;
		}
	}

	for(i=0;i<8;i++)
	{
		for(int j=i+1;j<9;j++)
		{
			if(m_iChess[i] == m_iChess[j])
			{
				bFlag = FALSE;
			break;
			}
		}
	}

	return bFlag;

}

//终止计算
void CNineGridDlg::OnButtonEnd() 
{
	// TODO: Add your control notification handler code here
	if(m_pMeThread != NULL)
	{
		TerminateThread(m_pMeThread->m_hThread,0);
		CloseHandle(m_pMeThread->m_hThread);
		m_bCanRunThread = FALSE;
	}
}

LRESULT CNineGridDlg::OnReceThreadMsg(WPARAM wParam,LPARAM lParam)
{

	DWORD dwNo = (DWORD)lParam;
	DWORD dwStep = (DWORD)wParam;
	
	CString strTmp;
	if(dwStep == 0)//计算过程中
	{
		strTmp.Format("正在计算中...\r\n当前计算步数为:%d",dwNo);
		int iLen=m_output.GetWindowTextLength();
		m_output.SetSel(0,iLen);
		m_output.ReplaceSel(strTmp);
	}
	else if(dwStep == 1)//计算完成
	{
		strTmp.Format("计算完成!\r\n当前计算总步数为:%d",dwNo);
		int iLen=m_output.GetWindowTextLength();
		m_output.SetSel(0,iLen);
		m_output.ReplaceSel(strTmp);
		
		//输出路径
		CString strTmp,strOutput;
		iLen=m_edtcntl_output.GetWindowTextLength();
		m_edtcntl_output.SetSel(0,iLen);
		m_edtcntl_output.ReplaceSel("");
		iLen=m_edtcntl_output.GetWindowTextLength();
		strOutput = "解的路径为:\r\n";
		if(!m_pNineGrid->m_PathList.IsEmpty())
		{
			Node *pNode = NULL;
			
			unsigned char aiChess[9];
			POSITION posList = m_pNineGrid->m_PathList.GetHeadPosition();
			for (int i = 0; i < m_pNineGrid->m_PathList.GetCount(); i++)
			{
				pNode = (Node *)m_pNineGrid->m_PathList.GetNext(posList);
				m_pNineGrid->DwordToArray(pNode->dwStatus,aiChess);
				strTmp.Format("%d %d %d %d %d %d %d %d %d ;\r\n",
					aiChess[0],aiChess[1],aiChess[2],aiChess[3],
					aiChess[4],aiChess[5],aiChess[6],aiChess[7],aiChess[8]);
				strOutput += strTmp;
			}
		}
		
		m_edtcntl_output.SetSel(iLen,iLen);
		m_edtcntl_output.ReplaceSel(strOutput);
	}

	return 0L;
}

//计算线程
UINT CaluPath(LPVOID pParam)
{
	CNineGridDlg *pDlg = (CNineGridDlg *)pParam;
	
	pDlg->m_pNineGrid->SearchTargetChess(pDlg->m_pNineGrid->m_iIniChess,
		pDlg->m_pNineGrid->m_iTargetChess,pDlg->GetSafeHwnd());

	return 0;
}