aihomeworkdlg.cpp

自己用VC编写的8数码问题求解程序

// AIHomeWorkDlg.cpp : implementation file
//

#include "stdafx.h"
#include "AIHomeWork.h"
#include "AIHomeWorkDlg.h"
#include "iostream.h"
#include <stdlib.h>
#include <time.h>
#include "About.h"
#include <string.h>

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

extern UINT idc[9]={IDC_EDIT0,IDC_EDIT1,IDC_EDIT2,IDC_EDIT3,
	IDC_EDIT4,IDC_EDIT5,IDC_EDIT6,IDC_EDIT7,IDC_EDIT8};
bool check=false;

/////////////////////////////////////////////////////////////////////////////
// CAIHomeWorkDlg dialog

CAIHomeWorkDlg::CAIHomeWorkDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CAIHomeWorkDlg::IDD, pParent)
{
	//shownode=tracknodes->next;//->next;

	//{{AFX_DATA_INIT(CAIHomeWorkDlg)
	m_Val0 = 0;
	m_Val1 = 0;
	m_Val2 = 0;
	m_Val3 = 0;
	m_Val4 = 0;
	m_Val5 = 0;
	m_Val6 = 0;
	m_Val7 = 0;
	m_Val8 = 0;
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDI_ICON1);
}

void CAIHomeWorkDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAIHomeWorkDlg)
	DDX_Control(pDX, IDC_INFO, m_list);
	DDX_Control(pDX, IDC_HIDEINFO, m_hideinfo);
	DDX_Control(pDX, IDC_EDIT8, m_Ctl8);
	DDX_Control(pDX, IDC_EDIT7, m_Ctl7);
	DDX_Control(pDX, IDC_EDIT6, m_Ctl6);
	DDX_Control(pDX, IDC_EDIT5, m_Ctl5);
	DDX_Control(pDX, IDC_EDIT4, m_Ctl4);
	DDX_Control(pDX, IDC_EDIT3, m_Ctl3);
	DDX_Control(pDX, IDC_EDIT2, m_Ctl2);
	DDX_Control(pDX, IDC_EDIT1, m_Ctl1);
	DDX_Control(pDX, IDC_EDIT0, m_Ctl0);
	DDX_Text(pDX, IDC_EDIT0, m_Val0);
	DDX_Text(pDX, IDC_EDIT1, m_Val1);
	DDX_Text(pDX, IDC_EDIT2, m_Val2);
	DDX_Text(pDX, IDC_EDIT3, m_Val3);
	DDX_Text(pDX, IDC_EDIT4, m_Val4);
	DDX_Text(pDX, IDC_EDIT5, m_Val5);
	DDX_Text(pDX, IDC_EDIT6, m_Val6);
	DDX_Text(pDX, IDC_EDIT7, m_Val7);
	DDX_Text(pDX, IDC_EDIT8, m_Val8);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAIHomeWorkDlg, CDialog)
	//{{AFX_MSG_MAP(CAIHomeWorkDlg)
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDC_CONFORM, OnConform)
	ON_BN_CLICKED(IDC_HIDEINFO, OnHideinfo)
	ON_BN_CLICKED(IDC_RANDOM, OnRandom)
	ON_BN_CLICKED(IDC_RUN, OnRun)
	ON_BN_CLICKED(IDC_SHOW, OnShow)
	ON_BN_CLICKED(IDC_ABOUT, OnAbout)
	ON_LBN_DBLCLK(IDC_INFO, OnDblclkInfo)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CAIHomeWorkDlg message handlers
CString change(int n)
{
	switch(n)
	{
	case 0:
		return "0";
	case 1:
		return "1";
	case 2:
		return "2";
	case 3:
		return "3";
	case 4:
		return "4";
	case 5:
		return "5";
	case 6:
		return "6";
	case 7:
		return "7";
	case 8:
		return "8";
	case 9:
		return "9";
	default:
		return "0";
	}
}

