/*
我花了3个小时解决了这个问题！激动呀！这是我对朋友们的挑战！因为他们说这个问题根本就没办法解决！
这是手机上的一个游戏《数字九宫格》英文名字叫“Sudoku”，估计大家都玩过！这个游戏对智力是个很大
的挑战！我很想在两分总之内就能把格子全填上，但是我的脑袋却没有那样的智商，只好写个程序让电脑
帮帮我了！(*^__^*) 嘻嘻……
程序的思路就是栈，核心算法是最后的test函数！本来我想用递归的思路，但是没有找到递归的终止条件，
只好用栈了！
或者访问我的博客吧，在google中搜索“风中之哨”，排名第一的就是！！！
多捧场哦！朋友们！
程序使用方法：把九宫格已经给出的数字填到下边的二维数组中，没有给出的用0代替！如下例！
coder_jack@ 于上海贝尚通讯 0911
*/
本文来自CSDN博客，转载请标明出处：/coder_jack/archive//05/27/5629224.aspx
#include
#include
#include
//这是个例子，里面的值换一下就好了！九宫格的解可能是唯一的，所以不要胡乱填写！否则容易无解
//如果你的智商达不到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<
}
//________________________________________
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<
}
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");
getchar();getchar();getchar();
}
//code--END
