📄 eightqueensfinal.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,int color);
void PlaceQueens(int solution[QUEENNUM],int specialx,int specialy);
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,int specialx,int specialy);
/*功能部分函数声明*/
void MainMenu();
void RefSolution(int solution[SOLUTIONNUM][QUEENNUM],
int solutionNum,int specialx,int specialy);
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.4");
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: /*对回车符的响应*/
/*对所有解不存在特殊位置，用(-1,-1)*/
if(selection==ALL_SOLUTION) RefSolution(solution,SOLUTIONNUM,-1,-1);
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,得到八皇后问题的相关解。
specialx和specialy给出特殊皇后位置。
*/
void RefSolution(int solution[SOLUTIONNUM][QUEENNUM],int solutionNum,int specialx,int specialy){
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],specialx,specialy); /*显示第一组解*/
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,specialx,specialy);
else if(selection==LAST&&solutionCount!=0)
solutionCount=ShowNewSolution(LASTONE,solution,solutionCount,specialx,specialy);
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,specialPosition[0],specialPosition[1]);
return;
}
/*帮助文档*/
void Help(){
int code;
cleardevice();
ShowTitle();
setcolor(WHITE);
settextstyle(3,0,4);
outtextxy(500,400,"BACK");
SelectionBar(500,400,4);
/*显示帮助文字*/
settextstyle(2,0,6);
outtextxy(50,100,"The famous 8-queens problem asks you");
outtextxy(50,130,"to place 8 queens on a chess board so");
outtextxy(50,160,"no two attack each other.");
outtextxy(50,210,"A queen moves to any square that is");
outtextxy(50,240,"visible in any of the eight horizontal,");
outtextxy(50,270,"vertical, and diagonal directions from ");
outtextxy(50,300,"the current position. ");
outtextxy(50,350,"This program is aim to show you the");
outtextxy(50,380,"solutions of the difficult problem. ");
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为显示的字符串。⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -