请问华容道问题的解法,非高手勿进!
在4*5型华容道中,是不是任意排列都可以得出结果?请证明或举出反例。任意一个4*5型华容道的一般解法,给出思路即可,有例子更好,如能发来原程序我就给您磕头了,只要回答出任意一个问题就可以得到满分。
参考答案:算法
int move(int d)
{if(递归深度d>=规定值)return;
顺序对基础状态中与空白格相铃的每个方格循环
{
确定当前相铃方格p;
if(是来回移动)continue;
生成本次移动的新状态;
if(新状态是终状态)
{
输出解;
return;
}
递归调用;
}
}
#include<stdio.h>
#define N 30
#define LEN 9
struct ele{char state[LEN+1];
int empty;
}q[N];
int net[LEN][5]={{1,3,-1},{0,2,4,-1},{1,5,-1},{0,4,6,-1},{1,3,5,7,-1},{2,4,8,-1},{3,7,-1},{4,6,8,-1},{5,7,-1}};
char success[LEN+1]="***********";//终态
char state0[len+1]="***********";//初态
int best=N;//限制解的步骤
void main(void)
{
q[0].empty=8;//初始状态的空格位置
strcpy(q[0].state,state0);//设定状态迁移的初态
move(1);
printf("The program has completed1\n");
}
int move(int d)
{
int k,j,p,empty;
if(d>best)
return;
empty=q[d-1].empty;//基础状态的空格位置
for(k=0;net[empty][k]>=0;k++)
{p=net[empty][k];//后继状态的空格位置
if*d<=2&&p==q[d-2].empty)//略过来回移动
continue;
//生成本次移动的新状态
strcpy(q[d].state,q[d-1].state);
q[d].state[empty]=q[d-1].state[p];
q[d].state[p]='';
q[d].empty=p;
if(strcmp(q[d].state,success)==0)
{//新状态是解,输础
for(j=1;j<=d;j++)
printf("%2c",q[j-1].state[q[j].empty]);
printf("\n");
best=d;
return;
}
move(d+1);//继序递归
}
}