首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C++ >

数独哪里错呢?解决方法

2012-04-09 
数独哪里错呢?数独(Sudoku)是一项经久不衰的游戏,全世界有数量众多的数独fans,有不同的形式的数独,最广为

数独哪里错呢?
数独(Sudoku)是一项经久不衰的游戏,全世界有数量众多的数独fans,有不同的形式的数独,最广为流传的是9*9格的数独。
数独(游戏的规则很简单,有一张9*9的表格,每个表格中可填1-9之间的数字,但是在一行、一列或者一个3*3的小块内1-9之间的数字有且仅有出现一次。数独中的部分数字已经填好了,请你在最短的时间内按要求填好全部数字。
例如初始时如下:"."表示待填数字的空位置。
4 2 . 7 5 . 6 . .
3 8 6 . . . 5 . 1
. . . . 3 1 4 8 2
6 9 7 3 1 4 . . .
2 5 4 . . . 3 1 7
. . . 2 7 5 9 6 4
1 4 8 5 9 . . . .
5 . 9 . . . 8 4 6
. . 2 . 8 3 . 9 5
填好后,得到如下结果:
4 2 1 7 5 8 6 3 9
3 8 6 9 4 2 5 7 1
9 7 5 6 3 1 4 8 2
6 9 7 3 1 4 2 5 8
2 5 4 8 6 9 3 1 7
8 1 3 2 7 5 9 6 4
1 4 8 5 9 6 7 2 3
5 3 9 1 2 7 8 4 6
7 6 2 4 8 3 1 9 5

当然,现在的任务不是要你填表(这个任务有点复杂,我们留到以后吧!),而是假设这个表已经被别人填好了,请你编程帮助他判断一下这个表格是否满足填表条件。

Input
第一数字表示测试用例的个数n(n<=100)
对于每个测试用例,输入有9行9列矩阵。矩阵元素为1-9之间的数字。输入数据元素之间用空格分隔。
两个测试用例之间用空行分隔。

Output
对于每个测试用例,输出单独占一行,如果表格满足条件要求则输出1,否则输出0。

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

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

Sample Output
1
0

C/C++ code
#include<stdio.h>main(){    int num[9][9],n,i,j,k,flag=0,u;    scanf("%d",&n);    for(i=0;i<n;i++)    {        for(j=0;j<9;j++)        {            for(k=0;k<9;k++)            scanf("%d",&num[j][k]);        }        flag=1;    for(j=0;j<9;j++)    {        for(k=0;k<8;k++)          for(u=k+1;u<9;u++)        if(num[j][k]==num[j][u])        {            flag=0;        }        if(j+1<9)        if(num[j][0]==num[j+1][0])        flag=0;    }    for(j=0;j<7;j+=3)    {        for(k=0;k<7;k+=3)        {            for(u=1;u<3;u++)            {            if(num[j][k+u]==num[j][k])            flag=0;            if(num[j+u][k]==num[j][k])            flag=0;            if(num[j+u][k+u]==num[j][k])            flag=0;            }        }    }    printf("%d\n",flag);    }}

哪里错呢?老是WA?

[解决办法]
因为楼主只判断了行,没有判断列。。。程序有待改进啊。。。只发改进的地方
C/C++ code
        flag=1;        for(j=0;j<9;j++)        {            flag=checkRowAndCol(num, j);            if (flag==0)            {                break;            }        }
[解决办法]
C/C++ code
#include<stdio.h>main(){    int num[9][9],n,i,j,k,flag=0,u;    int v,w,small[9];     //  为了简化3x3小格判断,我们需要一个辅助数组    scanf("%d",&n);    for(i=0;i<n;i++)    {        for(j=0;j<9;j++)        {            printf("Line%d-->",j+1);    //  输入这么多数字,还是稍微给人一点提示吧,否则很累啊            for(k=0;k<9;k++)                scanf("%d",&num[j][k]);        }        flag=1;        for(j=0;j<9;j++)        {            for(k=0;k<8;k++)              for(u=k+1;u<9;u++)              {                if(num[j][k]==num[j][u])                {                    flag=0;                }                if (num[k][j]==num[u][j])   //  判定第j列是否有重复数字,只要把行和列下标互相交换就可以了。因为那是个正方形表格                    flag=0;              }            /*if(j+1<9)     //  这个样子怎么能判断列重复呢?它们甚至才执行了仅仅9遍。                if(num[j][0]==num[j+1][0])                    flag=0;*/        }        for(j=0;j<7;j+=3)        {            for(k=0;k<7;k+=3)            {                /*for(u=1;u<3;u++)          //  这样仅仅把num[j][k]拿出来对比,也就仅仅核对了每个3x3格子的顶部那一个数据而已,漏多了                {                    if(num[j][k+u]==num[j][k])                    flag=0;                    if(num[j+u][k]==num[j][k])                    flag=0;                    if(num[j+u][k+u]==num[j][k])                    flag=0;                }*/                for (u=0;u<3;u++)           //  我们首先把这个小矩阵里的数据放到small里                    for (v=0;v<3;v++)                        small[u*3+v]=num[j+u][k+v];                for (u=0;u<8;u++)           //  然后就能方便的判定里面有没有重复数据了                    for (v=u+1;v<9;v++)                        if (small[u]==small[v])                            flag=0;            }        }        printf("%d\n",flag);    }} 

热点排行