eightnumwithastardlg.cpp

八数码难题的程序

// EightNumWithAStarDlg.cpp : implementation file
//

#include "stdafx.h"
#include "EightNumWithAStar.h"
#include "EightNumWithAStarDlg.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
#include <math.h>
#define MaxSize  12000   //最大缓冲区

long Original;
long Goal;

struct StateNode 
{
	long Puzzle;
	int Val;
	bool WasOpened;
	int TreeLevel;
	int Parent;
	
};

StateNode NodeList[MaxSize];
int ListIndex;
int CurrentTreeLevel;
int CurrentParent;
/////////////////////////////////////////////////////////////////////////////
// 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()

/////////////////////////////////////////////////////////////////////////////
// CEightNumWithAStarDlg dialog

CEightNumWithAStarDlg::CEightNumWithAStarDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CEightNumWithAStarDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CEightNumWithAStarDlg)
	m_num1 = 0;
	m_num2 = 1;
	m_num3 = 2;
	m_num4 = 3;
	m_num5 = 4;
	m_num6 = 5;
	m_num7 = 6;
	m_num8 = 7;
	m_num9 = 8;
	m_step = 0;
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CEightNumWithAStarDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CEightNumWithAStarDlg)
	DDX_Text(pDX, IDC_EDIT1, m_num1);
	DDV_MinMaxInt(pDX, m_num1, 0, 9);
	DDX_Text(pDX, IDC_EDIT2, m_num2);
	DDV_MinMaxInt(pDX, m_num2, 0, 9);
	DDX_Text(pDX, IDC_EDIT3, m_num3);
	DDV_MinMaxInt(pDX, m_num3, 0, 9);
	DDX_Text(pDX, IDC_EDIT4, m_num4);
	DDV_MinMaxInt(pDX, m_num4, 0, 9);
	DDX_Text(pDX, IDC_EDIT5, m_num5);
	DDV_MinMaxInt(pDX, m_num5, 0, 9);
	DDX_Text(pDX, IDC_EDIT6, m_num6);
	DDV_MinMaxInt(pDX, m_num6, 0, 9);
	DDX_Text(pDX, IDC_EDIT7, m_num7);
	DDV_MinMaxInt(pDX, m_num7, 0, 9);
	DDX_Text(pDX, IDC_EDIT8, m_num8);
	DDV_MinMaxInt(pDX, m_num8, 0, 9);
	DDX_Text(pDX, IDC_EDIT9, m_num9);
	DDV_MinMaxInt(pDX, m_num9, 0, 9);
	DDX_Text(pDX, IDC_STEP, m_step);
	DDV_MinMaxInt(pDX, m_step, 0, 10000);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CEightNumWithAStarDlg, CDialog)
	//{{AFX_MSG_MAP(CEightNumWithAStarDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDC_Search, OnSearch)
	ON_BN_CLICKED(IDC_yanshi, Onyanshi)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CEightNumWithAStarDlg message handlers

BOOL CEightNumWithAStarDlg::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
	
	return TRUE;  // return TRUE  unless you set the focus to a control
}

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

void CEightNumWithAStarDlg::OnSearch() 
{
	// TODO: Add your control notification handler code here
	UpdateData(); 
	long startstate,n; 
	bool f=false; 
	startstate=(m_num1+1)*100+(m_num2+1)*10+m_num3+1; 
	startstate=startstate*1000+(m_num4+1)*100+(m_num5+1)*10+m_num6+1; 
	startstate=startstate*1000+(m_num7+1)*100+(m_num8+1)*10+m_num9+1; 
	Original=startstate;//得到初态 
	n=startstate; 
	int m[10]; 
	for(int i=0;i<9;i++) 
	{m[i]=n%10; 
	n/=10; 
	} 
	for( i=0;i<9;i++)//判断添入的有没有重复数字 
		for( int j=i+1;j<9;j++) 
			if(m[i]==m[j]){MessageBox("初始状态有重复数字");return;} 
			
			Goal=123456789; 
			f=sousuo(); 
			if(!f){MessageBox("目标状态不可达,请调整数字顺序!","搜索失败！",MB_ICONINFORMATION);} 
			else {MessageBox("搜索成功,请按演示进行演示","A*算法搜索"); 
			CWnd *p; 
			p=GetDlgItem(IDC_yanshi); 
			p->EnableWindow(); } 

}

