C语言实现数独合法性判断

C语言实现数独合法性判断

数独是根据 9×9 盘面上的已知数字,推理出所有剩余空格的数字的游戏,并满足每一行、每一列、每一个粗线宫内的数字均含 1∼9,不重复。

设计出了全球最难的“数独游戏”,并刊登在报纸上,让大家去挑战。有人声称解决了这些数独问题,请你判断他是否真的解决了这些数独问题。

输入格式
输入共 9 行
输入的每行包含 9个正整数,代表填好的数独(可能会乱填数独,导致出现大于 9 的数)
输出格式
输出 YES 或 NO,表示填好的数独合法或不合法



测试样例
Input

8 1 2 7 5 3 6 4 9

9 4 3 6 8 2 1 7 5

6 7 5 4 9 1 2 8 3

1 5 4 2 3 7 8 9 6

3 6 9 8 4 5 7 2 1

2 8 7 1 6 9 5 3 4

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

Output

YES

从题目介绍来看,这道题重点考察对C语言中二维数组的使用。从题目中可以知道数独满足的条件是,“每一行、每一列、每一个粗线宫内的数字均含 1∼9,不重复。这也就意味着,要满足两个条件才算是数独。

  • 每行、每列是否只含数字1~9,如果有重复数字则认为不满足数独条件。
  • 粗线宫格也要满足只含数字1~9,并且不重复的条件。仔细分析上面那张图,不难发现粗线宫格实际上,就是把整个二维数组分为9个3X3的二维数组。因此,第二个条件就转化为判断3X3的二维数组,是否满足条件。

经过这样分析,我们不难得出,解决这道题的编码思路如下。

  • 准备3个标记数组,默认值都为0,遍历数组每行、每列元素,在各自标记数组进行标记。
  • 如果标记数组不为0,则说明这个数组被标记过,数字出现重复,不满足条件。
  • 判断3×3二维数组是否满足条件时,需要将二维数组元素转化到3×3数组里面,进行判断。

仔细想来,这道题其实是进一步加强对二维数组的使用,特别是使用标记数组对元素进行标记。

如果有疑问或者需要源码,可通过公众号与我联系。

发表评论

邮箱地址不会被公开。 必填项已用*标注