就真的有那么一点点思维含量······

今天的题取自我们学校的BNDSOJ网站：

BNDS校园吉尼斯开展解数独比赛，数独游戏的规则是这样的：在一个9x9的方格中，你需要把数字1-9填写到空格当中，并且使方格的每一行和每一列中都包含1-9这九个数字。同时还要保证，空格中用粗线划分成9个3x3的方格也同时包含1-9这九个数字。

现在BNDS信息学竞赛班的学生需要用编程解决数独问题。输入一个9*9的数字序列，其中空位用0表示。输出解答之后的数字序列

示例输入：

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

首先是读题。我作为一个从来没有玩过数独的人，只能先把输入的样例解出来，然后再研究规律。按照题意，一个3*3的方格里会有1-9的数字，横竖都是1-9九个数字的排列。所以我应该有三套for循环来筛选出可能能填的数。然后就是逐渐排查呗。先把能够直接确定的数据填写上，然后再逐渐的往上找。最后就可以确定整个数独的所有数据了。

多简单呀（记住我说的话）

早些时候我写出来的那些连一个格子都没法填的程序现在已经无从考证了。讲真，光是将最简单的数独填出来就用了一个下午。我真的没想到还会有最开始让你连一个数都确定不了的数独，但是测试点#3应该就是这种。前面我用了N多的for循环来模拟逐个空白填的过程。中间的三块循环分别是在该空白所在的３＊３空白区域、所在的行和所在的列里排除法找答案。这样做最大的缺陷就是如果出测试点的人再狠一点，一个数字都不给你确定的话，你不是就没辙了么······

于是最近学的深度优先搜索就成了拿到最后10分的唯一方案。当然前面的90分可不是白拿的。主程序里积攒了大量的，现成的循环筛选程序片段。我只要稍加改进就可以变成一个函数里的核心成分。

最后满分的程序

在函数里，我只能让x坐标一点点往上涨，超过8以后y坐标再增加。这样一来我就相当于遍历了一遍整个数独。而且再函数回溯的时候y会自动往回降。这样就很方便了。后面往数组里填数的模块我改动了一下。这样哪怕是可能有多种情况我也可以应对了。

有了计算机，一般的数独真的可以所向披靡随便解！（下面是我的程序解决百度上所谓的世界最难数独，附上最难数独的程序输入文字）

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

好啦，今天的信息竞赛基础题就到这里啦。既然都看到这里了，给个三连再走不好嘛~~

Ps:据说，世界上最难的数独有9种解法。今天UP决定，点赞只要够4个，下一期我用程序把9种解法全算出来。