前些日子,有人网上说解决了什么最难数独什么的,然后下面一片欢呼 -- 我看了下所谓题目,无非一个普通的9*9的小题目而已,机器完全可以轻松遍历。 感觉很不可思议 -- 在这种信息时代,计算机能轻松遍历的东西,就不算什么难题,让人闲暇时候玩玩就算了,拿来当作学术成就什么来炫耀,实在有些。。。坐什么观什么了。

正事做着,debug很烦恼,所以随便写个数独的解决来调节下身心健康。 数独有规则如下:

  1. 9*9空格中,填入1~9 这9个数字之1
  2. 每行,每列的9个数字不可重复。
  3. 将9*9的区域分为3*3个3*3格的区域,每个区域内部不可重复

实现如下:

1. 每行不可重复

在初始化的时候,未填写的位置是0,所以不会影响到别的数据。 然后就是行坐标不变,列坐标一个一个试探,如果都不相同说明是可以用的。

int Horizontal(int a[9][9],int abscissa,int ordinate,int test)
{
    int i;
    for(i=0;i<9;i++)
        if(a[abscissa][i] == test)return 0;
    return 1;
}

2. 每列不可重复

每列不可重复其实和每行不可重复是相似的,只是一个是行坐标不变,一个是列坐标。

int Vertical(int a[9][9],int abscissa,int ordinate,int test)
{
    int i;
    for(i=0;i<9;i++)
        if(a[i][ordinate] == test) return 0;
    return 1;
}

3. 小区域不可重复

首先检查待测试的代码所在区域(其实就是横向3个区域,纵向3个区域)。 然后比较和前两个一样。

int Area(int a[9][9],int abscissa,int ordinate,int test)
{
    int i,j;
    int absMin = (abscissa/3)*3;
    int absMax = (abscissa/3+1)*3;
    int ordMin = (ordinate/3)*3;
    int ordMax = (ordinate/3+1)*3;
    for(i=absMin;i<absMax;i++)
        for(j=ordMin;j<ordMax;j++)
            if(test == a[i][j]) return 0;
    return 1;
}

4. 递归试探

传入的是一个已经填写了一半的数组和一个offset,offset的值是0~80共81个,如果超过这个,说明完美完结了,否则继续判断。 如果是非0,则递归自己,填写下个offset,否则从1~9逐个试探是否可以填写。若可以,填写,否则清0本次数据,测试下个。直到可以或者终于确定这条路走不痛,返回是或者否。

inline int AllDone(int a[9][9],int abscissa,int ordinate,int test)
{
    if(!Horizontal(a,abscissa,ordinate,test)) return 0;
    if(!Vertical(a,abscissa,ordinate,test)) return 0;
    if(!Area(a,abscissa,ordinate,test)) return 0;
    return 1;
}

int nextData(int a[9][9],int offset)
{
    if(offset >= 81) return 1;
    int i;
    int abs = offset/9;
    int ord = offset%9;
    if(a[abs][ord]!=0)
    {
        return nextData(a,offset+1);
    }
    for(i=1;i<10;i++)
    {
        if(AllDone(a,abs,ord,i))
        {
            a[abs][ord] = i;
            if(nextData(a,offset+1))
            {
                return 1;
            }
        }
        a[abs][ord] = 0;
    }
    return 0;
}

5. 输出

如题。输出就是个简单的控制。 每行输出9个,输出9行即可。

int output(int a[9][9])
{
    int i,j;
    for(i=0;i<9;i++)
    {
        for(j=0;j<9;j++)
            printf("%d ",a[i][j]);
        printf("\n");
    }
    return 1;       
}

6. main函数

main函数读取9*9个数字,然后递归开搞。 如果无法搞,显示无解,否则显示解。

int main()
{
    int a[9][9];
    int i;
    int j;
    memset(a,0,sizeof(a));
    for(i=0;i<9;i++)
    {
        for(j=0;j<9;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    if(nextData(a,0))
    {
        printf("get result:\n");
        output(a);
    }else
    {
        printf("no result.\n");
    }
    return 0;
}

当然,参数列表什么的,有些没有用到,回头再改,反正不是在做的正事。

输出测试

[yu@argcandargv-com Sudoku]$ make run 
INPUT:
0 0 0 0 0 0 4 5 0
0 0 7 0 0 0 3 0 0
1 0 9 0 6 0 0 0 0
3 0 0 0 0 0 0 0 0
5 0 0 4 0 0 0 0 0
0 0 0 0 7 0 0 0 9
0 0 1 2 0 0 0 0 0
0 0 0 3 0 0 0 0 0
0 0 6 0 0 0 0 0 7
OUTPUT:
get result:
8 6 3 7 9 2 4 5 1 
2 5 7 1 8 4 3 9 6 
1 4 9 5 6 3 8 7 2 
3 9 8 6 2 1 7 4 5 
5 7 2 4 3 9 6 1 8 
6 1 4 8 7 5 2 3 9 
9 8 1 2 4 7 5 6 3 
7 2 5 3 1 6 9 8 4 
4 3 6 9 5 8 1 2 7 

CORRECT?

工程位置如下:

有人有兴趣,可以拿过去玩玩。

需要说明的是, 这个纯粹是暴力跑. 有很多方法可以很容易优化, 只是没有做而已.

此外, leetcode 有一道题也是讲数独的, 我为此准备了一个解在此处.

来自的你,很高兴你能看到这儿。若本文对你有所用处,或者内容有什么不足之处,敬请毫不犹豫给个回复。谢谢!