void CEightNumWithAStarDlg::Onyanshi() 
{
	// TODO: Add your control notification handler code here
//////////////////////////////////////////////////////////////////////////
PrintSolution(); 
//////////////////////////////////////////////////////////////////////////

}

int CEightNumWithAStarDlg::WhereIsDigitInNum(int digit, long num)
{
	bool found=false;
	int DigitFromNum,pos=9;
	while (!found && num) 
	{ 
		DigitFromNum=num%10; 
		if (digit==DigitFromNum) 
			found=true; 
		else 
		{ 
			pos--; 
			num/=10; 
		} 
	} 
	return pos; 

}


int CEightNumWithAStarDlg::CalcDistance(long org, long tar)
{

	int i,MSum=0,OrgPos,TarPos,OrgRow,TarRow,OrgLine,TarLine; 
	for (i=2; i<=9; i++) 
	{ 
		OrgPos=WhereIsDigitInNum(i,org); 
		TarPos=WhereIsDigitInNum(i,tar); 
		OrgLine=(OrgPos-1)/3; 
		TarLine=(TarPos-1)/3; 
		
		OrgRow=OrgPos%3; 
		if (OrgRow==0) 
			OrgRow=3; 
		
		TarRow=TarPos%3; 
		if (TarRow==0) 
			TarRow=3; 
		
		MSum+=abs(OrgLine-TarLine)+abs(OrgRow-TarRow); 
	}  
	return MSum; 

}

void CEightNumWithAStarDlg::ReturnSons(long num, long &sr, long &sl, long &su, long &sd)
{

	int SpacePos; 
	SpacePos=WhereIsDigitInNum(1,num); 
	
	// 空格右移 
	if (SpacePos%3==0) 
		sr=0; 
	else 
		sr=Swap(num,SpacePos,SpacePos+1); 
	
	// 空格左移 
	if (SpacePos%3==1) 
		sl=0; 
	else 
		sl=Swap(num,SpacePos,SpacePos-1); 
	
	// 空格上移 
	if (SpacePos<4) 
		su=0; 
	else 
		su=Swap(num,SpacePos,SpacePos-3); 
	
	// 空格下移 
	if (SpacePos>6) 
		sd=0; 
	else 
          sd=Swap(num,SpacePos,SpacePos+3); 
}

long CEightNumWithAStarDlg::Swap(long num, int a, int b)
{
	
	long v[10]; 
	int i, temp; 
	
	for (i=9; i>=1; i--) 
	{ 
		v[i]=num%10; 
		num/=10; 
	} 
	
	temp=v[a]; 
	v[a]=v[b]; 
	v[b]=temp; 
	
	num=0; 
	for (i=1; i<=9; i++) 
	{ 
		num*=10; 
		num+=v[i]; 
	} 
	
     return num; 
}


bool CEightNumWithAStarDlg::SolvePuzzle()
{
	
	long CurrentNum,s1,s2,s3,s4; 
	
	CurrentNum=Goal; 
	InsertToList(CurrentNum,0,0,0);    //插入到结点表中 
	while (CurrentNum!=Original && ListIndex<12000){ 
		CurrentNum=FindBest();    //返回估价值最小的结点           
		ReturnSons(CurrentNum, s1, s2, s3, s4);    //取子结点 
		InsertToList(s1, s2, s3, s4);    //将子结点插入结点表 
	} 
	
	if (CurrentNum!=Original) 
		return false; 
	else  
 return true; 
}



