huarongdaojavashixian.txt

华容道的java实现

//---------------------------------------------------------------------------

#include <stdio.h>

#include <conio.h>

//---------------------------------------------------------------------------

//--以下定义一些常数或参数--

//---------------------------------------------------------------------------

//棋盘表示使用char一维数组,例:char q[20];

//用1-15表示各棋子,空位用0表示,兵1-4,竖将5-9,横将10-14,大王15

//大王只能1个,将必须5个(横竖合计),兵必须为4个

const char U[]="ABBBBCCCCCHHHHHM";; //棋子类型表

const COL[20]={0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3};   //列号表

const ROW[20]={0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4};   //行号表

const WQ2[13]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096}; //二进制位权表(12个)

//---------------------------------------------------------------------------

//--以下定义几函数--

//---------------------------------------------------------------------------

//以下define用于棋盘复制,不要用环循,实地址直接引用要快8倍

#define qpcpy(q1,q2) {/*复制棋盘*/\

  int *ls1=(int*)q1,*ls2=(int*)q2;\

  ls1[0]=ls2[0],ls1[1]=ls2[1],ls1[2]=ls2[2],ls1[3]=ls2[3],ls1[4]=ls2[4];\

}

//memset(JD,0,Bm.bmtot);

void qkmem(void *ps,int n){ //内存块置0

  register int *p=(int*)ps,*p2=p+n/4;

  while(p<p2) *p++=0;

  char *p3=(char *)p,*p4=(char *)ps+n;

  while(p3<p4) *p3++=0;

}

void prt(char *q){ //打印棋盘

  int i,j;

  for(i=0;i<5;i++){

    for(j=0;j<4;j++) printf("%2d ",q[i*4+j]);

    printf("\r\n");

  }

  printf("\r\n");

}

//---------------------------------------------------------------------------

//--以下是搜索算法之一(解决编码问题)--

//---------------------------------------------------------------------------

class PmBm{ //盘面编码类

 public:

 short int *Hz,*Sz,*Bz;  //竖将,横将,小兵,组合序号表

 int *Hw,*Sw,Mw[12]; //权值表:横条,竖条,大王

 int bmtot;

 PmBm(char *q){//初始化编码表

   Hz=new short int[4096*3]; Sz=Hz+4096; Bz=Hz+4096*2;

   Hw =new int[792*2];  Sw=Hw+792;  //C12取5=792

   int i,j,k;

   int Hn=0,Bn=0,Sn=0; //各类子数目,大王默认为1不用计数

   for(i=0;i<20;i++){   //计算各种棋子的个数

     if(U[q[i]]=='B') Bn++;

     if(U[q[i]]=='H') Hn++;

     if(U[q[i]]=='C') Sn++;

   }

   Hn/=2,Sn/=2;

   int Hmax=WQ2[11],Smax=WQ2[12-Hn*2],Bmax=WQ2[16-(Hn+Sn)*2]; //各种子的最大二进位数

   int Hx=0,Sx=0,Bx=0; //各种棋子组合的最大序号

   for(i=0;i<4096;i++){  //初始化组合序号表

     for(j=0,k=0;j<12;j++) if(i&WQ2[j]) k++; //计算1的个数

     if(k==Hn&&i<Hmax) Hz[i]=Hx++;

     if(k==Sn&&i<Smax) Sz[i]=Sx++;

     if(k==Bn&&i<Bmax) Bz[i]=Bx++;

   }

   int Sq=Bx,Hq=Bx*Sx,Mq=Bx*Sx*Hx; //竖将位权,横将位权,王位权

   for(i=0;i<12;i++) Mw[i]=i*Mq; //初始化大王权值表

   for(i=0;i<Hx;i++) Hw[i]=i*Hq; //初始化横将权值表

   for(i=0;i<Sx;i++) Sw[i]=i*Sq; //初始化竖将权值表

   bmtot=Mq*12;

 }

 ~PmBm(){ delete[] Hz,Hw; }

