aihomeworkdlg.cpp

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

	a->next->last=-1;    //-1
	a->next->next=NULL;
	a->next->parent=NULL;

	node *temp,*lastnode;
	temp=(*completenodes);
	lastnode=temp->next;
	temp=temp->next;

	int test[num],checklast; //checklast表示上一次0的位置
	int St[num]={1,2,3,4,5,6,7,8,0};

	while(true)
	{
		checklast=temp->last;
		setvalue(test,temp->Sk);

		if(issame(test,St))
		{
			count++;
			//AfxMessageBox("运行完毕"+change(count-5));
			break;
			//return;
		}
		else
		{
			count++;
		}
	
		i=0;
		int zp;
		zp=testpt(test,0);

		int childs[4][num+1];
		int childsum=0;

		for(int j=0;j<=3;j++)
		{
			for(i=0;i<=num-1;i++)
				childs[j][i]=test[i];
			childs[j][num]=-2;  //-1表示初态
		}

		switch(zp)
		{
			int change;
		case 0:
			if(checklast==-1)   //初态
			{
				change=childs[0][1];
				childs[0][1]=childs[0][0];
				childs[0][0]=change;
				childs[0][num]=0;

				change=childs[1][7];
				childs[1][7]=childs[1][0];
				childs[1][0]=change;
				childs[1][num]=0;

				childsum=2;
				childs[2][0]=childs[3][0]=-1;
			}
			else if(checklast==1)
			{
				change=childs[0][7];
				childs[0][7]=childs[0][0];
				childs[0][0]=change;
				childs[0][num]=0;

				childsum=1;
				childs[1][0]=childs[2][0]=childs[3][0]=-1;
			}
			else if(checklast==7)
			{
				change=childs[0][1];
				childs[0][1]=childs[0][0];
				childs[0][0]=change;
				childs[0][num]=0;

				childsum=1;
				childs[1][0]=childs[2][0]=childs[3][0]=-1;
			}
			break;
		case 1:
			if(checklast==-1)   //初态   
			{
				change=childs[0][0];
				childs[0][0]=childs[0][1];
				childs[0][1]=change;
				childs[0][num]=1;

				change=childs[1][2];
				childs[1][2]=childs[1][1];
				childs[1][1]=change;
				childs[1][num]=1;

				change=childs[2][8];
				childs[2][8]=childs[2][1];
				childs[2][1]=change;
				childs[2][num]=1;

				childsum=3;
				childs[3][0]=-1;
			}
			else if(checklast==0)
			{
				change=childs[0][2];
				childs[0][2]=childs[0][1];
				childs[0][1]=change;
				childs[0][num]=1;

				change=childs[1][8];
				childs[1][8]=childs[1][1];
				childs[1][1]=change;
				childs[1][num]=1;

				childsum=2;
				childs[2][0]=childs[3][0]=-1;
			}
			else if(checklast==2)
			{
				change=childs[0][0];
				childs[0][0]=childs[0][1];
				childs[0][1]=change;
				childs[0][num]=1;

				change=childs[1][8];
				childs[1][8]=childs[1][1];
				childs[1][1]=change;
				childs[1][num]=1;

				childsum=2;
				childs[2][0]=childs[3][0]=-1;
			}
			else if(checklast==8)
			{
				change=childs[0][0];
				childs[0][0]=childs[0][1];
				childs[0][1]=change;
				childs[0][num]=1;

				change=childs[1][2];
				childs[1][2]=childs[1][1];
				childs[1][1]=change;
				childs[1][num]=1;

				childsum=2;
				childs[2][0]=childs[3][0]=-1;
			}
			break;
		case 2:
			if(checklast==-1)   //初态
			{
				change=childs[0][1];
				childs[0][1]=childs[0][2];
				childs[0][2]=change;
				childs[0][num]=2;

				change=childs[1][3];
				childs[1][3]=childs[1][2];
				childs[1][2]=change;
				childs[1][num]=2;

				childsum=2;
				childs[2][0]=childs[3][0]=-1;
			}
			else if(checklast==1)
			{
				change=childs[0][3];
				childs[0][3]=childs[0][2];
				childs[0][2]=change;
				childs[0][num]=2;

				childsum=1;
				childs[1][0]=childs[2][0]=childs[3][0]=-1;
			}
			else if(checklast==3)
			{
				change=childs[0][1];
				childs[0][1]=childs[0][2];
				childs[0][2]=change;
				childs[0][num]=2;

				childsum=1;
				childs[1][0]=childs[2][0]=childs[3][0]=-1;
			}
			break;
		case 3:
			if(checklast==-1)   //初态   
			{
				change=childs[0][2];
				childs[0][2]=childs[0][3];
				childs[0][3]=change;
				childs[0][num]=3;

				change=childs[1][4];
				childs[1][4]=childs[1][3];
				childs[1][3]=change;
				childs[1][num]=3;

				change=childs[2][8];
				childs[2][8]=childs[2][3];
				childs[2][3]=change;
				childs[2][num]=3;

				childsum=3;
				childs[3][0]=-1;
			}
			else if(checklast==2)
			{
				change=childs[0][4];
				childs[0][4]=childs[0][3];
				childs[0][3]=change;
				childs[0][num]=3;

				change=childs[1][8];
				childs[1][8]=childs[1][3];
				childs[1][3]=change;
				childs[1][num]=3;

				childsum=2;
				childs[2][0]=childs[3][0]=-1;
			}
			else if(checklast==4)
			{
				change=childs[0][2];
				childs[0][2]=childs[0][3];
				childs[0][3]=change;
				childs[0][num]=3;

				change=childs[1][8];
				childs[1][8]=childs[1][3];
				childs[1][3]=change;
				childs[1][num]=3;

				childsum=2;
				childs[2][0]=childs[3][0]=-1;
			}
			else if(checklast==8)
			{
				change=childs[0][2];
				childs[0][2]=childs[0][3];
				childs[0][3]=change;
				childs[0][num]=3;

				change=childs[1][4];
				childs[1][4]=childs[1][3];
				childs[1][3]=change;
				childs[1][num]=3;

				childsum=2;
				childs[2][0]=childs[3][0]=-1;
			}
			break;

		case 4:
			if(checklast==-1)   //初态
			{
				change=childs[0][3];
				childs[0][3]=childs[0][4];
				childs[0][4]=change;
				childs[0][num]=4;

				change=childs[1][5];
				childs[1][5]=childs[1][4];
				childs[1][4]=change;
				childs[1][num]=4;

				childsum=2;
				childs[2][0]=childs[3][0]=-1;
			}
			else if(checklast==3)
			{
				change=childs[0][5];
				childs[0][5]=childs[0][4];
				childs[0][4]=change;
				childs[0][num]=4;

				childsum=1;
				childs[1][0]=childs[2][0]=childs[3][0]=-1;
			}
			else if(checklast==5)
			{
				change=childs[0][3];
				childs[0][3]=childs[0][4];
				childs[0][4]=change;
				childs[0][num]=4;

				childsum=1;
				childs[1][0]=childs[2][0]=childs[3][0]=-1;
			}
			break;
		case 5:
			if(checklast==-1)   //初态   
			{
				change=childs[0][4];
				childs[0][4]=childs[0][5];
				childs[0][5]=change;
				childs[0][num]=5;

				change=childs[1][6];
				childs[1][6]=childs[1][5];
				childs[1][5]=change;
				childs[1][num]=5;

				change=childs[2][8];
				childs[2][8]=childs[2][5];
				childs[2][5]=change;
				childs[2][num]=5;

				childsum=3;
				childs[3][0]=-1;
			}
			else if(checklast==4)
			{
				change=childs[0][6];
				childs[0][6]=childs[0][5];
				childs[0][5]=change;
				childs[0][num]=5;

				change=childs[1][8];
				childs[1][8]=childs[1][5];
				childs[1][5]=change;
				childs[1][num]=5;

				childsum=2;
				childs[2][0]=childs[3][0]=-1;
			}
			else if(checklast==6)
			{
				change=childs[0][4];
				childs[0][4]=childs[0][5];
				childs[0][5]=change;
				childs[0][num]=5;

				change=childs[1][8];
				childs[1][8]=childs[1][5];
				childs[1][5]=change;
				childs[1][num]=5;

				childsum=2;
				childs[2][0]=childs[3][0]=-1;
			}
			else if(checklast==8)
			{
				change=childs[0][4];
				childs[0][4]=childs[0][5];
				childs[0][5]=change;
				childs[0][num]=5;

				change=childs[1][6];
				childs[1][6]=childs[1][5];
				childs[1][5]=change;
				childs[1][num]=5;

				childsum=2;
				childs[2][0]=childs[3][0]=-1;
			}
			break;
		case 6:
			if(checklast==-1)   //初态
			{
				change=childs[0][5];
				childs[0][5]=childs[0][6];
				childs[0][6]=change;
				childs[0][num]=6;

				change=childs[1][7];
				childs[1][7]=childs[1][6];
				childs[1][6]=change;
				childs[1][num]=6;

				childsum=2;
				childs[2][0]=childs[3][0]=-1;
			}
			else if(checklast==5)
			{
				change=childs[0][7];
				childs[0][7]=childs[0][6];
				childs[0][6]=change;
				childs[0][num]=6;

				childsum=1;
				childs[3][0]=-1;
			}
			else if(checklast==7)
			{
				change=childs[0][5];
				childs[0][5]=childs[0][6];
				childs[0][6]=change;
				childs[0][num]=6;

				childsum=1;
				childs[3][0]=-1;
			}
			break;
		case 7:
			if(checklast==-1)   //初态   
			{
				change=childs[0][0];
				childs[0][0]=childs[0][7];
				childs[0][7]=change;
				childs[0][num]=7;

				change=childs[1][6];
				childs[1][6]=childs[1][7];
				childs[1][7]=change;
				childs[1][num]=7;

				change=childs[2][8];
				childs[2][8]=childs[2][7];
				childs[2][7]=change;
				childs[2][num]=7;

				childsum=3;
				childs[3][0]=-1;
			}
			else if(checklast==0)
			{
				change=childs[0][6];
				childs[0][6]=childs[0][7];
				childs[0][7]=change;
				childs[0][num]=7;

				change=childs[1][8];
				childs[1][8]=childs[1][7];
				childs[1][7]=change;
				childs[1][num]=7;

				childsum=2;
				childs[2][0]=childs[3][0]=-1;
			}
			else if(checklast==6)
			{
				change=childs[0][0];
				childs[0][0]=childs[0][7];
				childs[0][7]=change;
				childs[0][num]=7;

				change=childs[1][8];
				childs[1][8]=childs[1][7];
				childs[1][7]=change;
				childs[1][num]=7;

				childsum=2;
				childs[2][0]=childs[3][0]=-1;
			}
			else if(checklast==8)
			{
				change=childs[0][0];
				childs[0][0]=childs[0][7];
				childs[0][7]=change;
				childs[0][num]=7;

				change=childs[1][6];
				childs[1][6]=childs[1][7];
				childs[1][7]=change;
				childs[1][num]=7;

				childsum=2;
				childs[2][0]=childs[3][0]=-1;
			}
			break;
		case 8:
			if(checklast==-1)   //初态   
			{
				change=childs[0][1];
				childs[0][1]=childs[0][8];
				childs[0][8]=change;
				childs[0][num]=8;

				change=childs[1][3];
				childs[1][3]=childs[1][8];
				childs[1][8]=change;
				childs[1][num]=8;

				change=childs[2][5];
				childs[2][5]=childs[2][8];
				childs[2][8]=change;
				childs[2][num]=8;

				change=childs[3][7];
				childs[3][7]=childs[3][8];
				childs[3][8]=change;
				childs[3][num]=8;

				childsum=4;
			}
			else if(checklast==1)
			{
				change=childs[0][3];
				childs[0][3]=childs[0][8];
				childs[0][8]=change;
				childs[0][num]=8;

				change=childs[1][5];
				childs[1][5]=childs[1][8];
				childs[1][8]=change;
				childs[1][num]=8;

				change=childs[2][7];
				childs[2][7]=childs[2][8];
				childs[2][8]=change;
				childs[2][num]=8;

				childsum=3;
				childs[3][0]=-1;
			}
			else if(checklast==3)
			{
				change=childs[0][1];
				childs[0][1]=childs[0][8];
				childs[0][8]=change;
				childs[0][num]=8;

				change=childs[1][5];
				childs[1][5]=childs[1][8];
				childs[1][8]=change;
				childs[1][num]=8;

				change=childs[2][7];
				childs[2][7]=childs[2][8];
				childs[2][8]=change;
				childs[2][num]=8;

				childsum=3;
				childs[3][0]=-1;
			}
			else if(checklast==5)
			{
				change=childs[0][1];
				childs[0][1]=childs[0][8];
				childs[0][8]=change;
				childs[0][num]=8;

				change=childs[1][3];
				childs[1][3]=childs[1][8];
				childs[1][8]=change;
				childs[1][num]=8;

				change=childs[2][7];
				childs[2][7]=childs[2][8];
				childs[2][8]=change;
				childs[2][num]=8;

				childsum=3;
				childs[3][0]=-1;
			}
			else if(checklast==7)
			{
				change=childs[0][1];
				childs[0][1]=childs[0][8];
				childs[0][8]=change;
				childs[0][num]=8;

				change=childs[1][3];
				childs[1][3]=childs[1][8];
				childs[1][8]=change;
				childs[1][num]=8;

				change=childs[2][5];
				childs[2][5]=childs[2][8];
				childs[2][8]=change;
				childs[2][num]=8;

				childsum=3;
				childs[3][0]=-1;
			}
			break;
		default:
			break;
		}
		
		//将扩展的节点添加到completenodes表中，并修改应修改的指针
		int realchild[num];

		for(i=0;i<=3;i++)   //<=3,<而不是3
		{			
			if(childs[i][0]!=-1)
			{
				for(int k=0;k<=num-1;k++)
					realchild[k]=childs[i][k];
				if(isexist(a,realchild))
					childs[i][0]=-1;
			}
		}

		for(i=0;i<=3;i++)
		{
			node *child1;
			if(childs[i][0]!=-1)
			{				
				child1=(node *)malloc(sizeof(node));
				for(int k=0;k<=num-1;k++)
					child1->Sk[k]=childs[i][k];
				child1->last=childs[i][9];
				child1->parent=temp;
				child1->next=NULL;
				lastnode->next=child1;
				lastnode=lastnode->next;
			}
		}

		temp=temp->next;
	}

	while(temp!=NULL)
	{
		b->next=(node *)malloc(sizeof(node));
		setvalue(b->next->Sk,temp->Sk);
		b=b->next;
		temp=temp->parent;
		tracknodesum++;
	}
	AfxMessageBox("运行完毕!目标路径上节点个数为:"+change(tracknodesum));
	b->next=NULL;
}

