/*
智力拼图问题:将一个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 <stdio.h>
#include <stdlib.h>
#include <bios.h>
#include <graphics.h>
#include <string.h>
/*以下定义键盘扫描码*/
#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,in,jn;
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++) {
for(j=0;j<=4&&flag;j++) {
Qmatnum=0;
for(ik=i;ik<i+4;ik++)
for(jk=j;jk<j+4;jk++)
if(Qmat[ik][jk]==dispnum) ++Qmatnum;
if(Qmatnum==f_num[dispnum]) {
flag=0;
x=(dispnum-1)%5; y=(dispnum-1)/5;
x=20+80*x; y=200+80*y;
setcolor(WHITE);
rectangle(x,y,x+80,y+80);
ip_sharp=0;
for(in=0,ik=i;ik<i+4;ik++,in++) {
for(jn=0,jk=j;jk<j+4;jk++,jn++) {
if(Qmat[ik][jk]==dispnum) {
if(ip_sharp==0) {
shapep[dispnum][ip_sharp][0]=ik;
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)<clicks){}
}