C语言实现数独游戏 |
您所在的位置：网站首页 › 数独游戏对数学的帮助 › C语言实现数独游戏 |
C语言实现数独游戏
|
一、功能： （1）输出排名 从文件中读出数据，保存在单链表中，并利用选择排序对数据进行排序后输出。 （2）开始游戏 进入该游戏系统后，系统先随机创建一个唯一解的数独，并解出该数独答案。 （3）选择难度 根据玩家选择的难度，挖空系统已经解出的数独，比如选择简单（给出40个数），则把系统已经解出的答案随机挖空41格，挖空处用数字0代替。 （4）给出数独并开始作答 玩家得到题目后进行解答（解答需将数独完整写一遍，以空格分割每列，以回车分割每行），最后系统根据答案判断玩家解答是否正确，正确则输出所用时间，如果该玩家是新纪录，则还要记录到文件，如果玩家解答错误，则失败并给出正确答案。 功能结构图：
二、涉及数据结构： 十字双向循环链表 三、涉及算法： DLX算法 如何将数独转化为精准覆盖问题，并用DLX算法去解 数据结构体设计： ①玩家游戏记录信息 四、实验环境： 使用语言：C 使用软件：Microsoft Visual C++ 6.0 五、功能截图： 六、具体代码： #include #include #include #include #include #include #include #define MAX 999 struct Node{ Node *up,*down,*left,*right,*colPtr,*rowPtr;//指向row,col对应的行对象和列对象 int row_num;//记录行数，行专属(从1开始) int col_elemCount;//记录该列元素个数，列专属 }; struct player{//玩家信息结点 int m ; int s ; char name[20]; int level ; player* next; }; int row_size=593;//行数 int col_size = 324;//列数 int result[81];//存放结果行的栈 int index = 0;//栈指针 int sudoku[81] = {0};//存放数独 int time_start = 0; int time_end = 0;//起始时间 void init(Node* head){ head->left = head; head->right = head; head->up = head; head->down = head; for(int k = 0;k up = head; newNode->down = head->down; newNode->left = newNode; newNode->right = newNode; newNode->down->up = newNode; head->down = newNode; newNode->row_num = row_size-k; newNode->col_elemCount = 0;//借用，作为标志 } } void init_col(Node* head){ /************初始化行列对象*******************/ for(int j = 0;j right = head->right; newNode->left = head; newNode->down = newNode; newNode->up = newNode; newNode->right->left = newNode; head->right = newNode; newNode->col_elemCount = 0;//列元素个数初始为0 } } void link(Node* head,int** matrix){ /***********插入结点*************/ Node *current_row, *current_col, *current;//当前行对象,当前列对象,当前节点 current_row = head; for(int row = 0;rowdown; current_col = head; for(int col = 0;colright; if(matrix[row][col] == 0) continue; /*****插入结点，结点的行和列都用尾插法来与行列对象链接*****/ Node* newNode = (Node*)malloc(sizeof(Node)); newNode->colPtr = current_col;//设置节点对应的行和列 newNode->rowPtr = current_row; /**********列尾插************/ newNode->down = current_col; newNode->up = current_col->up; newNode->up->down = newNode; current_col->up = newNode;//链接当前节点到列双向链尾端 if(current_row->col_elemCount == 0){//行的这个为0,说明该行还没有元素，行双向链表不把行对象包含进来(便于后面覆盖) current_row->right = newNode; newNode->left = newNode; newNode->right = newNode; current_row->col_elemCount++;//此为标志，为了不把行对象包含进来 } current = current_row->right; newNode->left = current->left; /**********行尾插************/ newNode->right = current; newNode->left->right = newNode; current->left = newNode;//链接当前节点到行双向链尾端 current_col->col_elemCount++;//该列元素加1 } } } int** create_matrix()//将数独转换为01矩阵 { int** matrix = (int**)malloc(row_size*sizeof(int*));//申请二维数组空间 for(int m=0;mleft = cRoot->left;//删除该列对象，及该列结点的每行结点 Node *i, *j; i = cRoot->down; while (i != cRoot) { j = i->right; while (j != i) { j->down->up = j->up; j->up->down = j->down; j->colPtr->col_elemCount--; j = j->right; } i = i->down; } } void recover(Node* cRoot){//回溯 Node *i, *j; i = cRoot->up; while (i != cRoot) { j = i->left; while (j != i) { j->colPtr->col_elemCount++; j->down->up = j; j->up->down = j; j = j->left; } i = i->up; } cRoot->right->left = cRoot; cRoot->left->right = cRoot; } bool search(Node* head){ if(head->right == head){ return true; } Node *cRoot, *c; int minSize = MAX;//最少列元素个数 for(c = head->right; c != head; c = c->right)//先选择列元素最少的列对象（提高效率） { if (c->col_elemCount col_elemCount; cRoot = c; if (minSize == 1)//1是最小 break; if (minSize == 0)//有一列为空,失败 return false; } } cover(cRoot); Node *current_row,*current; for (current_row = cRoot->down; current_row != cRoot; current_row = current_row->down) { result[index]=current_row->rowPtr->row_num;//将该行加入result中(行数) index++; for (current = current_row->right; current != current_row; current = current->right) { cover(current->colPtr); } if (search(head))//递归 return true; for (current = current_row->left; current != current_row; current = current->left) recover(current->colPtr); index--;//发现该行不符合要求,出栈 } recover(cRoot); return false; } int* to_sudoku(int** matrix){//01矩阵转化为数独 int* done = (int*)malloc(81*sizeof(int)); int temp[162]={0}; for(int i = 0;im==q->m&&p->s>q->s)){//对换两个结点的内容 temp1 = p->m; temp2 = p->s; strcpy(temp3,p->name); p->m = q->m; p->s = q->s; strcpy(p->name,q->name); q->m = temp1; q->s = temp2; strcpy(q->name,temp3); } } void show(player* easy,player* normal,player* hard){//输出排行 int no=1; player* p1 = easy->next; player* p2 = normal->next; player* p3 = hard->next; printf("==========================================================================\n"); printf("\t\t 简单\t\t\t 一般\t\t\t 困难\n"); while(p1 != NULL || p2 != NULL || p3 != NULL){ printf("NO.%d",no++); if(p1 != NULL){ printf("\t\t%s\t%d:%d\t",p1->name,p1->m,p1->s); p1 = p1->next; } if(p2 != NULL){ printf("\t%s\t%d:%d\t",p2->name,p2->m,p2->s); p2 = p2->next; } if(p3 != NULL){ printf("\t%s\t%d:%d\t",p3->name,p3->m,p3->s); p3 = p3->next; } printf("\n"); } } void re_init(Node* head){//重新初始化行和列对象 Node* p; for(p = head->down;p!=head;p=p->down) p->col_elemCount = 0; if(head->right == head){//如果有解，则列对象会在search中被删除，需要重新链接列对象 init_col(head); return; } for(p = head->right;p!=head;p=p->right){//无解时,则恢复列对象 p->col_elemCount = 0; p->down = p; p->up = p; } } void main(){ int player_res[81]={0}; int choice; int** matrix;//存放数独的01矩阵 int* answer;//存放答案 player* easy;//容易难度排行 player* normal;//简单难度排行 player* hard;//困难难度排行 player info ;//玩家信息 Node* head =(Node*)malloc(sizeof(Node)); init(head);init_col(head);//初始化行列对象，建立十字双向循环链表 srand(time(NULL)); bool flag = false;//有无解 while(true){ while(!flag){ flag=true; create_sudoku();//创建17个数的数独（17个数及以上唯一解） matrix = create_matrix();//得到该数独的01矩阵 link(head,matrix);//将01矩阵转化为十字双向循环链表（转化为精准覆盖问题） if(!search(head))//得到答案行（result） flag = false;//如果不幸无解，则重新构建数独（经本人测试，无解的概率大概为1/1000） index = 0;//初始化result栈 re_init(head);//重新初始化十字链表 } flag = false; answer = to_sudoku(matrix);//得到答案 printf(" 数独\n"); printf("==========================================================================\n\n"); printf("1.开始游戏\n"); printf("2.查看排名\n"); printf("3.退出\n\n"); printf("==========================================================================\n"); printf("请选择:"); scanf("%d",&choice); switch(choice){ case 1: int option; printf("玩家名:"); scanf("%s",&info.name); if(strlen(info.name)>20){ printf("名字太长！\n"); break; } printf("请选择游戏难度: 1.简单\t2.一般\t3.困难\n"); scanf("%d",&option); printf("\n"); switch(option){ case 1: sudoku_level(answer,40);//挖空答案 ready(); time_start = get_time(); if(!receiver(player_res)){ printf("\n您已放弃作答!\t正确答案为:\n\n"); print(answer); break; } time_end = get_time(); info.m = (time_end-time_start)/60; info.s = (time_end-time_start)%60; info.level = 1; if(judge(player_res,answer)){ printf("回答正确!\t用时: %d:%d\n",info.m,info.s); record(info); } else { printf("\n回答错误!\t正确答案为:\n\n"); fflush(stdin); print(answer); } break; case 2: sudoku_level(answer,35); time_start = get_time(); ready(); if(!receiver(player_res)){ printf("\n您已放弃作答!\t正确答案为:\n\n"); print(answer); break; } time_end = get_time(); info.m = (time_end-time_start)/60; info.s = (time_end-time_start)%60; info.level = 2; if(judge(player_res,answer)){ printf("回答正确!\t用时: %d:%d\n",info.m,info.s); record(info); } else { printf("回答错误!\t正确答案为:\n\n"); fflush(stdin); print(answer); } break; case 3: sudoku_level(answer,30); time_start = get_time(); ready(); if(!receiver(player_res)){ printf("\n您已放弃作答!\t正确答案为:\n\n"); print(answer); break; } time_end = get_time(); info.m = (time_end-time_start)/60; info.s = (time_end-time_start)%60; info.level = 3; if(judge(player_res,answer)){ printf("回答正确!\t用时: %d:%d\n",info.m,info.s); record(info); } else { printf("回答错误!\t正确答案为:\n\n"); fflush(stdin); print(answer); } break; default: printf("no option!\n"); fflush(stdin); break; } break; case 2: easy = get_record(1); normal = get_record(2); hard = get_record(3); order(easy); order(normal); order(hard); show(easy,normal,hard); break; case 3: printf("\n拜拜~\n\n"); exit(0); default: printf("no option!\n"); fflush(stdin); break; } system("pause"); system("cls"); } } (转载请说明出处) |
②存储数独结点信息 
【本文地址】
今日新闻 |
推荐新闻 |