设计一个例如八数码难题或者其他复杂的搜索类难题

输入方法：

例如：

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(" ");

printf("%d ",m.s[i]);

}

while (!kbhit());

i=getch();

printf(" ");

}

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|成功.

COPY来的答案，看能不能帮到你吧。。。

输入方法:

例如:

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(" ");

printf("%d

",m.s[i]);

}

while

(!kbhit());

i=getch();

printf(" ");

}

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|成功.

COPY来的答案，看能不能帮到你吧。。。