int antichange(char n)
{
	switch(n)
	{
	case '0':
		return 0;
	case '1':
		return 1;
	case '2':
		return 2;
	case '3':
		return 3;
	case '4':
		return 4;
	case '5':
		return 5;
	case '6':
		return 6;
	case '7':
		return 7;
	case '8':
		return 8;
	case '9':
		return 9;
	default:
		return 0;
	}
}

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

	m_bMax = false;
	CRect rc;
	GetWindowRect(&rc);
	rc.bottom -= 150;
	MoveWindow(&rc);

	GetDlgItem(IDC_EDIT0)->GetWindowRect(&m_Rect0);
	GetDlgItem(IDC_EDIT1)->GetWindowRect(&m_Rect1);
	GetDlgItem(IDC_EDIT2)->GetWindowRect(&m_Rect2);
	GetDlgItem(IDC_EDIT3)->GetWindowRect(&m_Rect3);
	GetDlgItem(IDC_EDIT4)->GetWindowRect(&m_Rect4);
	GetDlgItem(IDC_EDIT5)->GetWindowRect(&m_Rect5);
	GetDlgItem(IDC_EDIT6)->GetWindowRect(&m_Rect6);
	GetDlgItem(IDC_EDIT7)->GetWindowRect(&m_Rect7);
	GetDlgItem(IDC_EDIT8)->GetWindowRect(&m_Rect8);
	
	ScreenToClient(&m_Rect0);
	ScreenToClient(&m_Rect1);
	ScreenToClient(&m_Rect2);
	ScreenToClient(&m_Rect3);
	ScreenToClient(&m_Rect4);
	ScreenToClient(&m_Rect5);
	ScreenToClient(&m_Rect6);
	ScreenToClient(&m_Rect7);
	ScreenToClient(&m_Rect8);

	m_list.AddString("{0,1,2,3,4,5,6,7,8}");
	m_list.AddString("{1,0,2,3,4,5,6,7,8}");
	m_list.AddString("{1,2,0,3,4,5,6,7,8}");
	m_list.AddString("{1,2,3,0,4,5,6,7,8}");
	m_list.AddString("{1,2,3,4,0,5,6,7,8}");
	m_list.AddString("{1,2,3,4,5,0,6,7,8}");
	m_list.AddString("{1,2,3,4,5,6,0,7,8}");
	m_list.AddString("{1,2,3,4,5,6,7,0,8}");
	m_list.AddString("{1,2,3,4,5,6,7,8,0}");
	m_list.AddString("{8,1,3,4,5,6,7,0,2}");
	m_list.AddString("{1,3,4,0,5,6,7,8,2}");
	m_list.AddString("{1,2,3,5,6,0,7,8,4}");
	m_list.AddString("{1,2,3,4,5,0,6,7,8}");
	m_list.AddString("{1,0,2,3,4,5,7,8,6}");
	m_list.AddString("{1,3,0,4,5,6,7,8,2}");
	m_list.AddString("{1,2,3,5,0,6,7,8,4}");
	m_list.AddString("{0,1,3,4,5,6,7,8,2}");

	// 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
	((CButton *)GetDlgItem(IDC_RUN))->EnableWindow(false);
	((CButton *)GetDlgItem(IDC_SHOW))->EnableWindow(false);
	//((CButton *)GetDlgItem(IDC_SHOW))->EnableWindow(false);
	
	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 CAIHomeWorkDlg::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
	{
	///*
		CPaintDC dc(this);
		COLORREF YELLOW=RGB(255,255,0);
		COLORREF BLUE=RGB(255,0,255);
		CBrush YelloBrush(YELLOW);	//黄画刷
		CBrush BlueBrush(BLUE);	    //蓝画刷
		dc.SetBkColor(YELLOW);
	
		int x,y;
		CString show;

		//10--"10"
		if(Sk[0]!=0)
		{
			dc.FillRect(&m_Rect0,&YelloBrush);
			x=m_Rect0.CenterPoint().x;
			y=m_Rect0.CenterPoint().y;
			show=change((Sk[0]));
			dc.TextOut(x-5,y-5,show);
		}
		else
			dc.FillRect(&m_Rect0,&BlueBrush);

		if(Sk[1]!=0)
		{
			dc.FillRect(&m_Rect1,&YelloBrush);
			x=m_Rect1.CenterPoint().x;
			y=m_Rect1.CenterPoint().y;
			show=change(Sk[1]);
			dc.TextOut(x-5,y-5,show);
		}
		else
			dc.FillRect(&m_Rect1,&BlueBrush);

		if(Sk[2]!=0)
		{
			dc.FillRect(&m_Rect2,&YelloBrush);
			x=m_Rect2.CenterPoint().x;
			y=m_Rect2.CenterPoint().y;
			show=change(Sk[2]);
			dc.TextOut(x-5,y-5,show);
		}
		else
			dc.FillRect(&m_Rect2,&BlueBrush);

		if(Sk[3]!=0)
		{
			dc.FillRect(&m_Rect3,&YelloBrush);
			x=m_Rect3.CenterPoint().x;
			y=m_Rect3.CenterPoint().y;
			show=change(Sk[3]);
			dc.TextOut(x-5,y-5,show);
		}
		else
			dc.FillRect(&m_Rect3,&BlueBrush);

		if(Sk[4]!=0)
		{
			dc.FillRect(&m_Rect4,&YelloBrush);
			x=m_Rect4.CenterPoint().x;
			y=m_Rect4.CenterPoint().y;
			show=change(Sk[4]);
			dc.TextOut(x-5,y-5,show);
		}
		else
			dc.FillRect(&m_Rect4,&BlueBrush);

		if(Sk[5]!=0)
		{
			dc.FillRect(&m_Rect5,&YelloBrush);
			x=m_Rect5.CenterPoint().x;
			y=m_Rect5.CenterPoint().y;
			show=change(Sk[5]);
			dc.TextOut(x-5,y-5,show);
		}
		else
			dc.FillRect(&m_Rect5,&BlueBrush);

		if(Sk[6]!=0)
		{
			dc.FillRect(&m_Rect6,&YelloBrush);
			x=m_Rect6.CenterPoint().x;
			y=m_Rect6.CenterPoint().y;
			show=change(Sk[6]);
			dc.TextOut(x-5,y-5,show);
		}
		else
			dc.FillRect(&m_Rect6,&BlueBrush);

		if(Sk[7]!=0)
		{
			dc.FillRect(&m_Rect7,&YelloBrush);
			x=m_Rect7.CenterPoint().x;
			y=m_Rect7.CenterPoint().y;
			show=change(Sk[7]);
			dc.TextOut(x-5,y-5,show);
		}
		else
			dc.FillRect(&m_Rect7,&BlueBrush);

		if(Sk[8]!=0)
		{
			dc.FillRect(&m_Rect8,&YelloBrush);
			x=m_Rect8.CenterPoint().x;
			y=m_Rect8.CenterPoint().y;
			show=change(Sk[8]);
			dc.TextOut(x-5,y-5,show);
		}
		else
			dc.FillRect(&m_Rect8,&BlueBrush);
	
		dc.MoveTo(m_Rect0.left,m_Rect0.top);
		dc.LineTo(m_Rect6.left,m_Rect6.bottom);
		dc.MoveTo(m_Rect1.left,m_Rect1.top);
		dc.LineTo(m_Rect5.left,m_Rect5.bottom);
		dc.MoveTo(m_Rect2.left,m_Rect2.top);
		dc.LineTo(m_Rect4.left,m_Rect4.bottom);
		dc.MoveTo(m_Rect2.right,m_Rect2.top);
		dc.LineTo(m_Rect4.right,m_Rect4.bottom);

		dc.MoveTo(m_Rect0.left,m_Rect0.top);
		dc.LineTo(m_Rect2.right,m_Rect2.top);
		dc.MoveTo(m_Rect7.left,m_Rect7.top);
		dc.LineTo(m_Rect3.right,m_Rect3.top);
		dc.MoveTo(m_Rect6.left,m_Rect6.top);
		dc.LineTo(m_Rect4.right,m_Rect4.top);
		dc.MoveTo(m_Rect6.left,m_Rect6.bottom);
		dc.LineTo(m_Rect4.right,m_Rect4.bottom);
	//*/
		//CDialog::OnPaint();
	
	}
}

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

