eightnumsearchdlg.cpp

一个8数码问题的解法

		base[n+1].matrix[1][1]=base[n+1].matrix[0][1];
		base[n+1].matrix[0][1]=a;
		base[n+1].x=0;
        base[n+1].y=1;
	    base[n+1].d=base[m].d+1;
		n=n+1;
        match(n);
		getf(n);

		base[n+1]=base[m];
		a=base[n+1].matrix[1][1];
		base[n+1].matrix[1][1]=base[n+1].matrix[1][2];
		base[n+1].matrix[1][2]=a;
		base[n+1].x=1;
        base[n+1].y=2;
	    base[n+1].d=base[m].d+1;
		n=n+1;
		match(n);
		getf(n);

		base[n+1]=base[m];
		a=base[n+1].matrix[1][1];
		base[n+1].matrix[1][1]=base[n+1].matrix[2][1];
		base[n+1].matrix[2][1]=a;
		base[n+1].x=2;
        base[n+1].y=1;
	    base[n+1].d=base[m].d+1;
		n=n+1;
		match(n);
		getf(n);

		base[n+1]=base[m];
		a=base[n+1].matrix[1][1];
		base[n+1].matrix[1][1]=base[n+1].matrix[1][0];
		base[n+1].matrix[1][0]=a;
		base[n+1].x=1;
        base[n+1].y=0;
	    base[n+1].d=base[m].d+1;
		n=n+1;
		match(n);
		getf(n);
		break;
	case 5://空格位于[1][2]，有三种移动，并获得移动后空格的位置及估价函数f值
		base[n+1]=base[m];
		a=base[n+1].matrix[1][2];
		base[n+1].matrix[1][2]=base[n+1].matrix[0][2];
		base[n+1].matrix[0][2]=a;
		base[n+1].x=0;
        base[n+1].y=2;
	    base[n+1].d=base[m].d+1;
		n=n+1;
        match(n);
		getf(n);

		base[n+1]=base[m];
		a=base[n+1].matrix[1][2];
		base[n+1].matrix[1][2]=base[n+1].matrix[2][2];
		base[n+1].matrix[2][2]=a;
		base[n+1].x=2;
        base[n+1].y=2;
	    base[n+1].d=base[m].d+1;
		n=n+1;
		match(n);
		getf(n);

		base[n+1]=base[m];
		a=base[n+1].matrix[1][2];
		base[n+1].matrix[1][2]=base[n+1].matrix[1][1];
		base[n+1].matrix[1][1]=a;
		base[n+1].x=1;
        base[n+1].y=1;
	    base[n+1].d=base[m].d+1;
		n=n+1;
		match(n);
		getf(n);
		break;
	case 6://空格位于[2][0]，有两种移动，并获得移动后空格的位置及估价函数f值
		base[n+1]=base[m];
		a=base[n+1].matrix[2][0];
		base[n+1].matrix[2][0]=base[n+1].matrix[1][0];
		base[n+1].matrix[1][0]=a;
		base[n+1].x=1;
        base[n+1].y=0;
	    base[n+1].d=base[m].d+1;
		n=n+1;
        match(n);
		getf(n);

		base[n+1]=base[m];
		a=base[n+1].matrix[2][0];
		base[n+1].matrix[2][0]=base[n+1].matrix[2][1];
		base[n+1].matrix[2][1]=a;
		base[n+1].x=2;
        base[n+1].y=1;
	    base[n+1].d=base[m].d+1;
		n=n+1;
		match(n);
		getf(n);
		break;
	case 7://空格位于[2][1]，有三种移动，并获得移动后空格的位置及估价函数f值
		base[n+1]=base[m];
		a=base[n+1].matrix[2][1];
		base[n+1].matrix[2][1]=base[n+1].matrix[1][1];
		base[n+1].matrix[1][1]=a;
		base[n+1].x=1;
        base[n+1].y=1;
	    base[n+1].d=base[m].d+1;
		n=n+1;
        match(n);
		getf(n);

		base[n+1]=base[m];
		a=base[n+1].matrix[2][1];
		base[n+1].matrix[2][1]=base[n+1].matrix[2][2];
		base[n+1].matrix[2][2]=a;
		base[n+1].x=2;
        base[n+1].y=2;
	    base[n+1].d=base[m].d+1;
		n=n+1;
		match(n);
		getf(n);

		base[n+1]=base[m];
		a=base[n+1].matrix[2][1];
		base[n+1].matrix[2][1]=base[n+1].matrix[2][0];
		base[n+1].matrix[2][0]=a;
		base[n+1].x=2;
        base[n+1].y=0;
	    base[n+1].d=base[m].d+1;
		n=n+1;
		match(n);
		getf(n);
		break;
	case 8://空格位于[2][2]，有两种移动，并获得移动后空格的位置及估价函数f值
		base[n+1]=base[m];
		a=base[n+1].matrix[2][2];
		base[n+1].matrix[2][2]=base[n+1].matrix[1][2];
		base[n+1].matrix[1][2]=a;
		base[n+1].x=1;
        base[n+1].y=2;
	    base[n+1].d=base[m].d+1;
		n=n+1;
        match(n);
		getf(n);
		base[n+1]=base[m];
		a=base[n+1].matrix[2][2];
		base[n+1].matrix[2][2]=base[n+1].matrix[2][1];
		base[n+1].matrix[2][1]=a;
		base[n+1].x=2;
        base[n+1].y=1;
	    base[n+1].d=base[m].d+1;
		n=n+1;
		match(n);
		getf(n);
		break;
	default:
		AfxMessageBox("输入错误");
		}
		m=m+1;
        paixu(n,m);
		//新节点里没有目标节点
		if(!flat)
		{
			for(i=0;i<m-1;i++)
			{
				h=0;
				for(k=0;k<3;k++)
					for(j=0;j<3;j++)
					{
						if(base[m-1].matrix[k][j]==base[i].matrix[k][j])
						{
							h=h+1;
						}
					}
					
				if(h==9)//如果路径上已经出现过相同节点,换个节点,本次不累计
				{   
					q=base[m-1];
					base[m-1]=base[m];
					base[m]=q;
					m=m-1;
					break;
				
				}
			}
		}
		
}

