连连看AI算法

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_WIDTH 20
#define MAX_HIGH 20
#define MAX_NUMBER 50
#define SAME_NUMBER 4
#define PAUSE
typedef struct tagPOINT {
    int x;
    int y;
} POINT;

int Initmap(int aMap[MAX_WIDTH][MAX_HIGH]);
int PrintMap(int aMap[MAX_WIDTH][MAX_HIGH],POINT *ap1,POINT* ap2);
int PrintMap(int aMap[MAX_WIDTH][MAX_HIGH]);
int Find(int aMap[MAX_WIDTH][MAX_HIGH]);
//测试是否结束
bool testEmpty(int aMap[MAX_WIDTH][MAX_HIGH]);
//测试两个点是不是能一条线连接
bool testLine(int aMap[MAX_WIDTH][MAX_HIGH],POINT *ap1,POINT* ap2);
//测试一个折线
bool testcorner(int aMap[MAX_WIDTH][MAX_HIGH],POINT *ap1,POINT* ap2);
//测试两个折线
bool testtwocorner(int aMap[MAX_WIDTH][MAX_HIGH],POINT *ap1,POINT* ap2);
int main(int argc, char* argv[])
{ 
  int Map[MAX_WIDTH][MAX_HIGH]={0};
 Initmap(Map);
 PrintMap(Map);
 int x=0;
 while (1) {
  Find(Map);
  if(testEmpty(Map))
   break;
  if(x>5){
   printf("无解，你运气真好！\n");
   break;
  }
 }
 return 0;
}
int Initmap(int aMap[MAX_WIDTH][MAX_HIGH])
{
 srand((unsigned int)time(NULL)); //初始化随机数发生器
 //init map
 for(int map1=0;map1<SAME_NUMBER;map1++){//初始化地图
  for(int i=1;i<=MAX_NUMBER;i++){
   int x=rand()%MAX_WIDTH; 
   int y=rand()%MAX_HIGH;
   if(0==aMap[x][y]){
    aMap[x][y]=i;
   }else{
    i--;
   }
  }
 }
 return 1;
}
int PrintMap(int aMap[MAX_WIDTH][MAX_HIGH])
{
 system("cls.exe");
 printf("  ");
 for(int x=0;x<MAX_WIDTH;x++)printf(" %02d",x);
 printf("\n");
 //输出棋盘
 printf("┌");
 for(x=0;x<MAX_WIDTH*3/2;x++)printf("─");
 printf("┐\n");
 
 for(int a=0;a< MAX_HIGH;a++){
  printf("│");
  for(int b=0;b<MAX_WIDTH;b++){
   if(0==aMap[b][a]){
    printf("   ");
   }else{
    printf(" %02d",aMap[b][a]);
   }
  }
  printf("│%d\n",a);
 }

 printf("└");
 for(x=0;x<MAX_WIDTH*3/2;x++)printf("─");
 printf("┘\n");
 return 1;
}
int PrintMap(int aMap[MAX_WIDTH][MAX_HIGH],POINT *ap1,POINT* ap2)
{
// ;
 int temp=aMap[ap1->x][ap1->y];
  system("cls.exe");
 printf("  ");
 for(int x=0;x<MAX_WIDTH;x++)printf(" %02d",x);
 printf("\n");
 printf("┌");
 for(x=0;x<MAX_WIDTH*3/2;x++)printf("─");
 printf("┐\n");
 //输出棋盘 
 for(int a=0;a< MAX_HIGH;a++){
  printf("│");
  for(int b=0;b<MAX_WIDTH;b++){
   if(0==aMap[b][a]){
    printf("   ");
   }else
    if(temp==aMap[b][a]){
     printf("*%02d",aMap[b][a]);
    }else{
     printf(" %02d",aMap[b][a]);
    }
  }
  printf("│%d\n",a);
 }
 printf("└");
 for(x=0;x<MAX_WIDTH*3/2;x++)printf("─");
 printf("┘\n");
 aMap[ap1->x][ap1->y]=0;
 aMap[ap2->x][ap2->y]=0;
 return 1;
}
int Find(int aMap[MAX_WIDTH][MAX_HIGH])
{
 POINT p1={0};
 POINT p2={0};
// 列出所有的选择方案
 for(int x1=0;x1<MAX_WIDTH;x1++){
  for(int y1=0;y1<MAX_HIGH;y1++){
   for(int x2=0;x2<MAX_WIDTH;x2++){
    for(int y2=0;y2<MAX_HIGH;y2++){
     p1.x=x1;
     p1.y=y1;
     p2.x=x2;
     p2.y=y2;
     if ((aMap[p1.x][p1.y]==0)||(aMap[p2.x][p2.y]==0) )continue;//不为0
     if(aMap[p1.x][p1.y]!=aMap[p2.x][p2.y])continue;//相等
     if((x1==x2)&&(y1==y2))continue;//同一个点
     if(testLine(aMap,&p1,&p2)){
      int temp=aMap[p1.x][p1.y];
      PrintMap(aMap,&p1,&p2);
      printf("一直线 数值=%d  p1=%d,%d,p2=%d,%d\n",temp,p1.x,p1.y,p2.x,p2.y);
#ifdef PAUSE
      system("pause");
#endif
      continue;
     }
 
     if(testcorner(aMap,&p1,&p2)){
      int temp=aMap[p1.x][p1.y];
      PrintMap(aMap,&p1,&p2);
      printf("二直线 数值=%d  p1=%d,%d,p2=%d,%d\n",temp,p1.x,p1.y,p2.x,p2.y);
#ifdef PAUSE
      system("pause");
#endif
      continue;
     }
     if(testtwocorner(aMap,&p1,&p2)){
      int temp=aMap[p1.x][p1.y];
      PrintMap(aMap,&p1,&p2);
      printf("三直线 数值=%d  p1=%d,%d,p2=%d,%d\n",temp,p1.x,p1.y,p2.x,p2.y);
#ifdef PAUSE
      system("pause");
#endif
      continue;
     }//*/
    }
   }
  }
 }
 return 1;
}