void CEightNumWithAStarDlg::InsertToList(long a, long b, long c, long d)
{

	long arr[4]; 
	int index=0, i; 
	bool found; 
	if (a) 
	{ 
		arr[index]=a; 
		index++; 
	} 
	if (b) 
	{ 
		arr[index]=b; 
		index++; 
	} 
	if (c)
	{ 
		arr[index]=c; 
		index++; 
	} 
	if (d) 
	{ 
		arr[index]=d; 
		index++; 
	} 
	index--; 
	while (index>=0)//的确有节点想插入 
	{ 
		found=false; 
		//在结点表中查找是否存在想要插入的节点 
		for (i=0;i<ListIndex;i++) 
			if(arr[index]==NodeList[i].Puzzle) 
			{found=true;break;} 
			
			// 没找到或找到但是CalcDistance值更小,则插入结点表, 
			// 对已存在的结点相当于重新计算估计值并扩展 
			if ( 
				found &&  
				( 
				(CurrentTreeLevel+1+CalcDistance(arr[index],Original))<NodeList[i].Val 
				) 
				
				|| (!found) 
				) 
			{ 
				NodeList[ListIndex].Puzzle=arr[index]; 
				NodeList[ListIndex].WasOpened=false; 
				NodeList[ListIndex].TreeLevel=CurrentTreeLevel+1; 
				NodeList[ListIndex].Val=NodeList[ListIndex].TreeLevel+CalcDistance(arr[index],Original); 
				NodeList[ListIndex].Parent=CurrentParent; 
				ListIndex++; 
			} 
			index--; 
	} 

}

long CEightNumWithAStarDlg::FindBest()
{
	
	int min, i, j, mini; 
	bool found=false; 
	// 先设置第一个未扩展结点的估价值为最小值 
	for (i=0;NodeList[i].WasOpened;i++); 
	{ 
		found=true; 
		min=NodeList[i].Val; 
		mini=i; 
	} 
	
	// 查找估计值最小的 
	for(j=i+1;j<ListIndex;j++) 
		if((NodeList[j].Val<=min) && (NodeList[j].WasOpened==false)) 
		{ 
			min=NodeList[j].Val; 
			mini=j; 
		} 
		
		NodeList[mini].WasOpened=true;    //将扩展该结点 
		CurrentTreeLevel=NodeList[mini].TreeLevel;    //设置当前层数 
		CurrentParent=mini;  
		
     return NodeList[mini].Puzzle; 
}


void CEightNumWithAStarDlg::PrintSolution()
{
	
	long num=CurrentParent; 
	CString s; 
    int StepCounts=0; 
    while (NodeList[num].Puzzle!=Goal) 
    {   
		xianshi(NodeList[num].Puzzle); 
		m_step=StepCounts++; 
		UpdateData(FALSE); 
		s.Format("演示第%d步移动！",StepCounts); 
		MessageBox(s); 
		num = NodeList[num].Parent; 
    } 
    xianshi(NodeList[num].Puzzle); 
    m_step=StepCounts; 
	UpdateData(FALSE); 
	s.Format("演示完毕，共%d步~！",m_step); 
   MessageBox(s); 
}


bool CEightNumWithAStarDlg::sousuo()
{
	
	ListIndex=0; 
	CurrentTreeLevel=-1;    //第一层为0  
	CurrentParent=0; 
    return SolvePuzzle();   
}



void CEightNumWithAStarDlg::xianshi(long Puzzle)
{
	
	long v[10]; 
    int i; 
	for (i=9;i>=1; i--) 
	{ 
        v[i]=Puzzle%10-1; 
        Puzzle/=10; 
	} 
	m_num1=v[1],m_num2=v[2],m_num3=v[3],m_num4=v[4]; 
	m_num5=v[5],m_num6=v[6],m_num7=v[7],m_num8=v[8]; 
	m_num9=v[9];//输出 

}