void CAIHomeWorkDlg::OnConform() 
{
	// TODO: Add your control notification handler code here
	int i,j;
	for(i=0;i<=8;i++)
		S0[i]=GetDlgItemInt(idc[i]);

	for(i=0;i<=8;i++)
		for(j=0;j<=8;j++)
		{
			if(j!=i&&S0[i]==S0[j])
			{
				AfxMessageBox("你输入的9个数有错误!");
				return;
			}
		}

	for(i=0;i<=8;i++)
		((CEdit *)GetDlgItem(idc[i]))->ShowWindow(false);

	((CButton *)GetDlgItem(IDC_RANDOM))->EnableWindow(false);
	((CButton *)GetDlgItem(IDC_CONFORM))->EnableWindow(false);
	((CButton *)GetDlgItem(IDC_RUN))->EnableWindow(true);

	for(i=0;i<=8;i++)
		Sk[i]=S0[i];
	
	CClientDC dc(this);
	COLORREF color1=RGB(255,255,0);
	COLORREF color0=RGB(255,0,255);
	CBrush brush1(color1);
	CBrush brush0(color0);
	
	int x,y;
	CString show;

	if(S0[0]!=0)
	{
		dc.FillRect(&m_Rect0,&brush1);
		x=m_Rect0.CenterPoint().x;
		y=m_Rect0.CenterPoint().y;
		show=change(S0[0]);
		dc.TextOut(x-5,y-5,show);
	}
	else
		dc.FillRect(&m_Rect0,&brush0);

	if(S0[1]!=0)
	{
		dc.FillRect(&m_Rect1,&brush1);
		x=m_Rect1.CenterPoint().x;
		y=m_Rect1.CenterPoint().y;
		show=change(S0[1]);
		dc.TextOut(x-5,y-5,show);
	}
	else
		dc.FillRect(&m_Rect1,&brush0);

	if(S0[2]!=0)
	{
		dc.FillRect(&m_Rect2,&brush1);
		x=m_Rect2.CenterPoint().x;
		y=m_Rect2.CenterPoint().y;
		show=change(S0[2]);
		dc.TextOut(x-5,y-5,show);
	}
	else
		dc.FillRect(&m_Rect2,&brush0);

	if(S0[3]!=0)
	{
		dc.FillRect(&m_Rect3,&brush1);
		x=m_Rect3.CenterPoint().x;
		y=m_Rect3.CenterPoint().y;
		show=change(S0[3]);
		dc.TextOut(x-5,y-5,show);
	}
	else
		dc.FillRect(&m_Rect3,&brush0);

	if(S0[4]!=0)
	{
		dc.FillRect(&m_Rect4,&brush1);
		x=m_Rect4.CenterPoint().x;
		y=m_Rect4.CenterPoint().y;
		show=change(S0[4]);
		dc.TextOut(x-5,y-5,show);
	}
	else
		dc.FillRect(&m_Rect4,&brush0);

	if(S0[5]!=0)
	{
		dc.FillRect(&m_Rect5,&brush1);
		x=m_Rect5.CenterPoint().x;
		y=m_Rect5.CenterPoint().y;
		show=change(S0[5]);
		dc.TextOut(x-5,y-5,show);
	}
	else
		dc.FillRect(&m_Rect5,&brush0);

	if(S0[6]!=0)
	{
		dc.FillRect(&m_Rect6,&brush1);
		x=m_Rect6.CenterPoint().x;
		y=m_Rect6.CenterPoint().y;
		show=change(S0[6]);
		dc.TextOut(x-5,y-5,show);
	}
	else
		dc.FillRect(&m_Rect6,&brush0);

	if(S0[7]!=0)
	{
		dc.FillRect(&m_Rect7,&brush1);
		x=m_Rect7.CenterPoint().x;
		y=m_Rect7.CenterPoint().y;
		show=change(S0[7]);
		dc.TextOut(x-5,y-5,show);
	}
	else
		dc.FillRect(&m_Rect7,&brush0);

	if(S0[8]!=0)
	{
		dc.FillRect(&m_Rect8,&brush1);
		x=m_Rect8.CenterPoint().x;
		y=m_Rect8.CenterPoint().y;
		show=change(S0[8]);
		dc.TextOut(x-5,y-5,show);
	}
	else
		dc.FillRect(&m_Rect8,&brush0);
	
	dc.MoveTo(m_Rect0.left,m_Rect0.top);
	dc.LineTo(m_Rect6.left,m_Rect6.bottom);
	dc.MoveTo(m_Rect1.left,m_Rect1.top);
	dc.LineTo(m_Rect5.left,m_Rect5.bottom);
	dc.MoveTo(m_Rect2.left,m_Rect2.top);
	dc.LineTo(m_Rect4.left,m_Rect4.bottom);
	dc.MoveTo(m_Rect2.right,m_Rect2.top);
	dc.LineTo(m_Rect4.right,m_Rect4.bottom);

	dc.MoveTo(m_Rect0.left,m_Rect0.top);
	dc.LineTo(m_Rect2.right,m_Rect2.top);
	dc.MoveTo(m_Rect7.left,m_Rect7.top);
	dc.LineTo(m_Rect3.right,m_Rect3.top);
	dc.MoveTo(m_Rect6.left,m_Rect6.top);
	dc.LineTo(m_Rect4.right,m_Rect4.top);
	dc.MoveTo(m_Rect6.left,m_Rect6.bottom);
	dc.LineTo(m_Rect4.right,m_Rect4.bottom);

	SetDlgItemText(IDC_SHOWINFO,"    按“开始运行”键开始搜索目标状态!");
	SetDlgItemText(IDC_RUN,"开始运行");
}

