智力拼图问题.doc

/*
智力拼图问题:将一个6*8的矩阵模块，划分成n个小模块，设计一个算法，用这n个小模块再重新拼接成原
6*8矩阵，要求给出所有的可行方案。

本函数是演示程序，程序最多可以将6*8大小的矩阵分成15个模块，每个小模块的大小不能超过4*4大。并允许
手动编辑。该程序计算所有的可行方案并显示出组合拼接的所有结果。本程序在初始的时候已经给了一个11模块的划分形式，要演示按回车即可。

backup函数是本程序的核心函数，该函数采用标准的递归回溯算法，算法的基本思想是：
从左到右，从上到下扫描6*8矩阵，如果发现某个位置为空（用0表示）就依次尝试每一个还没有用到的
小模块，如果该小模块可以安放在这个位置，那么就放置上去并递归调用下一个可行的位置，否则如果所有小
模块用尽，那么就产生回溯。该函数有两个主要参数x0，y0，表示在6*8矩阵中的第一个空位置。

本程序的操作方法为：
回车：演示开始。
q：在演示过程中退出演示进入模块编辑模式。
c：在编辑模式中减少一个编辑值。
v：在编辑模式中增加一个编辑值。
空格：用于在光标出设置该编辑值。
上，下，左，右：移动光标。
ESC：在编辑模式下退出程序。

如果想让本程序独立运行即其exe文件可以脱离tc根目录到其他目录下运行，要进行如下操作：
    在tc根目录下键入：
    c:\turboc2>bgiobj egavga  //bgiobj是tc下的命令，它将egavga.bgi转换成egavga.obj的目标文件
    c:\turboc2>tlib lib\graphics.lib+egavga  //tlib将egavga.obj的目标模块装到graphics.lib库中
最后在本程序的opengraph函数中加入registerbgidriver(EGAVGA_driver);语句

本程序采用了很好的算法思想，有很高的阅读价值和参考价值，但并不适合c语言初学者，
特别是那些还没有学过数据结构的同学。

本程序建议在vc++6.0下打开阅读，在tc2.0下编译链接
*/

#include
#include
#include
#include
#include
/*以下定义键盘扫描码*/
#define  k_enter 7181
#define  k_up    18432
#define  k_down  20480
#define  k_left  19200
#define  k_right 19712
#define  k_space 14624
#define  k_esc   283
#define  k_c    11875
#define  k_q    4209
#define  k_v    12150
#define _ROW 6
#define _COL 8
#define _MDLM  25  
#define _MDLN  25
#define FLASH  2   /*光标闪烁间隔时间*/

typedef struct point  {
int x;
int y;
}point;

int Qmat[_ROW][_COL];     /*该数组用于存储原始数据_ROW=6,_COL=8*/
int Qmatd[_ROW][_COL];    /*该数组保存运行时结果*/
int shapep[16][17][2];    /*该数组用于保存每个小模块的形状*/
static int Initmat[_ROW][_COL]={1,1,2,2,7,7,10,11,/*该数组保存初始的设置值*/
    1,1,2,2,7,7,10,10,
       1,1,3,3,7,8,9,10,
       3,3,3,3,6,8, 9,10,
       4,4,4,5,6,8,9,9,
       4,4,4,5,6,8,9,9};
int f_num[16];       /*该函数用于记录每个小模块的数组元素组成个数*/

void opengraph(void);  /*打开图形模式*/
void delayx(int);     /*精确延时函数*/
void Init(void);       /*对相关数据结构进行初始化*/
int  DispModule(void);    /*显示所有的小模块形状并计算相关数据结构值*/
void OutputMessage(char* str);   /*在屏幕特定位置显示一行信息str*/
void dispcnum(int num);   /*在屏幕特定位置显示一个数值num*/
void backup(int x0,int y0,int* f_exit);   /*完成对问题的回溯求解*/

