八数码问题介绍
八数码问题介绍
问题描述：有一个3*3的棋盘，其中有0-8 9个数字，0表示空格，其他的数字可以和0交换位置。求由初始状态
1 2 3
4 5 6
7 8 0
到达目标状态步数最少的解。
输入方法：
例如：
input(从键盘):
1 2 3 7 4 5 8 0 6
output(向屏幕):
Step:1
1 2 3
4 5 6
7 8 0
Step:2
1 2 3
4 5 0
7 8 6
Step:3
1 2 3
4 0 5
7 8 6
Step:4
1 2 3
0 4 5
7 8 6
Step:5
1 2 3
7 4 5
0 8 6
Step:6
1 2 3
7 4 5
8 0 6
我的程序：
#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 i,j;
step++;
printf("Step:%d",step);
for (i=0;i<9;i++)
{
if (0==i%3) printf("/n");
printf("%d ",m.s[i]);
}
while (!kbhit());
i=getch();
printf("/n");
}
void out()
{
int i,j,k;
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,j;
step=0;
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("I cannot find the answer!");
}