AC代码
(别抄了AC代码就走了，下面还有分析)
分析
1思路
很简单，各个格子都搜一遍，看看可以填哪个数即可，很像八皇后，但除去每行每列的数不同外，每一个九宫格中的数也不能相同，所以我们应该开三个bool数组，判断哪个数还可以填。但是没剪枝，效率往往低的让人无法忍受，所以我们可以优先填写空格子数较少的行或列。这样可以让没有数字的位置越来越少，从而减少搜索空间。
2数组与函数
此题数组很多，只能分开讲了
bool数组：
如1所述，g[i][j]判断在第i个九宫格中数字j是否出现过，hang[i][j]判断在第i个行中数字j是否出现过,lie[i][j]则表示判断在第i个列中数字j是否出现过
还有个问题，怎么判断矩阵中的数（如第x行第y列的数）属于第几个九宫格呢？
wg()的功能便是将1个9∗99*99∗9的矩阵分成9个3 ∗ 3 3*33∗3的九宫格，并能返回如第x行第y列的数所属九宫格
int数组：
如1所述，我们应按照空格子的个数从小到大排序，按此顺序排序即可，xu便是搜索顺序，sum是此行0出现的次数具体来说：
sum数组记录每个空格子可以填入数字的数量和。是间接排序的重要辅助数组。
很显然，我们对xu数组排序，却看的是sum数组中数字的大小，这便是间接排序。
xu数组存储数独的行号，用于按照空格子的个数从小到大排序。在优先填写空格子数较少的行的剪枝策略中，我们可以按照xu数组的顺序依次填写每行，并对每行的空格子数从小到大排序，这样可以让没有数字的位置越来越少，从而减少搜索空间。
举个例子，xu数组初始值为{1, 2, 3, 4, 5, 6, 7, 8, 9}，则搜索时第一次从第1行开始，第二次从第2行开始，以此类推。在搜索某行的空格子时，我们可以按照该行空格子数从小到大排序，生成新的xu数组，这样可以让搜索更加高效。
综上所述，sum和xu数组均是为了优化搜索算法而引入的辅助数组。
3.DFS(深度优先搜索)
参数：
在dfs函数中，4个参数分别是：
* x：当前要填的空格子的行数；
* y：当前要填的空格子的列数；
* score：当前方案的总分数，包括已经填好的格子权值之和以及当前正在填的格子的权值；
* sx：记录目前x在xu数组中的下标。
其中，x、y用来确定当前要填的空格子的位置，因为搜索是从左到右、从上到下的，所以需要记录行、列号。score则是当前方案的总分数，需要在搜索时不断更新。最终的答案就是所有可行方案中最大的总分数。
sx参数则是辅助作用，因为在dfs函数中，我们按照每行空格子的数量从小到大依次进行搜索，所以需要记录当前搜索的是哪一行的空格子，以便于下一步搜索，即剪枝。
边界：
当搜索到当前行的最后一列，即y==10时，需要判断是否已经填完了整个数独，即sx == 9。如果是，说明已经填完了整个数独，此时需要将当前方案的总分数与之前找到的最大分数进行比较，更新最大分数，然后结束本次搜索。
如果还没有填完整个数独，就需要继续搜索下一行，并从该行的第一列开始搜索。
回溯：
由于使用了bool数组作为标记，所以在向下搜索后取消标记
END\bold E\bold N\bold D END
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
我相信读者能够读懂main函数，我不过多赘述，另外这是一道相对来说比较困难的搜索题目，通过后可以加深对搜索和剪枝算法理解。也比较难优化。
附：
清晰易懂，效率极(鸡)高