 int BM(char *q){ //盘面编码

   int Bb=0,Bd=-1; //空位序号记录器

   int Sb=0,Sd=-1; //竖条序号记录器

   int Hb=0,Hd=-1; //横条序号记录器

   int Mb;         //大王序号记录器

   char c,lx,f[16]={0};   //其中f[]标记几个棋子是否已确定位置序号

   int i;

   for(i=0;i<20;i++){

     c=q[i],lx=U[c]; //当前的值

     if(lx=='M') { //大王定序

       if(!f[c]) Mb=i-ROW[i],f[c]=1;

       continue;

     }

     if(COL[i]<3&&U[q[i+1]]<='H') Hd++; //横条位置序号(编号)

     if(lx=='H') {//横将定序,转为二进制进行询址得Hb

       if(!f[c]) Hb+=WQ2[Hd],f[c]=1;

       continue;

     }

     if(ROW[i]<4&&U[q[i+4]]<='C') Sd++; //竖将位置序号(编号)

     if(lx=='C') { //竖条定序,转为二进制进行询址得Sb

       if(!f[c]) Sb+=WQ2[Sd],f[c]=1;

       continue;

     }

     if(lx<='B') Bd++;  //小兵位置序号(编号)

     if(lx=='B') Bb+=WQ2[Bd]; //小兵定序,转为二进制进行询址得Bb

   }

   //Hb,Sb,Bb为组合序号,"横刀立马"最大值为小兵C(6,4)-1=15-1,竖条C(10,4)-1=210-1

   Bb=Bz[Bb],Sb=Sz[Sb],Hb=Hz[Hb];//询址后得得Bb,Sb,Hb组合序号

   return Bb+Sw[Sb]+Hw[Hb]+Mw[Mb]; //用位权编码,其中Bb的位权为1

 }

 int dcBM(char *q){ //按左右对称规则考查棋盘,对其编码

   char i,q2[20];

   for(i=0;i<20;i+=4) q2[i]=q[i+3],q2[i+1]=q[i+2],q2[i+2]=q[i+1],q2[i+3]=q[i];

   return BM(q2);

 }

};

//---------------------------------------------------------------------------

//以下定义搜索过程使用的核心数据结构

//---------------------------------------------------------------------------

struct PMZB{ //盘面走步集结构

  char s[10],d[10];//原位置,目标位置,最多只会有10步

  int n;           //总步数

};

//以下是走法生成器函数

#define kgpd(i)  (i==k1||i==k2) //空格判断宏

#define kgpd1(i) (i==k1&&h==1)  //竖联空格判断宏

#define kgpd2(i) (i==k1&&h==2)  //横联空格判断宏

#define zin(des) z->s[z->n]=i,z->d[z->n]=des,z->n++ //保存步法宏

void zbFX(char *q,PMZB *z){ //分析当前可能的步法,并将所有可能的步法保存在z中

  int i,col,k1=0,k2=0,h=0; //i,列,空格1位置,空格2位置,h为两空格的联合类型

  char c,lx,f[16]={0}; //f[]记录已判断过的棋字

  z->n=0; //计步复位

 

  for(i=0;i<20;i++){

    if(!q[i]) k1=k2,k2=i; //查空格的位置

  }

  if(k1+4==k2) h=1;            //空格竖联合

  if(k1+1==k2&&COL[k1]<3) h=2; //空格横联合

  for(i=0;i<20;i++){

    c=q[i],lx=U[c],col=COL[i];

    if(f[c]) continue;

    switch(lx){

     case 'M': //曹操可能的走步

       if(kgpd2(i+8))        zin(i+4);  //向下

       if(kgpd2(i-4))        zin(i-4);  //向上

       if(col<2&&kgpd1(i+2)) zin(i+1);  //向右

       if(col  &&kgpd1(i-1)) zin(i-1);  //向左

       f[c]=1; break;

     case 'H': //关羽可能的走步

       if(kgpd2(i+4))        zin(i+4);  //向下

       if(kgpd2(i-4))        zin(i-4);  //向上

       if(col<2&&kgpd(i+2)) {zin(i+1); if(h==2) zin(k1); }  //向右

       if(col  &&kgpd(i-1)) {zin(i-1); if(h==2) zin(k1); }  //向左

       f[c]=1; break;

     case 'C': //张飞,马超,赵云,黄忠可能的走步

       if(kgpd(i+8))        {zin(i+4); if(h==1) zin(k1); }  //向下

       if(kgpd(i-4))        {zin(i-4); if(h==1) zin(k1); }  //向上

       if(col<3&&kgpd1(i+1)) zin(i+1);  //向右

       if(col  &&kgpd1(i-1)) zin(i-1);  //向左

       f[c]=1; break;

     case 'B': //小兵可能的走步

       if(kgpd(i+4))        { if(h){zin(k1);zin(k2);} else zin(i+4); } //向上

       if(kgpd(i-4))        { if(h){zin(k1);zin(k2);} else zin(i-4); } //向下

       if(col<3&&kgpd(i+1)) { if(h){zin(k1);zin(k2);} else zin(i+1); } //向右

       if(col  &&kgpd(i-1)) { if(h){zin(k1);zin(k2);} else zin(i-1); } //向右

       break;

    }

  }

}