void CAIHomeWorkDlg::OnHideinfo() 
{
	// TODO: Add your control notification handler code here
	CButton* pbMore = (CButton*)GetDlgItem(IDC_HIDEINFO);
	CRect rc;
	GetWindowRect(&rc);
	if(m_bMax)
	{
		for (int i= 0; i < 150; i+=2)
		{
			rc.bottom-=2;
			//::Sleep(5);
			MoveWindow(&rc);
		}
	}
	else
	{
		for (int i= 0; i < 150; i++)
		{
			rc.bottom++;
			//::Sleep(5);
			MoveWindow(&rc);
		}
	}
	m_bMax = !m_bMax;
	pbMore->SetFocus();
}

void setvalue(int a[num],int b[num])
{
	int i;
	for(i=0;i<=num-1;i++)
		a[i]=b[i];
}

void CAIHomeWorkDlg::OnRandom() 
{
	// TODO: Add your control notification handler code here

	//产生伪随机数
	int statusset[20][10]=
	{{0,1,2,3,4,5,6,7,8},
	{1,0,2,3,4,5,6,7,8},
	{1,2,0,3,4,5,6,7,8},
	{1,2,3,0,4,5,6,7,8},
	{1,2,3,4,0,5,6,7,8},  //25
	{1,2,3,4,5,0,6,7,8},
	{1,2,3,4,5,6,0,7,8},
	{1,2,3,4,5,6,7,0,8},
	{8,1,3,4,5,6,7,0,2},  //11,4--1
	{1,3,4,0,5,6,7,8,2},  //11,4--3
	{1,2,3,5,6,0,7,8,4},  //11,4--5
	{1,2,3,4,5,0,6,7,8},  //13,4--7
	{1,3,0,4,5,6,7,8,2},  //5
	{1,0,2,3,4,5,7,8,6},  //43
	{1,2,3,5,0,6,7,8,4},  //5,3
	{0,1,3,4,5,6,7,8,2},  //5,3
	{0,1,2,3,4,5,6,7,8},
	{0,1,2,3,4,5,6,7,8},
	{0,1,2,3,4,5,6,7,8},
	{0,1,2,3,4,5,6,7,8}};
	
	int i;
	srand( (unsigned)time(NULL));
	i=rand()%20;
	setvalue(S0,statusset[i]);
/*
	//产生真正的随机数
	int i,j;
	int zerop,genp;

	srand( (unsigned)time(NULL));

	zerop=(rand()%10)%9;  //数0所在的位置
	S0[zerop]=0;

	for(i=0;i<=num-1;i++)
	{
		if(i==zerop) 
		{
			continue;
		}
		
		//把i==0单独列出来，是因为后面的while子句中不能判断i==0的情景
		genp=(rand()%10)%9;
		while(genp==0)
			genp=(rand()%10)%9;
		if(i==0)
		{
			S0[i]=genp;
			continue;
		}
	
		j=-1;
		while(j<i)   //i从1开始
		{
			genp=(rand()%10)%9;
			if(genp==0) continue;
			for(j=0;j<=i-1;j++)
			{
				if(genp==S0[j]) break;
			}
		}
		S0[i]=genp;
	}
*/
	for(i=0;i<=num-1;i++)
		SetDlgItemInt(idc[i],S0[i]);
}

