eightqueens.c

由C语言编写的八皇后算法的图形演示版

#include<stdio.h>
#include<math.h>
#include <graphics.h>
#include <dos.h>
#include<bios.h>



/*核心算法部分宏定义*/
/*皇后的个数进行宏定义，利于可扩展性*/
#define QUEENNUM 8
/*八皇后问题共有92组解*/
#define SOLUTIONNUM 92

/*图形图像部分宏定义*/
/*每个格子的边长为45像素*/
#define EDGE 46
/*外框间隙宽度*/
#define SPACE 3
/*棋盘起始位置x,y*/
#define STARTX 40
#define STARTY 70
/*解的位数*/
#define MAXBIT 2
/*下一个和上一个*/
#define NEXTONE 1
#define LASTONE 0
/*计数器所在位置*/
#define COUNTPOSITIONX 500
#define COUNTPOSITIONY 150



/*核心算法部分函数声明*/
int EightQueens(int x[SOLUTIONNUM][QUEENNUM]);
int Place(int x[QUEENNUM],int k);
void SaveSolution(int temp[QUEENNUM],int x[SOLUTIONNUM][QUEENNUM],int k);

/*图形图像部分函数声明*/
void InistGraphic();
void SelectionBar(int x,int y,int size);
void ReplayText(int x,int y,char string[],int size);
void ShowTitle();
void ShowBoard();
void ShowQueen(int x,int y);
void PlaceQueens(int solution[QUEENNUM]);
void ClearQueens(int solution[QUEENNUM]);
void ClearGrid(int i,int j);
void LightenGrid(int i,int j);
int ShowNewSolution(int style,int solution[SOLUTIONNUM][QUEENNUM],int solutionCount);

/*功能部分函数声明*/
void MainMenu();
void RefSolution(int solution[SOLUTIONNUM][QUEENNUM],int solutionNum);
void SpecialSolution(int solution[SOLUTIONNUM][QUEENNUM]);
void ChoosePosition(int thePosition[2]);
void Help();
void Exit();
void conversion(int num,char numString[MAXBIT]);
int findSpecialSolution(int solution[SOLUTIONNUM][QUEENNUM],
                          int specialSolution[SOLUTIONNUM][QUEENNUM],int specialPosition[2]);

/*键盘部分函数声明*/
int specialkey();



/*主函数*/
int main(){

    InistGraphic();

    MainMenu();

    closegraph();

    return 0;
}

/*核心算法的测试main函数*/
/*
int main(){

    int x[SOLUTIONNUM][QUEENNUM];
    int i,j;

    printf("Total solution Of Eight Quuens Problem is %d\n",EightQueens(x));
    for(i=0;i<SOLUTIONNUM;i++){
        for(j=0;j<QUEENNUM;j++) printf("%d ",x[i][j]);
        printf("\n");
        getch();
    }
    getch();

    return 0;
}
*/



/*功能部分函数*/

/*主菜单*/
void MainMenu(){

    int code;   /*接收键盘信息所用变量*/
    int i;

    /*主菜单枚举信息*/
    /*设立selection枚举变量，指向现在所选内容*/
    enum menu{ALL_SOLUTION,SPECIAL_SOLUTION,HELP,EXIT}selection;
    /*主菜单内容字符串*/
    char menuText[4][17]=
         {"ALL SOLUTION","SPECIAL SOLUTION","H E L P","E X I T"};
    /*主菜单字符串长度数组，不用strlen求解，提高运行效率*/
    int menuTextLen[4]={12,16,7,7};
    /*主菜单字符串位置*/
    int textPosition[4][2]={{200,200},{170,250},{250,300},{255,350}};
    int solution[SOLUTIONNUM][QUEENNUM]; /*存储八皇后的所有解*/

    EightQueens(solution);    /*解决八皇后问题*/

    selection=ALL_SOLUTION;   /*selection默认为ALL_SOLUTINO*/

    cleardevice();    /*清除全屏*/

    settextstyle(1,0,6);
    outtextxy(80,40,"EIGHT QUEENS");
    outtextxy(320,100,"PROBLEM");

    settextstyle(3,0,4);
    for(i=0;i<4;i++)
      outtextxy(textPosition[i][0],textPosition[i][1],menuText[i]);

    settextstyle(2,0,6);
    outtextxy(300,450,"prensents by liuyubobobo 2006.5");

    while(1){
      /*显示正在选择的项*/
      /*充分运用枚举常量和数组的对应关系*/
      SelectionBar(textPosition[selection][0],textPosition[selection][1],
                     menuTextLen[selection]);

      code=specialkey();     /*接收键盘字符*/

      /*对接收字符的响应*/
      switch(code){
        case 80:     /*对下箭头的响应*/
          if(selection!=EXIT){
            ReplayText(textPosition[selection][0],textPosition[selection][1],
                       menuText[selection],menuTextLen[selection]);
            selection++;
            }
          break;
        case 72:     /*对上箭头的响应*/
          if(selection!=ALL_SOLUTION){
             ReplayText(textPosition[selection][0],textPosition[selection][1],
                          menuText[selection],menuTextLen[selection]);
             selection--;
          }
          break;
        case 13:     /*对回车符的响应*/
          if(selection==ALL_SOLUTION) RefSolution(solution,SOLUTIONNUM);
          else if(selection==SPECIAL_SOLUTION) SpecialSolution(solution);
          else if(selection==HELP) Help();
          else if(selection==EXIT) Exit();
          break;
        case 27: Exit();   /*对Esc直接响应退出*/
        default: break;
      }
    }

    return;
}

