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

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

数独有规则如下:

  • 9*9空格中,填入1~9 这9个数字之1
  • 每行,每列的9个数字不可重复。
  • 将99的区域分为33个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 有一道题也是讲数独的, 我为此准备了一个解在此处.

Categories: Code

Yu

Ideals are like the stars: we never reach them, but like the mariners of the sea, we chart our course by them.

38 Comments

t.k. · April 24, 2013 at 18:53

Google Chrome 25.0.1364.97 Google Chrome 25.0.1364.97 GNU/Linux GNU/Linux

没有玩过数独的路过。。

    yu · April 24, 2013 at 19:53

    Google Chrome 26.0.1410.63 Google Chrome 26.0.1410.63 GNU/Linux x64 GNU/Linux x64

    我也不会 —
    不过这并不妨碍代码轻松完破这些所谓难题

Leniy · April 25, 2013 at 07:52

Google Chrome 26.0.1410.64 Google Chrome 26.0.1410.64 Windows 7 Windows 7

能评论了么

    yu · April 25, 2013 at 09:51

    Google Chrome 26.0.1410.64 Google Chrome 26.0.1410.64 Windows 7 x64 Edition Windows 7 x64 Edition

    原来的IP被墙了,但是CDN转发没问题。
    本来打算用CDN完全替代原IP用的,但CDN不怎么给力,老是拿缓存骗人。。。囧。。

    另,评论通知邮件工作正常否?

      Leniy · April 25, 2013 at 15:43

      Google Chrome 26.0.1410.64 Google Chrome 26.0.1410.64 Windows 7 Windows 7

      然后没见到邮件

        yu · April 25, 2013 at 21:10

        Google Chrome 26.0.1410.63 Google Chrome 26.0.1410.63 GNU/Linux x64 GNU/Linux x64

        这个回复的邮件能否看到?

        调了下插件,发现插件暗藏玄机。。所以,你从没有收到过这个小站发出的邮件提示。。。。?

          Leniy · April 26, 2013 at 07:55

          Google Chrome 26.0.1410.64 Google Chrome 26.0.1410.64 Windows 7 Windows 7

          收到了。以前收到过几次,后来就没有反应了

    yu · April 25, 2013 at 09:56

    Google Chrome 26.0.1410.64 Google Chrome 26.0.1410.64 Windows 7 x64 Edition Windows 7 x64 Edition

    然后我换了个主机。。。
    迁移数据麻烦了点,但搞主机什么的贼方便
    用git管理就是爽

      Leniy · April 25, 2013 at 15:03

      Google Chrome 26.0.1410.64 Google Chrome 26.0.1410.64 Windows 7 Windows 7

      我过几个月准备把我的博客放到dreamhost的主机上。目前只用那个主机的ssh功能,感觉很浪费啊

        yu · April 25, 2013 at 15:12

        Google Chrome 26.0.1410.63 Google Chrome 26.0.1410.63 GNU/Linux x64 GNU/Linux x64

        $15 / month per month ?
        看介绍配置很赞啊,不知道用起来怎么样。

        等我自己赚钱了再转付费的吧。。。

          Leniy · April 25, 2013 at 15:24

          Google Chrome 26.0.1410.64 Google Chrome 26.0.1410.64 Windows 7 Windows 7

          $119/y
          和同学合租的。每人才几十元

            yu · April 25, 2013 at 15:40

            Google Chrome 26.0.1410.63 Google Chrome 26.0.1410.63 GNU/Linux x64 GNU/Linux x64

            哦,对…root权限的vps可以自己配环境,N多个网站可以一起用的哈。。。

              Leniy · April 25, 2013 at 15:51

              Google Chrome 26.0.1410.64 Google Chrome 26.0.1410.64 Windows 7 Windows 7

              不是vps

                yu · April 25, 2013 at 16:05

                Google Chrome 26.0.1410.63 Google Chrome 26.0.1410.63 GNU/Linux x64 GNU/Linux x64

                web hosting 也可以多domain不混?
                之前还不知道

                  Leniy · April 25, 2013 at 16:06

                  Google Chrome 26.0.1410.64 Google Chrome 26.0.1410.64 Windows 7 Windows 7

                  看主机是不是提供了

Leniy · April 25, 2013 at 15:02

Google Chrome 26.0.1410.64 Google Chrome 26.0.1410.64 Windows 7 Windows 7

