1.cpp

一个解决八数码问题的源码

#include <stdio.h>
#include <math.h>
#include <CONIO.h>
struct bsm
{
  int s[9];
  int prep,pos;
} 
ar1[1000],ar2[1000];
int h1,r1,h2,r2,step;
struct bsm p;
int pd(int k)
{
	int i,j,b1,b2;
	b1=1;
	p.s[p.pos+k]=p.s[p.pos]+p.s[p.pos+k];
	p.s[p.pos]=p.s[p.pos+k]-p.s[p.pos];
	p.s[p.pos+k]=p.s[p.pos+k]-p.s[p.pos];
	p.pos=p.pos+k;
	for (i=0;i<=r1;i++)
	{
		b2=0;
		for (j=0;j<9;j++)
		if (!(ar1[i].s[j]==p.s[j])) b2=1;
			b1=b1*b2;
	}
	return(b1);
}
int pd0(int k)
{
	int i,j,b1,b2;
	b1=1;
	p.s[p.pos+k]=p.s[p.pos]+p.s[p.pos+k];
	p.s[p.pos]=p.s[p.pos+k]-p.s[p.pos];
	p.s[p.pos+k]=p.s[p.pos+k]-p.s[p.pos];
	p.pos=p.pos+k;
	for (i=0;i<=r2;i++)
	{
		b2=0;
		for (j=0;j<9;j++)
		if (!(ar2[i].s[j]==p.s[j])) b2=1;
			b1=b1*b2;
	}
	return(b1);
}
int pd1()
{
	int i,j,b1,b2;
	b1=0;
	for (i=h2;i<=r2;i++)
	{
		b2=0;
		for (j=0;j<9;j++)
		if (!(ar2[i].s[j]==p.s[j])) b2=1;
		if (0==b2)
		{
			r2=i;
			b1=1;
		}
	}
	return(b1);
}
int pd2()
{
	int i,j,b1,b2;
	b1=0;
	for (i=h1;i<=r1;i++)
	{
		b2=0;
		for (j=0;j<9;j++)
		if (!(ar1[i].s[j]==p.s[j])) b2=1;
		if (0==b2)
		{
			r1=i;
			b1=1;
		}
	}
	return(b1);
}
void out1(struct bsm m)
{
	int a;
	step++;
	printf("Step:%d",step);
	for (a=0;a<9;a++)
	{
		if (0==a%3) printf("\n");
		printf("%d ",m.s[a]);
	}
	while (!kbhit());
	a=getch();
	printf("\n");
}
void out()
{
	int i,j;
	int arr[1000];
	j=-1;
	while (r1>0)
	{
		j=j+1;
		arr[j]=r1;
		r1=ar1[r1].prep;
	}
	j=j+1;
	arr[j]=r1;
	for (i=j;i>-1;i--)
	{
		out1(ar1[arr[i]]);
	}
	while (r2>0)
	{
		out1(ar2[ar2[r2].prep]);
		r2=ar2[r2].prep;
	}
}
void main()
{
	int i;
	step=0;
	printf("八数码初态为123456780\n");
	printf("请输入终态按回车结束!\n");
	for (i=0;i<9;i++)
	{
		ar1[0].s[i]=(i+1)%9;
		scanf("%d",&ar2[0].s[i]);
		if (0==ar2[0].s[i]) ar2[0].pos=i;
	}
	ar1[0].pos=8;
	ar1[0].prep=-1;
	ar2[0].prep=-1;
	h1=0;r1=0;h2=0;r2=0;
	while(((h1<=r1)&&(r1<999))||((h2<=r2)&&(r2<999)))
	{
		if ((h1<=r1)&&(r1<999))
		{
			p=ar1[h1];
			if (p.pos>2)
			{
				if (1==pd(-3))
				{
					p.prep=h1;
					r1++;
					ar1[r1]=p;
					if (1==pd1())
					{
						out();return;
					}
				}
			}
			p=ar1[h1];
			if (p.pos%3>0)
			{
				if (1==pd(-1))
				{
					p.prep=h1;
					r1++;
					ar1[r1]=p;
					if (1==pd1())
					{
						out();return;
					}
				}
			}
			p=ar1[h1];
			if (p.pos<6)
			{
				if (1==pd(3))
				{
					p.prep=h1;
					r1++;
					ar1[r1]=p;
					if (1==pd1())
					{
						out();return;
					}
				}
			}
			p=ar1[h1];
			if (p.pos%3<2)
			{
				if (1==pd(1))
				{
					p.prep=h1;
					r1++;
					ar1[r1]=p;
					if (1==pd1())
					{
						out();return;
					}
				}
			}
			h1++;
		}
		if ((h2<=r2)&&(r2<999))
		{
			p=ar2[h2];
			if (p.pos>2)
			{
				if (1==pd0(-3))
				{
				p.prep=h2;
				r2++;
				ar2[r2]=p;
				if (1==pd2())
				{
					out();return;
				}
			}
		}
		p=ar2[h2];
		if (p.pos%3>0)
		{
			if (1==pd0(-1))
			{
				p.prep=h2;
				r2++;
				ar2[r2]=p;
				if (1==pd2())
				{
					out();return;
				}
			}
		}
		p=ar2[h2];
		if (p.pos<6)
		{
			if (1==pd0(3))
			{
				p.prep=h2;
				r2++;
				ar2[r2]=p;
				if (1==pd2())
				{
					out();return;
				}
			}
		}
		p=ar2[h2];
		if (p.pos%3<2)
		{
			if (1==pd0(1))
			{
				p.prep=h2;
				r2++;
				ar2[r2]=p;
				if (1==pd2())
				{
					out();return;
				}
			}
		}
		h2++;
	}
}
if (step==0) printf("不能找到正确的步骤!\n");
}