/*给出解向量组solution和解的个数solutionNum,得到八皇后问题的相关解*/
void RefSolution(int solution[SOLUTIONNUM][QUEENNUM],int solutionNum){

    int code;   /*接收键盘信息所用变量*/
    int i;
    int solutionCount=0;

    /*菜单枚举信息*/
    /*设立selection枚举变量，指向现在所选内容*/
    enum menu{NEXT,LAST,BACK}selection;
    /*菜单内容字符串*/
    char menuText[3][5]=
         {"NEXT","LAST","BACK"};
    /*菜单字符串长度数组，不用strlen求解，提高运行效率*/
    int menuTextLen[3]={4,4,4};
    /*主菜单字符串位置*/
    int textPosition[3][2]={{480,300},{480,350},{480,400}};
    /*计数器字符串位置*/

    selection=NEXT;   /*selection默认为NEXT*/

    cleardevice();
    ShowTitle();
    ShowBoard();
    /*显示选项*/
    settextstyle(3,0,4);
    for(i=0;i<3;i++)
      outtextxy(textPosition[i][0],textPosition[i][1],menuText[i]);
    /*显示记分牌*/
    settextstyle(1,0,4);
    outtextxy(COUNTPOSITIONX-50,COUNTPOSITIONY-50,"SOLUTION");
    /*将现在解的组数转换为字符形式。
      传入参数为solutionCount+1，因为数组索引与自然索引相差1。*/
    settextstyle(3,0,4);
    outtextxy(COUNTPOSITIONX,COUNTPOSITIONY,"01");

    PlaceQueens(solution[solutionCount]);  /*显示第一组解*/

    while(1){
      /*显示正在选择的项*/
      /*充分运用枚举常量和数组的对应关系*/
      SelectionBar(textPosition[selection][0],textPosition[selection][1],
                     menuTextLen[selection]);

      code=specialkey();     /*接收键盘字符*/

      /*对接收字符的响应*/
      switch(code){
        case 80:     /*对下箭头的响应*/
          if(selection!=BACK){
            ReplayText(textPosition[selection][0],textPosition[selection][1],
                       menuText[selection],menuTextLen[selection]);
            selection++;
            }
          break;
        case 72:     /*对上箭头的响应*/
          if(selection!=NEXT){
             ReplayText(textPosition[selection][0],textPosition[selection][1],
                          menuText[selection],menuTextLen[selection]);
             selection--;
          }
          break;
        case 13:     /*对回车符的响应*/
          if(selection==NEXT&&solutionCount!=solutionNum-1)
            solutionCount=ShowNewSolution(NEXTONE,solution,solutionCount);
          else if(selection==LAST&&solutionCount!=0)
            solutionCount=ShowNewSolution(LASTONE,solution,solutionCount);
          else if(selection==BACK) MainMenu();
          break;
        case 27: Exit();   /*对Esc直接响应退出*/
        default: break;
      }
    }

    return;
}

