yy九天利哥打架事件:八数码难题

输入方法：
例如：
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!");
}

1：
8 3 4
2 6 5
1 7 0

2：
2 8 3
1 6 4
7 0 5

3：
2 8 0
1 6 3
7 5 4

4：
1 3 4
8 0 2
7 6 5

5：
2 1 6
4 0 8
7 5 3

我知道什么样的情况有解,什么情况没解.
函数f(s)表示s前比s小的数字的数目.
例如:
|1 3 4|
|2 8 6|
|5 7 |
表示成:
|1 3 4|2 8 6|5 7 X| 则f(7)=6, f(5)=4,f(6)=4,f(8)=4,f(2)=1,
f(4)=2,f(3)=1,f(1)=0
当f(a8)+f(a7)+……+f(a1)为偶数时才能重排成
所以嘛,上面那个有解的.
下面我就来证明一下.

设任意一种情况:
|a1 a2 a3|
|a4 a5 a6|
|a7 a8 X | (X表示空格)

将之放在一行上: |a1 a2 a3|a4 a5 a6|a7 a8 X |
数字的上下移动可以相对于是空格的上下移动.
所以我们只要讨论X的移动了:

假设函数f(s)表示s前比s小的数字的数目.
例如:|1 3 4|2 8 6|5 7 X| 则f(7)=6, f(5)=4, f(8)=4,……

对于X在同一行中的移动，f(a8)+f(a7)+……+f(a1)大小不变(*1)
如：|a1 a2 a3|a4 a5 a6|a7 a8 X |=>|a1 a2 a3|a4 a5 a6|a7 X a8|

对于X在列中移动是，我们不妨设X与a6对换(即a6下移一格)
则数列变为|a1 a2 a3|a4 a5 X|a7 a8 a6|,可能引起变化的f(s)只有f(a6),f(a7),f(a8)
讨论：有4种情况1) a6<a7, a6<a8
f(a8) 减小1
f(a7) 减小1
f(a6) 不变
所以f(a8)+f(a7)+……+f(a1)奇偶性不变.
2) a6<a7, a6>a8
f(a8) 不变
f(a7) 减小1
f(a6) 增大1
所以f(a8)+f(a7)+……+f(a1)奇偶性不变.
3) a6>a7, a6>a8
f(a8) 不变
f(a7) 不变
f(a6) 增大2
所以f(a8)+f(a7)+……+f(a1)奇偶性不变.
3) a6>a7, a6<a8
f(a8) 减小1
f(a7) 不变
f(a6) 增大1
所以f(a8)+f(a7)+……+f(a1)奇偶性不变.

这样，再将a3下移一格则|a1 a2 a3|a4 a5 X|a7 a8 a6|=>|a1 a2 X|a4 a5 a3|a7 a8 a6|
则同样，对可能变化的f(a3),f(a4),f(a5)讨论，情况一上面完全一样。

其它情况都如此:
如：|a1 X a3|a4 a5 a6|a7 a8 a2|=>|a1 a5 a3|a4 X a6|a7 a8 a2|
就f(a3),f(a4),f(a5)变化.

结论：因为对于|1 2 3|4 5 6| 7 8 X|, f(8)+f(7)+……+f(1)=28, 是偶数，
所以当f(a8)+f(a7)+……+f(a1)为偶数时才能重排成|1 2 3|4 5 6| 7 8 X|成功.

楼下盗版我的答案的话~ 就是小狗~~

我也想回答,可是怕被楼上的当成小狗,5555

我也想回答

什么数到那个空位啊，问题不清楚