? ? ? ? ?首先因?yàn)閭€(gè)人原因前段時(shí)間在解一個(gè)數(shù)獨(dú)，因?yàn)楹茈y解不出來，再加上我王哥的啟發(fā)，就想的寫個(gè)程序來解決這類問題，于是就有了這篇文章。。。還有最近在學(xué)數(shù)據(jù)結(jié)構(gòu)，里面很多東西用的都是比較繁瑣的解決辦法，比如鏈?zhǔn)酱鎯?chǔ)，鏈棧之類的，但這樣思路比較清晰。

? ? ? ? ? ? ? ?1.程序大致思路

? ? ? ? ?將數(shù)組元素全部初始化為0，然后將空位的行列入棧，然后開始給棧頂元素的空位逐步++；每次++都要判斷這個(gè)數(shù)填在這個(gè)空位合不合適，合適的話入棧下一個(gè)元素，否則就出棧，這樣就回溯到了上一個(gè)空位，繼續(xù)++，這樣當(dāng)最后一個(gè)空位解決后，就出現(xiàn)了數(shù)獨(dú)的第一個(gè)解，然后解決多解的話，將此時(shí)的棧頂元素出棧，給棧頂元素++，將指針指向上一個(gè)空位，利用goto語句來實(shí)現(xiàn)數(shù)獨(dú)的多解；

? ? ? ? ? ? ? 2.代碼改進(jìn)思路

? ? ? ? ? 如果不用數(shù)據(jù)結(jié)構(gòu)的鏈棧知識(shí)的話，可將棧直接簡化成 s[M],top來進(jìn)行出入棧操作，這樣代碼的行數(shù)將大大減少。

? ? ? ? ? ? ? 3.程序功能：

? ? ? ? ? 可以進(jìn)行數(shù)獨(dú)的解（多解）。

? ? ? ? ? ?如果出現(xiàn)解比較多的數(shù)獨(dú)，機(jī)器運(yùn)行時(shí)間比較長；

? ? ? ? ? ? ? 4.關(guān)鍵代碼解析

?????????利用while進(jìn)入循環(huán)（注：因?yàn)檠h(huán)條件是p->next!=NULL，如果循環(huán)條件是p!=NULL的話，當(dāng)指針p指向鏈表的最后一個(gè)元素的話，進(jìn)入這條語句，最后一個(gè)空位肯定合適，所以指針p還會(huì)往后移一個(gè)，所以就找不到p的位置了，也就無法回溯（p=p->before）；所以解決辦法就是p->next!=NULL，并且存鏈表的時(shí)候在末端多存一個(gè)垃圾值）；循環(huán)里面入棧，然后進(jìn)行do while先從0++一次，然后通過qualified函數(shù)判斷空位能不能填這個(gè)數(shù)字，能的話返回0跳出循環(huán)，不能繼續(xù)do while。然后通過if判斷，是通過怎樣的方式跳出循環(huán)的：if跳出循環(huán)后a[row1][list1]<10就證明，這個(gè)數(shù)字可以填在此時(shí)的空位，則指針往后移動(dòng)，下一個(gè)入棧，else則說明1-9沒有合適的數(shù)字填到這個(gè)空位，則給這個(gè)空位初始化為0，出棧，將指針回調(diào)，繼續(xù)循環(huán)。

? ? ? ? ? ? ? ? ? 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 //申明一個(gè)棧 {LinkList *top;LinkList *bottom; }LinkStack;typedef struct nood_1 // 申明一個(gè)雙鏈表 {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) //把數(shù)獨(dú)空位的行列保存到雙鏈表里方便操作 {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() //打印此時(shí)數(shù)獨(dú)的結(jié)果 {int i,j;printf("數(shù)獨(dú)結(jié)果為:\n");for(i=0;i<9;i++){for(j=0;j<9;j++){if(a[i][j]==0){printf("| "); }elseprintf("|%2d ",a[i][j]);if(j==8)printf("|");}printf("\n\n");} }int qualified(int x,int row,int list) //判斷填的數(shù)字在這個(gè)空位的 行、 列 、九宮格是否合適 { 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) //利用回溯法開始對數(shù)獨(dú)的空位逐個(gè)解決 {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("這個(gè)數(shù)獨(dú)的第%d個(gè)解為:\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("這個(gè)數(shù)獨(dú)無解\n"); }

? ? ? ? ? ? ? ? ? ? ?6.程序待解決的問題：

? ? 出現(xiàn)無解，他會(huì)直接退出程序，并不會(huì)提示，程序的時(shí)間復(fù)雜度也比較高

? ? ? ? ? ? ? ? ? ? ?7.數(shù)獨(dú)提供樣例：

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 00 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

這里特別感謝我王哥的幫助，沒他就沒這些思路和BUG的解決，程序也有太多問題，如果有大佬發(fā)現(xiàn)問題或者有更好的解決辦法的話滴滴我，感謝感謝！！！

總結(jié)

以上是生活随笔為你收集整理的数独解、多解（数据结构、栈、回溯法）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。