void CAIHomeWorkDlg::OnRun() 
{
	// TODO: Add your control notification handler code here
	search(&completenodes,&tracknodes,S0);

	converse(tracknodes);
	shownode=(node *)malloc(sizeof(node));
	shownode=tracknodes->next;

	SetDlgItemText(IDC_SHOWINFO,
		"    按“开始显示”键开始显示目标路径上的每个状态!");
	SetDlgItemText(IDC_RUN,"运行完毕");
	SetDlgItemText(IDC_SHOW,"开始显示");
	((CButton *)GetDlgItem(IDC_RUN))->EnableWindow(false);
	((CButton *)GetDlgItem(IDC_SHOW))->EnableWindow(true);
}

void CAIHomeWorkDlg::OnShow() 
{
	// TODO: Add your control notification handler code here
	//shownode=shownode->next;
	if(shownode->next!=NULL)
	{
		for(int i=0;i<=num-1;i++)
			Sk[i]=shownode->next->Sk[i];

		SetDlgItemText(IDC_SHOW,"下一个节点");

		InvalidateRect(&m_Rect0);
		InvalidateRect(&m_Rect1);
		InvalidateRect(&m_Rect2);
		InvalidateRect(&m_Rect3);
		InvalidateRect(&m_Rect4);
		InvalidateRect(&m_Rect5);
		InvalidateRect(&m_Rect6);
		InvalidateRect(&m_Rect7);
		InvalidateRect(&m_Rect8);
		UpdateWindow();	
		shownode=shownode->next;
	}
	else
	{
		AfxMessageBox("显示完毕!");
		SetDlgItemText(IDC_SHOW,"显示完毕");
		((CButton *)GetDlgItem(IDC_SHOW))->EnableWindow(false);
		((CButton *)GetDlgItem(IDC_RANDOM))->EnableWindow(true);
		((CButton *)GetDlgItem(IDC_CONFORM))->EnableWindow(true);
		SetDlgItemText(IDC_SHOWINFO,"   请输入8个数(1-8)或按下“随机产生”键随机产生8个数(1-8),按“确认”键确认。");

		for(int i=0;i<=8;i++)
		{
			((CEdit *)GetDlgItem(idc[i]))->ShowWindow(true);
			SetDlgItemInt(idc[i],0);
		}
	}
}

void CAIHomeWorkDlg::OnAbout() 
{
	// TODO: Add your control notification handler code here
	CAbout AboutDlg;
	AboutDlg.DoModal();
}

void CAIHomeWorkDlg::OnDblclkInfo() 
{
	// TODO: Add your control notification handler code here
	CString numstring;
	int nIndex = m_list.GetCurSel();
	
	m_list.GetText(nIndex,numstring);
	AfxMessageBox("你选择了:"+numstring+"这样一组数");
	SetDlgItemInt(idc[0],antichange(numstring[1]));
	SetDlgItemInt(idc[1],antichange(numstring[3]));
	SetDlgItemInt(idc[2],antichange(numstring[5]));
	SetDlgItemInt(idc[3],antichange(numstring[7]));
	SetDlgItemInt(idc[4],antichange(numstring[9]));
	SetDlgItemInt(idc[5],antichange(numstring[11]));
	SetDlgItemInt(idc[6],antichange(numstring[13]));
	SetDlgItemInt(idc[7],antichange(numstring[15]));
	SetDlgItemInt(idc[8],antichange(numstring[17]));
}