bool issame(int a[num],int b[num])
{
	int i;
	for(i=0;i<=num-1;i++)
	{
		if(a[i]!=b[i]) break;
	}
	if(i==num) return true;
	else return false;
}

bool isexist(node *h,int S[num])
{
	node *temp;
	temp=h->next;
	while(temp!=NULL)
	{
		if(issame(temp->Sk,S))
			return true;
		temp=temp->next;    //重要!为什么漏了?
	}
	return false;
}

int testpt(int a[num],int n)
{
	for(int i=0;i<=num-1;i++)
		if(a[i]==n) return i;   //致命错误:a[i]=0
	return -1;
}

void converse(node * tracknodes)
{
	node *p,*q;
	p=tracknodes->next;
	tracknodes->next=NULL;
	while(p!=NULL)
	{
		q=p;
		p=p->next;
		q->next=tracknodes->next;
		tracknodes->next=q;
	}
}

void search(node ** completenodes,node **tracknodes,int S0[num])
{
	node *a,*b;
	*completenodes=(node *)malloc(sizeof(node)); //头节点
	*tracknodes=(node *)malloc(sizeof(node));  //头节点
	a=(*completenodes);
	b=(*tracknodes);
	b->next=NULL;

	int count=0;
	int tracknodesum=0;
	int i=0;
	
	//把S0放入completenodes表中
	a->next=(node *)malloc(sizeof(node));
	setvalue(a->next->Sk,S0);