git管理感觉麻烦啊。还要同步

    yu · April 25, 2013 at 15:09

    Google Chrome 26.0.1410.63 Google Chrome 26.0.1410.63 GNU/Linux x64 GNU/Linux x64

    设置好hook后push上去直接部署master那个branch

      Leniy · April 25, 2013 at 15:31

      Google Chrome 26.0.1410.64 Google Chrome 26.0.1410.64 Windows 7 Windows 7

      git我只用过github给的那个软件

        yu · April 25, 2013 at 16:08

        Google Chrome 26.0.1410.63 Google Chrome 26.0.1410.63 GNU/Linux x64 GNU/Linux x64

        github只是其中一个托管商而已。git对服务器要求不高,可以是任何的空间,https ssh连接都可以,对服务器配置也几乎没有要求。
        超好用呢

          Leniy · April 26, 2013 at 15:58

          Google Chrome 26.0.1410.64 Google Chrome 26.0.1410.64 Windows 7 Windows 7

          我能把自己的空间换成git管理么?

            yu · April 26, 2013 at 17:44

            Google Chrome 26.0.1410.63 Google Chrome 26.0.1410.63 GNU/Linux x64 GNU/Linux x64

            可以。
            我用的是自带的,不过自己写也很容易实现。
            这东西在回复里面不能说的太细,我写个新的帖子说说吧。

      Leniy · April 25, 2013 at 15:44

      Google Chrome 26.0.1410.64 Google Chrome 26.0.1410.64 Windows 7 Windows 7

      为嘛刚刚用python给你的站点post数据没有成功啊

        yu · April 25, 2013 at 16:07

        Google Chrome 26.0.1410.63 Google Chrome 26.0.1410.63 GNU/Linux x64 GNU/Linux x64

        不知道…
        难道cache问题

reizhi · May 1, 2013 at 22:35

Google Chrome 28.0.1494.0 Google Chrome 28.0.1494.0 Windows 8 x64 Edition Windows 8 x64 Edition

当然,这种能够遍历/枚举的数学问题用编程再好不过了

    yu · May 2, 2013 at 13:15

    Google Chrome 26.0.1410.63 Google Chrome 26.0.1410.63 GNU/Linux x64 GNU/Linux x64

    的确
    这类东西和代码真是专业对口

小草元 · July 5, 2013 at 23:39

Opera Mini 7.1.32052 Opera Mini 7.1.32052 J2ME/MIDP Device J2ME/MIDP Device

数独挺流行的,但我至今不了解其玩法。
看博主的解决方法没有理解。手机上看的难受,明天电脑再仔细顽味下。总感觉你的思路说的不清楚。。。或许还是我理解不到位

    yu · July 6, 2013 at 19:56

    Google Chrome 28.0.1500.71 Google Chrome 28.0.1500.71 GNU/Linux x64 GNU/Linux x64

    表示其实就是最普通粗暴的遍历而已..谈不上思路

Vespa · January 5, 2014 at 20:12

Sogou Explorer Sogou Explorer Windows XP Windows XP

以前大一也写过数独的全解程序,也是C++,也是这条思路。。

    yu · January 5, 2014 at 20:25

    Google Chrome 31.0.1650.63 Google Chrome 31.0.1650.63 GNU/Linux x64 GNU/Linux x64

    @Vespa 哈,9*9,遍历一遍都是小意思,轻松就能暴力,何乐而不为

Leniy · February 7, 2014 at 09:28

Google Chrome 32.0.1700.107 Google Chrome 32.0.1700.107 Windows 7 Windows 7

怎么又想起来更新这篇文章了?

    yu · February 7, 2014 at 12:57

    Google Chrome 32.0.1700.77 Google Chrome 32.0.1700.77 GNU/Linux x64 GNU/Linux x64

    @Leniy 删掉了1/3不喜欢的旧文,这个估计是一不小心更新的吧

      Leniy · February 7, 2014 at 12:58

      Google Chrome 32.0.1700.107 Google Chrome 32.0.1700.107 Windows 7 Windows 7

      @Yu Jing 你修改评论的速度好快

        yu · February 7, 2014 at 12:59

        Google Chrome 32.0.1700.77 Google Chrome 32.0.1700.77 GNU/Linux x64 GNU/Linux x64

        @Leniy 其实是不小心f5了下

          Leniy · February 7, 2014 at 13:00

          Google Chrome 32.0.1700.107 Google Chrome 32.0.1700.107 Windows 7 Windows 7

          @Yu Jing 评论中的“的”的位置不一样啊

            yu · February 7, 2014 at 13:02

            Google Chrome 32.0.1700.77 Google Chrome 32.0.1700.77 GNU/Linux x64 GNU/Linux x64

            @Leniy 就是不小心刷了下网页修改后重新提交,结果被判定为提交了两次,然后后台把第一次删掉这样的操作过程啊。

              Leniy · February 7, 2014 at 13:03

              Google Chrome 32.0.1700.107 Google Chrome 32.0.1700.107 Windows 7 Windows 7

              @Yu Jing soga。你们开学没?

                yu · February 7, 2014 at 13:04

                Google Chrome 32.0.1700.77 Google Chrome 32.0.1700.77 GNU/Linux x64 GNU/Linux x64

                @Leniy 实验室coding …顺手处理邮件之类的什么中

Leave a Reply

Your email address will not be published. Required fields are marked *