題目大意：給出一道數(shù)獨(dú)題，判斷該數(shù)獨(dú)是否有解且有唯一解。

解題思路：

　　由前幾題的難度得，此題的難度不會(huì)太過(guò)分，所以簡(jiǎn)單暴力就可以了，40ms用時(shí)一本滿足。

　　簡(jiǎn)單地講一下具體的實(shí)現(xiàn)，從左上開(kāi)始從左到右從上到下一格一格枚舉過(guò)去，枚舉當(dāng)前格子的數(shù)字時(shí)，判斷一下這個(gè)數(shù)字能不能用就行了（判斷是否在該行，該列，該區(qū)域出現(xiàn)過(guò)），全部填滿時(shí)就找到了一個(gè)解，找到第二個(gè)解的時(shí)候停止搜索即可。

　　關(guān)于判斷某個(gè)數(shù)字在當(dāng)前區(qū)域是否用過(guò)，比較方便的方法是，事先算好p[i][j]，用來(lái)記錄第i行第j格屬于哪一列，哪一行，哪一區(qū)域，這樣在寫(xiě)dfs時(shí)會(huì)方便很多。

代碼：

/*
被注釋掉的代碼都是用來(lái)調(diào)試的，取消注釋后可以用來(lái)查看程序運(yùn)行過(guò)程以便調(diào)試。
*/#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define MST(a,b) memset(a,b,sizeof(a))
#define MAXL 10
int error;//用于發(fā)現(xiàn)不合理時(shí)終止程序
int g[MAXL][MAXL];//存放數(shù)組初始狀態(tài)
int p1[MAXL][MAXL],p2[MAXL][MAXL],p3[MAXL][MAXL];//分別記錄(i,j)所對(duì)應(yīng)的行，列，區(qū)域
int b1[MAXL][MAXL],b2[MAXL][MAXL],b3[MAXL][MAXL];//記錄編號(hào)為i的行，列，區(qū)域的數(shù)字使用情況
void init()//讀入部分
{error=0;FOR(i,1,9)FOR(j,1,9)scanf("%d",&g[i][j]);MST(b1,0);MST(b2,0);MST(b3,0);FOR(i,1,9)FOR(j,1,9)if(g[i][j]){int p=p1[i][j],x=g[i][j];if(b1[p][x])error=1;b1[p][x]=1;p=p2[i][j];if(b2[p][x])error=1;b2[p][x]=1;p=p3[i][j];if(b3[p][x])error=1;b3[p][x]=1;}
}
int g2[MAXL][MAXL];//調(diào)試時(shí)用的數(shù)組，可無(wú)視
int tot;//記錄解的個(gè)數(shù)
void dfs(int x,int y)
{if(x==10)//dfs到第10行意味著已經(jīng)全部填滿
    {tot++;if(tot>1)error=1;//若發(fā)現(xiàn)第二個(gè)解則終止程序/*FOR(i,1,9){FOR(j,1,9)printf("%d ",g2[i][j]+g[i][j]);printf("\n");}printf("\n");*/return;}int xt=x,yt=y+1;//計(jì)算下一個(gè)if(yt>9){xt++;yt=1;}if(g[x][y]){dfs(xt,yt);return;}//若該格已有數(shù)字則無(wú)需嘗試，直接進(jìn)入下一格int c1=p1[x][y],c2=p2[x][y],c3=p3[x][y];//記錄當(dāng)前格所在的行，列，區(qū)域的編號(hào)FOR(i,1,9)if(b1[c1][i]+b2[c2][i]+b3[c3][i]==0)//是否在當(dāng)前行，列，區(qū)域都未使用
    {b1[c1][i]=1;b2[c2][i]=1;b3[c3][i]=1;//g2[x][y]=i;dfs(xt,yt);//進(jìn)入下一格繼續(xù)嘗試//g2[x][y]=0;if(error)return;b1[c1][i]=0;b2[c2][i]=0;b3[c3][i]=0;}
}
void work()//計(jì)算部分g2和輸出error什么的請(qǐng)無(wú)視
{MST(g2,0);tot=0;dfs(1,1);//if(error)printf("error");if(tot==0 || error)printf("No\n");else printf("Yes\n");
}
int main()
{freopen("in.txt","r",stdin);//文件輸入以便調(diào)試//freopen("out.txt","w",stdout);FOR(i,1,9)FOR(j,1,9)p1[i][j]=i;FOR(i,1,9)FOR(j,1,9)p2[i][j]=j;FOR(i,1,9)FOR(j,1,9)p3[i][j]=((i-1)/3)*3+((j-1)/3)+1;//預(yù)處理i,j所在區(qū)域/*FOR(i,1,9){FOR(j,1,9)printf("%d ",p3[i][j]);printf("\n");}*///上面的代碼用來(lái)檢查預(yù)處理時(shí)有無(wú)算錯(cuò)，下面開(kāi)始是正片int nn;scanf("%d",&nn);FOR(ii,1,nn){init();if (error){printf("No\n");continue;}work();}}

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/USTC-ACM/archive/2013/03/12/2955423.html

總結(jié)

以上是生活随笔為你收集整理的上交三月月赛[SJTU] 1106 sudoku的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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