void CEightNumSearchDlg::OnSolute() 
{
	// TODO: Add your control notification handler code here
	if(flat)
	{
		int nDlg=::MessageBox(NULL,"已经计算完毕,是否重新计算?","提示",MB_YESNO);
		if(nDlg==IDNO)return;
	}
	flat=false;
	n=0;m=0;
	UpdateData();
	char a[3][3],b[3][3],c[2];
	DWORD StarID1=IDC_COM1_EDIT1;
	DWORD StarID2=IDC_COM2_EDIT1;
	CWnd *pWnd;
	CString str;
	int i,j,x=0,y=0;
	for(i=0;i<3;i++)
	{
		for(j=0;j<3;j++)
		{
			pWnd=(CWnd *)GetDlgItem(StarID1+3*i+j);
			pWnd->GetWindowText(str);
			strcpy(c,str);
			if(str==_T("0")||str==_T(""))
			{
				x=i;y=j;
				c[0]=' ';
			}
			//if(c[0]=='0')c[0]=' ';
			a[i][j]=c[0];
		}
	}
	/*str.Format("%d,%d",x,y);
	AfxMessageBox(str);
	str.Format("%c",a[x][y]);
	AfxMessageBox(str);*/
	for(i=0;i<3;i++)
	{
		for(j=0;j<3;j++)
		{
			pWnd=(CWnd *)GetDlgItem(StarID2+3*i+j);
			pWnd->GetWindowText(str);
			strcpy(c,str);
			if(str==_T("0")||str==_T(""))
				c[0]=' ';
			//if(c[0]=='0')c[0]=' ';
			b[i][j]=c[0];
		}
	}
	for(i=0;i<3;i++)
	{
		for(j=0;j<3;j++)
		{
			start[i][j]=a[i][j];
			end[i][j]=b[i][j];
			base[0].matrix[i][j]=start[i][j];
		}
	}
	base[0].w=0;
	base[0].x=x;
	base[0].y=y;
	match(n);
	findkg(n);
	getf(n);
	while(!flat)
	{
		if(n<SearchNum)
			kong(m,base[m].x,base[m].y,n);
		else
		{
			AfxMessageBox("此问题无解!");
			return;
		}
	}
	curstep=0;
	str.Format("最佳路线共%d步\n",m);
	str="搜索完毕,"+str+"按下一步浏览";
	AfxMessageBox(str);
	m_NextStep.EnableWindow(flat);
}

