今天的題取自我們學(xué)校的BNDSOJ網(wǎng)站：

BNDS校園吉尼斯開展解數(shù)獨(dú)比賽，數(shù)獨(dú)游戲的規(guī)則是這樣的：在一個(gè)9x9的方格中，你需要把數(shù)字1-9填寫到空格當(dāng)中，并且使方格的每一行和每一列中都包含1-9這九個(gè)數(shù)字。同時(shí)還要保證，空格中用粗線劃分成9個(gè)3x3的方格也同時(shí)包含1-9這九個(gè)數(shù)字。

現(xiàn)在BNDS信息學(xué)競(jìng)賽班的學(xué)生需要用編程解決數(shù)獨(dú)問題。輸入一個(gè)9*9的數(shù)字序列，其中空位用0表示。輸出解答之后的數(shù)字序列

示例輸入：

0 1 2 0 6 0 3 5 8
0 6 5 2 0 7 1 0 4
4 0 8 0 1 3 6 7 2
9 2 4 0 5 6 0 3 7
5 0 6 0 0 0 2 4 1
1 0 3 7 2 0 9 0 5
0 0 1 9 7 5 4 8 6
6 0 7 0 3 0 5 1 9
8 5 9 0 4 0 0 2 3

示例輸出：

7 1 2 4 6 9 3 5 8
3 6 5 2 8 7 1 9 4
4 9 8 5 1 3 6 7 2
9 2 4 1 5 6 8 3 7
5 7 6 3 9 8 2 4 1
1 8 3 7 2 4 9 6 5
2 3 1 9 7 5 4 8 6
6 4 7 8 3 2 5 1 9
8 5 9 6 4 1 7 2 3

首先是讀題。我作為一個(gè)從來沒有玩過數(shù)獨(dú)的人，只能先把輸入的樣例解出來，然后再研究規(guī)律。按照題意，一個(gè)3*3的方格里會(huì)有1-9的數(shù)字，橫豎都是1-9九個(gè)數(shù)字的排列。所以我應(yīng)該有三套for循環(huán)來篩選出可能能填的數(shù)。然后就是逐漸排查唄。先把能夠直接確定的數(shù)據(jù)填寫上，然后再逐漸的往上找。最后就可以確定整個(gè)數(shù)獨(dú)的所有數(shù)據(jù)了。

多簡(jiǎn)單呀（記住我說的話）

早些時(shí)候我寫出來的那些連一個(gè)格子都沒法填的程序現(xiàn)在已經(jīng)無從考證了。講真，光是將最簡(jiǎn)單的數(shù)獨(dú)填出來就用了一個(gè)下午。我真的沒想到還會(huì)有最開始讓你連一個(gè)數(shù)都確定不了的數(shù)獨(dú)，但是測(cè)試點(diǎn)#3應(yīng)該就是這種。前面我用了N多的for循環(huán)來模擬逐個(gè)空白填的過程。中間的三塊循環(huán)分別是在該空白所在的３＊３空白區(qū)域、所在的行和所在的列里排除法找答案。這樣做最大的缺陷就是如果出測(cè)試點(diǎn)的人再狠一點(diǎn)，一個(gè)數(shù)字都不給你確定的話，你不是就沒轍了么······

于是最近學(xué)的深度優(yōu)先搜索就成了拿到最后10分的唯一方案。當(dāng)然前面的90分可不是白拿的。主程序里積攢了大量的，現(xiàn)成的循環(huán)篩選程序片段。我只要稍加改進(jìn)就可以變成一個(gè)函數(shù)里的核心成分。

最后滿分的程序

在函數(shù)里，我只能讓x坐標(biāo)一點(diǎn)點(diǎn)往上漲，超過8以后y坐標(biāo)再增加。這樣一來我就相當(dāng)于遍歷了一遍整個(gè)數(shù)獨(dú)。而且再函數(shù)回溯的時(shí)候y會(huì)自動(dòng)往回降。這樣就很方便了。后面往數(shù)組里填數(shù)的模塊我改動(dòng)了一下。這樣哪怕是可能有多種情況我也可以應(yīng)對(duì)了。

有了計(jì)算機(jī)，一般的數(shù)獨(dú)真的可以所向披靡隨便解?。ㄏ旅媸俏业某绦蚪鉀Q百度上所謂的世界最難數(shù)獨(dú)，附上最難數(shù)獨(dú)的程序輸入文字）

8 0 0 0 0 0 0 0 0
0 0 3 6 0 0 0 0 0
0 7 0 0 9 0 2 0 0
0 5 0 0 0 7 0 0 0
0 0 0 0 4 5 7 0 0
0 0 0 1 0 0 0 3 0
0 0 1 0 0 0 0 6 8
0 0 8 5 0 0 0 1 0
0 9 0 0 0 0 4 0 0

好啦，今天的信息競(jìng)賽基礎(chǔ)題就到這里啦。既然都看到這里了，給個(gè)三連再走不好嘛~~

Ps:據(jù)說，世界上最難的數(shù)獨(dú)有9種解法。今天UP決定，點(diǎn)贊只要夠4個(gè)，下一期我用程序把9種解法全算出來。