/*八皇后特殊解*/
void SpecialSolution(int solution[SOLUTIONNUM][QUEENNUM]){

    int specialPosition[2];
    int specialSolution[SOLUTIONNUM][QUEENNUM];
    int solutionNum;

    cleardevice();
    ShowTitle();
    ShowBoard();
    ChoosePosition(specialPosition);
    solutionNum=findSpecialSolution(solution,specialSolution,specialPosition);
    RefSolution(specialSolution,solutionNum);

    return;
}

/*帮助文档*/
void Help(){

    int code;

    cleardevice();
    ShowTitle();
    settextstyle(3,0,4);
    outtextxy(500,370,"BACK");
    SelectionBar(500,370,4);

    while(1){

      code=specialkey();     /*接收键盘字符*/

      /*对接收字符的响应*/
      switch(code){
        case 13:     /*对回车符的响应*/
          MainMenu();
          break;
        case 27: Exit();   /*对Esc直接响应退出*/
        default: break;
      }
    }

    return;
}

/*退出*/
void Exit(){

  exit(0);

  return;
}

/*将数字num转换为字符串放入numString中*/
void conversion(int num,char numString[MAXBIT]){

    int i;
    int bit=MAXBIT-1;    /*记录现在存取的位数，初始化为最后一位*/

    for(i=0;i<MAXBIT;i++) numString[i]='0';
    while(num){
        numString[bit]=num%10+'0';
        bit--;
        num/=10;
    }

    return;
}

/*选择某一位置的功能函数，选择的位置由传入的数组带出*/
void ChoosePosition(int position[2]){

    int code;
    int nowi=0,nowj=0; /*初始选择位置，默认为(0,0)*/
    int hasFound=0;    /*控制是否选定特殊点，初始化为否*/

    settextstyle(1,0,4);
    outtextxy(450,150,"CHOOSE");
    outtextxy(500,200,"A");
    outtextxy(440,250,"POSITION");
    while(1){
      LightenGrid(nowi,nowj);

      code=specialkey();     /*接收键盘字符*/

      /*对接收字符的响应*/
      switch(code){

        case 72:     /*对上箭头的响应*/
          if(nowi!=0){ClearGrid(nowi,nowj); nowi--; LightenGrid(nowi,nowj);}
          break;
        case 77:     /*对右箭头的响应*/
          if(nowj!=QUEENNUM-1){ClearGrid(nowi,nowj); nowj++; LightenGrid(nowi,nowj);}
          break;
        case 80:     /*对下箭头的响应*/
          if(nowi!=QUEENNUM-1){ClearGrid(nowi,nowj); nowi++; LightenGrid(nowi,nowj);}
          break;
        case 75:     /*对左箭头的响应*/
          if(nowj!=0){ClearGrid(nowi,nowj); nowj--; LightenGrid(nowi,nowj);}
          break;

        case 13:     /*对回车符的响应*/
          position[0]=nowi;
          position[1]=nowj;
          hasFound=1;
          break;

        case 27: Exit();   /*对Esc直接响应退出*/
        default: break;
      }

      if(hasFound) break;
    }

    return;
}

/*在solution中查找所有包含specialPosition*/
int findSpecialSolution(int solution[SOLUTIONNUM][QUEENNUM],
                          int specialSolution[SOLUTIONNUM][QUEENNUM],int specialPosition[2]){

    int i,j;
    int solutionNum=0;

    for(i=0;i<SOLUTIONNUM;i++)
      if(solution[i][specialPosition[0]]==specialPosition[1]){
        SaveSolution(solution[i],specialSolution,solutionNum);
        solutionNum++;
      }

    return solutionNum;
}



/*图形图像部分函数*/

/*初始化图形图像驱动*/
void InistGraphic(){

    int gdriver=DETECT,gmode;

    initgraph(&gdriver,&gmode,"C:\\TC\\BGI");   /*确定BGI文件路径*/

    return;
}

/*
对SANS_SERIF横向4号字体的选项画外边框。
x,y为显示左上角像素坐标位置。
size为菜单选项字符串长度。
*/
void SelectionBar(int x,int y,int size){

    setcolor(YELLOW);
    rectangle(x-5,y+5,x+17*size+5,y+40);
    setcolor(WHITE);

    return;
}

/*
对SANS_SERIF横向4号字体重新显示。
x,y为显示左上角像素坐标位置。
string为显示的字符串。