main()  {
int flag_f=1,f_flash=0,f_putok=1,f_b=1;
int i=0,j=0,keyid;
int ix,jx;
int fnum=1;
char strn[5];

    opengraph();
    Init();
    setcolor(WHITE);
settextstyle(0,0,1);
dispcnum(fnum);
while(flag_f)   {  /*flag_f状态循环*/
  if(bioskey(1))  {   /*如果有键按下*/
   keyid=bioskey(0);    /*读取键值*/
   if(keyid==k_up||keyid==k_down||keyid==k_left||keyid==k_right)  {
    setfillstyle(SOLID_FILL,BLACK);   /*重显示光标下隐藏数字*/
    setcolor(WHITE);
    bar(_MDLN*(j+1)+4,_MDLM*(i+1)+4,_MDLN*(j+2)-4,_MDLM*(i+2)-4);
    itoa(Qmat[i][j],strn,10);
    outtextxy(_MDLN*(j+1)+6,_MDLM*(i+1)+_MDLM/2,strn);
   }
   switch(keyid)  {
   case k_up:
    i=i==0?i:i-1;
    break;
   case k_down:
    i=i+1==_ROW?i:i+1;
    break;
            case k_left:
    j=j==0?j:j-1;
    break;
   case k_right:
    j=j+1==_COL?j:j+1;
    break;
   case k_esc:
                flag_f=0;
    break;
   case k_v:
    if(fnum<15) ++fnum;
    dispcnum(fnum);
    break;
   case k_c:
    if(fnum>1) --fnum;
    dispcnum(fnum);
    break;
   case k_space:  
    Qmat[i][j]=fnum;
                itoa(fnum,strn,10);
    setcolor(WHITE);
    outtextxy(MDLN*(j+1)+6,_MDLM*(i+1)+_MDLM/2,strn);
    if((f_putok=DispModule())<=0)  OutputMessage("Module Error!");
    else OutputMessage("Module must less than 4x4!");
    break;
   case k_enter:
          if(f_putok>0)  {/*f_putok>0表示模块拆分的合理（小于4*4）*/
              f_b=1;
     backup(0,0,&f_b);   /计算所有可行方案*/
     OutputMessage("That's all! Anykey to return!");
     getch();
     setcolor(WHITE);
     settextstyle(0,0,1);
     setfillstyle(SOLID_FILL,BLACK);
     for(ix=0;ix<_ROW;ix++)  {
                  for(jx=0;jx<_COL;jx++)  {
       bar(_MDLN*(jx+1)+4,_MDLM*(ix+1)+4,_MDLN*(jx+2)4,_MDLM*(ix+2)-4);
                   itoa(Qmat[ix][jx],strn,10);
                      outtextxy(_MDLN*(jx+1)+6,_MDLM*(ix+1)+_MDLM/2,strn);
      }
     }
     OutputMessage("Module must less than 4x4!");
    }
    break;
   }
  }
  delayx(FLASH);  
  if(f_flash)  {   /*用于在编辑模式下完成光标的闪烁*/
   f_flash=0;
   setcolor(WHITE);
   setfillstyle(SOLID_FILL,BLACK);
   bar(_MDLN*(j+1)+4,_MDLM*(i+1)+4,_MDLN*(j+2)-4,_MDLM*(i+2)-4);
   itoa(Qmat[i][j],strn,10);
   outtextxy(_MDLN*(j+1)+6,_MDLM*(i+1)+_MDLM/2,strn);
  }
  else  {
   f_flash=1;
   setfillstyle(SOLID_FILL,WHITE);
   bar(MDLN*(j+1)+4,_MDLM*(i+1)+4,_MDLN*(j+2)-4,_MDLM*(i+2)-4);
  }
}
closegraph();
}

void dispcnum(int num)  {
    char strn[5];
    setcolor(WHITE);
    settextstyle(0,0,1);
    setfillstyle(SOLID_FILL,BLACK);
    bar(30,180,100,198);
    itoa(num,strn,10);
    outtextxy(30,185,strn);
}

