? ? ? ? ?首先因为个人原因前段时间在解一个数独，因为很难解不出来，再加上我王哥的启发，就想的写个程序来解决这类问题，于是就有了这篇文章。。。还有最近在学数据结构，里面很多东西用的都是比较繁琐的解决办法，比如链式存储，链栈之类的，但这样思路比较清晰。
? ? ? ? ? ? ? ?1.程序大致思路
? ? ? ? ?将数组元素全部初始化为0，然后将空位的行列入栈，然后开始给栈顶元素的空位逐步++；每次++都要判断这个数填在这个空位合不合适，合适的话入栈下一个元素，否则就出栈，这样就回溯到了上一个空位，继续++，这样当最后一个空位解决后，就出现了数独的第一个解，然后解决多解的话，将此时的栈顶元素出栈，给栈顶元素++，将指针指向上一个空位，利用goto语句来实现数独的多解；
? ? ? ? ? ? ? 2.代码改进思路
? ? ? ? ? 如果不用数据结构的链栈知识的话，可将栈直接简化成 s[M],top来进行出入栈操作，这样代码的行数将大大减少。
? ? ? ? ? ? ? 3.程序功能：
? ? ? ? ? 可以进行数独的解（多解）。
? ? ? ? ? ?如果出现解比较多的数独，机器运行时间比较长；
? ? ? ? ? ? ? 4.关键代码解析
????????
?利用while进入循环（注：因为循环条件是p->next!=NULL，如果循环条件是p!=NULL的话，当指针p指向链表的最后一个元素的话，进入这条语句
，最后一个空位肯定合适，所以指针p还会往后移一个，所以就找不到p的位置了，也就无法回溯（p=p->before）；所以解决办法就是p->next!=NULL，并且存链表的时候在末端多存一个垃圾值）；循环里面入栈，然后进行do while先从0++一次，然后通过qualified函数判断空位能不能填这个数字，能的话返回0跳出循环，不能继续do while。然后通过if判断，是通过怎样的方式跳出循环的：if跳出循环后a[row1][list1]<10就证明，这个数字可以填在此时的空位，则指针往后移动，下一个入栈，else则说明1-9没有合适的数字填到这个空位，则给这个空位初始化为0，出栈，将指针回调，继续循环。
? ? ? ? ? ? ? ? ? 5.程序源代码：
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
int a[9][9]={0};
typedef struct nood
{
int row;
int list;
struct nood *next;
}LinkList;
typedef struct Stack //申明一个栈
{
LinkList *top;
LinkList *bottom;
}LinkStack;
typedef struct nood_1 // 申明一个双链表
{
int row;
int list;
struct nood_1 *next;
struct nood_1 *before;
}DulLinkList;
void init_Stack(LinkStack *s) // 栈的初始化
{
s->top=(LinkList *)malloc(sizeof(LinkList));
s->bottom=s->top;
s->top->next=NULL;
}
DulLinkList *init_DulLinkList(DulLinkList *head) //双链表的初始化
{
head=(DulLinkList *)malloc(sizeof(DulLinkList));
head->next=NULL;
head->before=NULL;
return head;
}
void push_Stack(LinkStack *s,int row1,int list1) //入栈操作
{
LinkList *p;
p=(LinkList *)malloc(sizeof(LinkList));
p->row=row1;
p->list=list1;
p->next=s->top;
s->top=p;
}
void push_DulLinkList(DulLinkList *head,int row1,int list1) //把数独空位的行列保存到双链表里方便操作
{
DulLinkList *p,*r;
r=head;
while(r->next!=NULL)
{
r=r->next;
}
p=(DulLinkList *)malloc(sizeof(DulLinkList));
p->row=row1;
p->list=list1;
r->next=p;
p->before=r;
p->next=NULL;
}
int empty_Stack(LinkStack *s) //栈的判空
{
if(s->top==s->bottom)
return 1;
else return 0;
}
void pull_Stack(LinkStack *s,int *row1,int *list1) // 出栈操作
{
LinkList *p;
p=s->top;
*row1=p->row;
*list1=p->list;
s->top=p->next;
free(p);
}
void print_shudu() //打印此时数独的结果
{
int i,j;
printf("数独结果为:\n");
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
if(a[i][j]==0)
{
printf("| ");
}
else
printf("|%2d ",a[i][j]);
if(j==8)
printf("|");
}
printf("\n\n");
}
}
int qualified(int x,int row,int list) //判断填的数字在这个空位的 行、 列 、九宫格是否合适
{
int i,j,f1,f2;
for(i=0;i<row;i++)
if(a[i][list]==x)
return 1;
for(i=row+1;i<9;i++)
if(a[i][list]==x)
return 1;
for(i=0;i<list;i++)
if(a[row][i]==x)
return 1;
for(i=list+1;i<9;i++)
if(a[row][i]==x)
return 1;
f1=row-row%3;
f2=list-list%3;
for(i=f1;i<f1+3;i++)
{
for(j=f2;j<f2+3;j++)
{
if((i!=row)||(j!=list))
{
if(a[i][j]==x)
return 1;
}
}
}
return 0;
}
int jie(LinkStack *s,DulLinkList *head) //利用回溯法开始对数独的空位逐个解决
{
int i,j,row1,list1,flag=1,c1,c2;
DulLinkList *p,*q;
q=head;
p=head->next;
f1: while(p->next!=NULL)
{
push_Stack(s,p->row,p->list);
row1=s->top->row;
list1=s->top->list;
do
{
a[row1][list1]++;
}
while(a[row1][list1]<10 && qualified(a[row1][list1],row1,list1));
if(a[row1][list1]<10)
{
p=p->next;
}
else
{
a[row1][list1]=0;
pull_Stack(s,&c1,&c2);
p=p->before;
}
}
if(p!=q)
{
printf("这个数独的第%d个解为:\n",flag);
print_shudu();
}
if(p==q)
return 0;
else
{
pull_Stack(s,&c1,&c2);
a[c1][c2]++;
p=p->before;
flag++;
goto f1;
}
}
int main()
{
LinkStack S;
DulLinkList *L;
int i,j;
init_Stack(&S);
L=init_DulLinkList(L);
printf("please enter a sudoku :\n");
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
scanf("%d",&a[i][j]);
if(a[i][j]==0)
{
push_DulLinkList(L,i,j);
}
}
}
push_DulLinkList(L,-1,-1);
system("CLS");
print_shudu();
if(jie(&S,L)==0)
printf("这个数独无解\n");
} ? ? ? ? ? ? ? ? ? ? ?6.程序待解决的问题：
? ? 出现无解，他会直接退出程序，并不会提示，程序的时间复杂度也比较高
? ? ? ? ? ? ? ? ? ? ?7.数独提供样例：
3 0 6 4 5 1 8 7 9
0 4 5 7 0 9 2 0 0
7 0 9 2 0 0 1 4 5
0 0 3 5 4 7 6 9 0
0 0 0 0 9 0 0 1 2
6 0 8 0 2 3 4 0 0
5 0 1 0 0 2 9 6 4
8 6 4 0 0 5 7 2 3
9 7 2 3 6 4 0 8 0
0 0 0 5 0 0 9 2 7
2 3 0 1 7 9 0 6 0
0 0 0 0 4 0 0 3 5
1 0 3 4 0 0 0 0 0
0 0 0 0 0 8 0 0 0
8 0 0 0 0 2 0 0 0
0 1 4 7 2 0 0 0 6
6 0 0 9 3 1 7 0 0
0 7 2 8 0 4 0 0 0
0 0 0 0 0 0 0 0 0
0 8 0 0 7 0 0 3 0
0 0 0 0 0 0 0 0 0
7 0 0 0 1 0 0 0 3
0 0 0 0 0 6 0 0 0
0 0 2 0 0 0 4 0 0
0 0 0 0 5 0 0 0 0
0 4 0 0 6 0 0 9 0
6 0 0 0 0 0 3 0 0