bool testLine(int aMap[MAX_WIDTH][MAX_HIGH],POINT *ap1,POINT* ap2)//测试两个点是不是能一条线连接
{
 if((ap1->x==ap2->x)||(ap1->y==ap2->y)){
  if(ap1->x==ap2->x){ //x轴相等
   int lisum=0;
   int min=0;
   int max=0;
   if(ap1->y > ap2->y){
    min=ap2->y;
    max=ap1->y;
   }else{
    max=ap2->y;
    min=ap1->y;
   }
   for(int x=min+1;x<max;x++){
    if(aMap[ap1->x][x])return false;
   }
   return true;
  }
  if(ap1->y==ap2->y){ //x轴相等
   int lisum=0;
   int min=0;
   int max=0;
   if(ap1->x > ap2->x){
    min=ap2->x;
    max=ap1->x;
   }else{
    max=ap2->x;
    min=ap1->x;
   }
   for(int x=min+1;x<max;x++){
    if(aMap[x][ap2->y])return false;
   }
   return true;
  }
 }else{
  return false;
 }
 return false;
}
bool testcorner(int aMap[MAX_WIDTH][MAX_HIGH],POINT *ap1,POINT* ap2)
{
 POINT tempPoint={0};
 for(int x=0;x<MAX_WIDTH;x++){
  for(int y=0;y<MAX_HIGH;y++){
   if(0!=aMap[x][y])
    continue;//不是空白
   tempPoint.x=x;
   tempPoint.y=y;
   if(testLine(aMap,ap1,&tempPoint)){
    if(testLine(aMap,&tempPoint,ap2)){
     //printf("tp %d,%d\n",x,y);
     return true;
    }
   }
  }
 }
 return false;
}
bool testtwocorner(int aMap[MAX_WIDTH][MAX_HIGH],POINT *ap1,POINT* ap2)
{
 POINT tP1={0};
 POINT tP2={0};
 for(int x1=0;x1<MAX_WIDTH;x1++){
  for(int y1=0;y1<MAX_HIGH;y1++){
   for(int x2=0;x2<MAX_WIDTH;x2++){
    for(int y2=0;y2<MAX_HIGH;y2++){
     if(0!=aMap[x1][y1])
      continue;//不是空白
     if(0!=aMap[x2][y2])
      continue;//不是空白
     tP1.x=x1;
     tP1.y=y1;
     tP2.x=x2;
     tP2.y=y2;
     if(testLine(aMap,&tP1,&tP2)){
      if(testLine(aMap,&tP1,ap1)&&testLine(aMap,&tP2,ap2)){
       printf("t1=%d,%d t2=%d,%d\n",x1,y1,x2,y2);
       return true;
      }
     }
    }
   }
  }
 }
 return false;
}

bool testEmpty(int aMap[MAX_WIDTH][MAX_HIGH])
{
 int lisum=0;
 for(int x=0;x<MAX_WIDTH;x++){
  for(int y=0;y<MAX_HIGH;y++){
   lisum=lisum+aMap[x][y];
  }
 }
 if (0==lisum)
  return true;
 return false;
}