void zb(char *q,int s,int d){ //走一步函数

  char c=q[s],lx=U[c];

  switch(lx){

    case 'B': {q[s]=0;        q[d]=c;          break; }

    case 'C': {q[s]=q[s+4]=0; q[d]=q[d+4]=c;   break; }

    case 'H': {q[s]=q[s+1]=0; q[d]=q[d+1]=c;   break; }

    case 'M': {q[s]=q[s+1]=q[s+4]=q[s+5]=0; q[d]=q[d+1]=q[d+4]=q[d+5]=c; break; }

  }

}

//---------------------------------------------------------------------------

//--以下是搜索过程（广度优先）--

//---------------------------------------------------------------------------

class ZBD{ //走步队

 public:

 char (*z)[20];     //队列

 PMZB zbj;

 int n;       //队长度

 int *hs,*hss;//回溯用的指针及棋子

 int m,cur;   //队头及队头内步集游标,用于广度搜索

 int max;     //最大队长

 int *res,ren;//结果

 ZBD(int k){ z=new char[k][20]; hs=new int[k*2+500]; hss=hs+k; res=hss+k; max=k; reset(); }

 ~ZBD(){ delete[] z; delete[] hs;}

 void reset() { n=0; m=0,cur=-1; hss[n]=-1; ren=0;}

 int zbcd(char *q){ //走步出队

   if(cur==-1) zbFX(z[m],&zbj);

   cur++; if(cur>=zbj.n) {m++,cur=-1; return 1;} //步集游标控制

   if(hss[m]==zbj.s[cur]) return 1;//和上次移动同一个棋子时不搜索,可提速20%左右

   qpcpy(q,z[m]); zb(q,zbj.s[cur],zbj.d[cur]); //走步后产生新节点,结果放在q中

   return 0;

 }

 void zbrd(char *q){ //走步入队

   if(n>=max) { printf("队溢出.\r\n"); return; }

   qpcpy(z[n],q); //出队

   if(cur>=0) hss[n]=zbj.d[cur]; //记录移动的子(用于回溯)

   hs[n++]=m; //记录回溯点

 }

 void hui(int cs){ //参数:层数

   int k=cs-2; ren=cs,res[cs-1]=m;

   for(;k>=0;k--) res[k]=hs[res[k+1]]; //回溯

 }

 char* getre(int n){ return z[res[n]];} //取第n步盘面

 

};

//--广度优先--

void bfs(char *q,int dep){ //参数为棋盘及搜索最大深度

  int i,j,k,bm,v; //ok表示是否找到

  int js=0,js2=0;

  PmBm Bm(q); //建立编码器

  char *JD=new char[Bm.bmtot]; qkmem(JD,Bm.bmtot); //建立节点数组

  ZBD Z=ZBD(Bm.bmtot/10); //建立队

  for(Z.zbrd(q),i=1;i<=dep;i++){ //一层一层的搜索

    k=Z.n;

    //printf("本层%d %d\r\n",i,k-Z.m);

    while(Z.m<k){ //广度优先

      if(Z.zbcd(q)) continue;     //返回1说明是步集出队,不是步出队

      js++;

      if(q[17]==15&&q[18]==15) { Z.hui(i); goto end; }//大王出来了

      if(i==dep) continue; //到了最后一层可以不再入队了

      bm=Bm.BM(q);

      if(!JD[bm]){

        js2++ ;  //js搜索总次数计数和js2遍历的实结点个数

        JD[bm]=1, JD[Bm.dcBM(q)]=1;//对节点及其对称点编码

        Z.zbrd(q);

      }

    }

  }

  end:delete JD;

  printf("共遍历%d个节点,其中实结点%d.队长%d,搜索层数%d,任意键...\r\n",js,js2,Z.n,Z.ren);

  if(!Z.ren) { printf("此局%d步内无解",dep); return; }

  for(i=0;i<Z.ren;i++) { getch();clrscr(); prt(Z.getre(i)); } //输出结果

}

//---------------------------------------------------------------------------

void main(int argc, char* argv[])

{//华荣道棋盘参数,须留二个空位,兵4个1-4,竖将5-9,横将10-14,大王15(1个)

 char qp[20]={

   6,15,15,7,

   6,15,15,7,

   8,11,11,5,

   8,3, 4, 5,

   2,0, 0, 1

 };

 int i,dep=81;

 bfs(qp,dep);

 getch();

}