手机智力游戏 数字九宫格 sudoku 求解算法 源码 程序

/* 我花了3个小时解决了这个问题！激动呀！这是我对朋友们的挑战！因为他们说这个问题根本就没办法解决！ 这是手机上的一个游戏《数字九宫格》英文名字叫“Sudoku”，估计大家都玩过！这个游戏对智力是个很大 的挑战！我很想在两分总之内就能把格子全填上，但是我的脑袋却没有那样的智商，只好写个程序让电脑 帮帮我了！(*^__^*) 嘻嘻…… 程序的思路就是栈，核心算法是最后的test函数！本来我想用递归的思路，但是没有找到递归的终止条件， 只好用栈了！ 需要的话和我交流了！邮箱：coder_jack@126.com 或者访问我的博客吧，在google中搜索“风中之哨”，排名第一的就是！牛X吧！！！ 多捧场哦！朋友们！ 程序使用方法：把九宫格已经给出的数字填到下边的二维数组中，没有给出的用0代替！如下例！ 20090911 coder_jack@126.com于上海贝尚通讯 */ //VC6.0下编译测试 #include <iostream.h> #include <stdlib.h> #include <stdio.h> //这是个例子，里面的值换一下就好了！九宫格的解可能是唯一的，所以不要胡乱填写！否则容易无解 //如果你的智商达不到99%的话最好照着手机上的初始内容填写，没有数字的地方用0代替， int ar_99[9][9]={ 9,0,5,0,0,0,0,0,8, 4,0,0,5,7,0,1,0,6, 0,2,7,6,0,0,0,4,0, 0,9,6,0,0,3,5,1,2, 7,0,4,0,1,0,3,0,0, 2,1,0,9,8,0,0,0,4, 0,8,1,0,0,4,0,9,0, 3,0,0,8,0,0,0,5,1, 0,0,2,0,0,7,0,6,0}; //--------------------------------构造栈-------------------------------- class stack { private: struct node { int x; int y; node* next; }; public: node *head; stack() { head = NULL; } ~stack() { node* p=head; while(head!=NULL) { head=head->next; delete p; p=head; } } void push(int xx, int yy) { node* new_node; new_node=new node; if(new_node!=NULL) { new_node->x=xx; new_node->y=yy; new_node->next=NULL; if(head==NULL) head=new_node; else { new_node->next=head; head=new_node; } } else cout<<"\n因为内存分配失败导致本次压栈失败！！！\n"; } //________________________________________ node* pop(int& xx,int& yy)//出栈时带回栈顶元素坐标 { if(head!=NULL) { node* p=head; head=head->next; xx=p->x; yy=p->y; delete p; } else { cout<<"\n因为栈已空导致本次出栈失败\n"; } return head;//每次出栈后返回新的栈定指针 } }; //------------------实例化一个栈---------------------------------- stack my_stack; //------------------构造Sudoku----------------------------------- void make_ar(void) { int x; int y; for (x=0;x<=8;x++) { printf("现在开始输入第 %d 行的数字，手机没有给出的用0代替，输入一个回车一下！\n",x+1); for (y=0;y<=8;y++) { printf("第 %d 行 第 %d 个 =",x+1,y+1); scanf("%d",&ar_99[x][y]); } } } //------------------输出Sudoku------------------------------------ void print_ar() { int x; int y; printf("\n ───────────────────\n │"); for (x=0;x<=8;x++) { for (y=0;y<=8;y++) { if(0==ar_99[x][y]) printf(" │"); else printf("% d│",ar_99[x][y]); } printf("\n ───────────────────\n │"); } printf("\b "); } //以下是核心代码！！！！！！ //----------------------行适应性判定-------------------------------- int line_ok(int x, int y) { int i; for(i=0;i<=8;i++) { if (y==i) continue; else if(ar_99[x][i]==ar_99[x][y]) return 0; } return 1; } //-----------------------列适应性判定---------------------------------- int column_ok(int x, int y) { int i; for(i=0;i<=8;i++) { if (x==i) continue; else if(ar_99[i][y]==ar_99[x][y]) return 0; } return 1; } //--------------------组适应性判定---------------------------------- int group_ok(int x, int y) { int field_x; int field_y; int select; int xx, yy; if(x<=2) field_x = 0; else if(x<=5) field_x = 1; else field_x = 2; if(y<=2) field_y = 0; else if(y<=5) field_y = 1; else field_y = 2; if(0==field_x && 0==field_y) select = 0; if(0==field_x && 1==field_y) select = 1; if(0==field_x && 2==field_y) select = 2; if(1==field_x && 0==field_y) select = 3; if(1==field_x && 1==field_y) select = 4; if(1==field_x && 2==field_y) select = 5; if(2==field_x && 0==field_y) select = 6; if(2==field_x && 1==field_y) select = 7; if(2==field_x && 2==field_y) select = 8; switch(select) { case 0: for(xx=0;xx<=2;xx++) for(yy=0;yy<=2;yy++) { if(xx==x && yy==y) continue; else if(ar_99[x][y]==ar_99[xx][yy]) return 0; }break; //---------------------------------------------------------------------------- case 1: for(xx=0;xx<=2;xx++) for(yy=3;yy<=5;yy++) { if(xx==x && yy==y) continue; else if(ar_99[x][y]==ar_99[xx][yy]) return 0; }break; //---------------------------------------------------------------------------- case 2: for(xx=0;xx<=2;xx++) for(yy=6;yy<=8;yy++) { if(xx==x && yy==y) continue; else if(ar_99[x][y]==ar_99[xx][yy]) return 0; }break; //---------------------------------------------------------------------------- case 3: for(xx=3;xx<=5;xx++) for(yy=0;yy<=2;yy++) { if(xx==x && yy==y) continue; else if(ar_99[x][y]==ar_99[xx][yy]) return 0; }break; //---------------------------------------------------------------------------- case 4: for(xx=3;xx<=5;xx++) for(yy=3;yy<=5;yy++) { if(xx==x && yy==y) continue; else if(ar_99[x][y]==ar_99[xx][yy]) return 0; }break; //---------------------------------------------------------------------------- case 5: for(xx=3;xx<=5;xx++) for(yy=6;yy<=8;yy++) { if(xx==x && yy==y) continue; else if(ar_99[x][y]==ar_99[xx][yy]) return 0; }break; //---------------------------------------------------------------------------- case 6: for(xx=6;xx<=8;xx++) for(yy=0;yy<=2;yy++) { if(xx==x && yy==y) continue; else if(ar_99[x][y]==ar_99[xx][yy]) return 0; }break; //---------------------------------------------------------------------------- case 7: for(xx=6;xx<=8;xx++) for(yy=3;yy<=5;yy++) { if(xx==x && yy==y) continue; else if(ar_99[x][y]==ar_99[xx][yy]) return 0; }break; //---------------------------------------------------------------------------- case 8: for(xx=6;xx<=8;xx++) for(yy=6;yy<=8;yy++) { if(xx==x && yy==y) continue; else if(ar_99[x][y]==ar_99[xx][yy]) return 0; }break; //---------------------------------------------------------------------------- } return 1; } //------------------------------------------------------------------- int test()//最最核心代码！！！！算法！！！！ { int x; int y; for (x=0;x<=8;x++) { for (y=0;y<=8;y++) { if (0==ar_99[x][y]) { for (;1;) { (ar_99[x][y])++; if (column_ok(x,y)&&line_ok(x,y)&&group_ok(x,y)) { my_stack.push(x,y);//进栈 break; } else if (9==ar_99[x][y]) { labe: ar_99[x][y]=0; if(my_stack.head==NULL)return -1; my_stack.pop(x,y); //出栈 if (9==ar_99[x][y]) goto labe; } } } else continue; } } return 0; } //核心代码到此结束 //------------------------------------------------------------------ void main() { //make_ar(); //如果你打算在程序运行时才开始输入数据的话把这个函数启用！ printf("\n\n\n原始九宫格\n"); print_ar(); printf("\n"); if (test()==-1) { printf("\n尝试完毕，很遗憾，此题无解！\n"); } printf("填充完毕后的九宫格\n"); print_ar(); printf("\n访问我的博客吧，在google中搜索“风中之哨”，排名第一的就是！牛X吧！！！\n"); ge