void CEightNumSearchDlg::OnNextstep() 
{
	// TODO: Add your control notification handler code here
	int k,j;
	DWORD StarID1=IDC_COM1_EDIT1;
	CWnd *pWnd;
	CString str;
	curstep++;
	if(curstep<=m)
	{
		for(k=0;k<3;k++)
		{
			for(j=0;j<3;j++)
			{
				pWnd=(CWnd *)GetDlgItem(StarID1+3*k+j);
				str.Format("%c",base[curstep].matrix[k][j]);
				pWnd->SetWindowText(str);
			}
		}
		m_ForthStep.EnableWindow(true);
	}
	else
	{
		//AfxMessageBox("已到目标节点");
		m_NextStep.EnableWindow(false);
	}
}

void CEightNumSearchDlg::OnForthstep() 
{
	// TODO: Add your control notification handler code here
	curstep--;
	int k,j;
	DWORD StarID1=IDC_COM1_EDIT1;
	CWnd *pWnd;
	CString str;
	if(curstep>=0)
	{
		for(k=0;k<3;k++)
		{
			for(j=0;j<3;j++)
			{
				pWnd=(CWnd *)GetDlgItem(StarID1+3*k+j);
				str.Format("%c",base[curstep].matrix[k][j]);
				pWnd->SetWindowText(str);
			}
		}
		if(!m_NextStep.GetState())m_NextStep.EnableWindow(true);
	}
	else
	{
		curstep++;
		m_ForthStep.EnableWindow(false);
	}
}

void CEightNumSearchDlg::OnInputoral() 
{
	// TODO: Add your control notification handler code here
	char a[9];
	int num;
	DWORD StarID=IDC_COM1_EDIT1;
	CWnd *pWnd;
	CString str;
	num=FileReadchar("",a);
	if(num<=0)return;
	if(num!=9){AfxMessageBox("输入的文件错误");return;}
	for(int i=0;i<num;i++)
	{
		pWnd=(CWnd *)GetDlgItem(StarID+i);
		str.Format("%c",a[i]);
		pWnd->SetWindowText(str);
	}
}

void CEightNumSearchDlg::OnInputobj() 
{
	// TODO: Add your control notification handler code here
	char a[9];
	int num;
	DWORD StarID=IDC_COM2_EDIT1;
	CWnd *pWnd;
	CString str;
	num=FileReadchar("",a);
	if(num<=0)return;
	if(num!=9){AfxMessageBox("输入的文件错误");return;}
	for(int i=0;i<num;i++)
	{
		pWnd=(CWnd *)GetDlgItem(StarID+i);
		str.Format("%c",a[i]);
		pWnd->SetWindowText(str);
	}
}
int CEightNumSearchDlg::FileReadchar(CString FileName,char a[])
{
	int Num;
	CFileDialog dlg(TRUE,NULL,"*.txt",OFN_FILEMUSTEXIST|OFN_PATHMUSTEXIST,  
	"Text files (*.txt)\0*.txt\0");
	if(dlg.DoModal()==IDOK)
	{
		FILE *fp=fopen(dlg.GetPathName(),"rt");	//打开用户选中的文件
		if(fp==NULL)
		{
			fclose(fp);
			fp=NULL;
			return 0;
		}
		Num=0;
		while(!feof(fp))
		{
			if(Num>9)return(Num);
			fscanf(fp,"%c ",&a[Num]);
			Num++;
		}
		return (Num);
	}
	else return (0);
	
}