void backup(int x0,int y0,int* f_exit)  {/*递归函数*/
    int i,j,f_ok,x,y;
char strn[5];

    for(i=1;i<16;i++)  if(f_num[i]>0)  break;
if(x0>=_ROW||y0>=_COL||i==16)  {  /*i==16表示所有模块都以用完，这样就得到了一个可行方案*/
  setcolor(BLACK);
  settextstyle(0,0,1);
     for(i=0;i<_ROW;i++)  {
      for(j=0;j<_COL;j++)  {
    setfillstyle(SOLID_FILL,Qmatd[i][j]);
       bar(_MDLN*(j+1)+4,_MDLM*(i+1)+4,_MDLN*(j+2)-4,_MDLM*(i+2)-4);
       itoa(Qmatd[i][j],strn,10);
          outtextxy(_MDLN*(j+1)+6,_MDLM*(i+1)+_MDLM/2,strn);
   }
  }
  OutputMessage("Anykey to continue,q to Quit!");
  if(getch()=='q') *f_exit=0;  /*如果按下'q'则强行退出递归*/
  return;
}
for(i=1;i<16&&*f_exit;i++)  {/*计算每一个可用的模块*/
  if(f_num[i]>0)  {  /*如果未用*/
   f_ok=1;
   x=x0;  y=y0;
   for(j=1;j<=f_num[i]&&f_ok;j++)  {  /*完成对该模块的放置并检查可行性*/
    if(x>=0&&y>=0&&x<_ROW&&y<_COL&&Qmatd[x][y]==0) Qmatd[x][y]=i;
    else  {
     f_ok=0;
                    for(x=0;x<_ROW;x++)
                    for(y=0;y<_COL;y++)
                        if(Qmatd[x][y]==i)  Qmatd[x][y]=0;
    }
                x=x0+shapep[i][j][0]; /*又偏移得到组成模块的下一个位置*/
       y=y0+shapep[i][j][1];
   }
   if(f_ok)  {  /*如果放置成功则继续递归，否则回溯*/
                f_num[i]=0-f_num[i];   /*求负表示该模块以用*/
    for(x=0;x<_ROW&&f_ok;x++)  /*找到第一个可空位置*/
                for(y=0;y<_COL&&f_ok;y++)  
     if(Qmatd[x][y]==0)  f_ok=0;
          backup(x-1,y-1,f_exit);  /*对该空位置产生递归调用*/
    for(x=0;x<_ROW;x++)     /*恢复数组数据*/
                for(y=0;y<_COL;y++)
     if(Qmatd[x][y]==i)  Qmatd[x][y]=0;
                f_num[i]=0-f_num[i];   /*恢复*/
   }
  }
}
}

void Init(void)  {
int i,j;
char strn[5];

setcolor(WHITE);
settextstyle(0,0,1);
outtextxy(_MDLN,_MDLN/2,"QiQiaoBan question by STN_LCD!I love doudou!");
for(i=0;i<_ROW;i++)  {
  for(j=0;j<COL;j++)  {
      setcolor(YELLOW);
   rectangle(_MDLN*(j+1),_MDLM*(i+1),_MDLN*(j+2),_MDLM*(i+2));
   Qmat[i][j]=Initmat[i][j];
   Qmatd[i][j]=0;
   itoa(Qmat[i][j],strn,10);
            setcolor(WHITE);
      outtextxy(_MDLN*(j+1)+6,_MDLM*(i+1)+_MDLM/2,strn);

  }
}
OutputMessage("Module must less than 4x4 !");
DispModule();
}

void OutputMessage(char* str)  {
    setfillstyle(SOLID_FILL,BLACK);
bar(250,50,630,80);
setcolor(WHITE);
settextstyle(0,0,1);
outtextxy(252,60,str);
}

int DispModule(void) {
    int dispnum=0,flag,ip_sharp;
int Qmatnum;
int i,j,ik,jk,x,y,injn;
char strn[5];

    memset(f_num,0,16*sizeof(int));
for(i=0;i<_ROW;i++)
  for(j=0;j<_COL;j++)
   ++f_num[Qmat[i][j]];
setfillstyle(SOLID_FILL,BLACK);
bar(20,200,600,450);
for(dispnum=1;dispnum<=15;dispnum++)  {
  if(f_num[dispnum])  {
   flag=1;
   for(i=0;i<=2&&flag;i++)  {
    forj=0;j<=4&&flag;j++)  {
     Qmatnum=0;
     for(ik=i;ik200+80*y;
      setcolor(WHITE);
      rectangle(x,y,x+80,y+80);      
      ip_sharp=0;
               for(in=0,ik=i;ikik;
          shapep[dispnum][ip_sharp++][1]=jk;
         }
         else  {
                                        shapep[dispnum][ip_sharp][0]=ik-shapep[dispnum][0][0];
          shapep[dispnum][ip_sharp++][1]=jk-shapep[dispnum][0][1];
         }
         setcolor(BLACK);
         setfillstyle(SOLID_FILL,Qmat[ik][jk]);
                  bar(x+20*jn+2,y+20*in+2,x+20*(jn+1)-2,y+20*(in+1)-2);
         itoa(Qmat[ik][jk],strn,10);
                  outtextxy(x+20*jn+3,y+20*in+5,strn);
        }
       }
      }
     }
    }
   }
   if(flag)  return 0;
  }
}
return 1;
}

void opengraph(void)  {
int gdriver=VGA,gmode=VGAHI;
/*registerbgidriver(EGAVGA_driver);*/
    initgraph(&gdriver,&gmode,"");
}

void delayx(int clicks)  {
unsigned int far *clock=(unsigned int far*)0x0000046cL;
unsigned int now;
now=*clock;
while(abs(*clock-now)