数独检查
题目来源：acwing题库
题目地址：https://www.acwing.com/problem/content/705/
题目描述：
数独是一种流行的单人游戏。
目标是用数字填充9×9矩阵，使每列，每行和所有9个非重叠的3×3子矩阵包含从1到9的所有数字。
给定完成的N2∗N2数独矩阵，你的任务是确定它是否是有效的解决方案。
有效的解决方案必须满足以下条件：
输入格式
第一行包含整数T，表示共有T组测试数据。
每组数据第一行包含整数N。
接下来N2行，每行包含N2个数字（均不超过1000），用来描述完整的数独矩阵。
输出格式
每组数据输出一个结果，每个结果占一行。
结果表示为“Case #x: y”，其中x是组别编号（从1开始），如果给定矩阵是有效方案则y是Yes，否则y是No。
数据范围
1≤T≤100,
3≤N≤6
输入样例：
3
3
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9
3
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
3
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 999 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9
输出样例：
Case #1: Yes
Case #2: No
Case #3: No
我看了很多大佬的题解，看得我眼花缭乱，所以我想来给大家介绍一种简单易懂的方法哈！
数独游戏的特征就是每行每列，从1~n*n每个数字都只会出现一次，否则那就是错误的，所以我们就抓住这个特性，利用一种特殊的方式（好像类似于哈希，但是我没学哈希，自己想出来的方法）来解决这个问题。我们先开一个额外的数组f[N][N]，先初始化为0，然后我们输入每个数据，让每个数据所在的行与列 对应的位置都加上1（比如第一行第一列的数是9，那么我们就让第一行和第一列对应的额外开的数组+1，即f[1][9]+=1,f[9][1]+=1，再比如第二行第三列的数字是8，那么就是f[2][8]+=1,f[8][3]+=1），对于每个数字都完成这样的操作以后，那么我们就可以对额外开的数组进行判断。
如果额外开的数组中，每个数字都是2，那么说明这个数独是正确的（为什么是2呢？因为一个数会影响其所在的行和列，所以行和列都会+1，所以结果应该大家都是2），如果出现不是2的，那儿么这个数独就是错误的，因为它要么就是少出现了，要么就是多出现了，都不行。所以通过这种简单易懂的方法，我们就可以解决这个题目。（因为我也是小白，看到那些大佬的解法吓我一条，所以我就自己想出了一种解法，我觉得是比较好理解的）
如果还有不太明白的同学可以带着代码一起看看，应该就可以明白了。
下面是AC代码+注释
#include
本来是在acwing上写的一篇题解，然后我每天都要写一篇博客嘛，然后偷个懒，就转过来了，是自己原创的哦！
好了，这个题目就讲到这里啦！
每篇博客后面都附上一句话。
是不是卑微到连她回你一个信息，你都可以开心一整天。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/220766.html原文链接：https://javaforall.net
