前些日子,有人网上说解决了什么最难数独什么的，然后下面一片欢呼 -- 我看了下所谓题目，无非一个普通的9*9的小题目而已，机器完全可以轻松遍历。 感觉很不可思议 -- 在这种信息时代，计算机能轻松遍历的东西，就不算什么难题，让人闲暇时候玩玩就算了，拿来当作学术成就什么来炫耀，实在有些。。。坐什么观什么了。
正事做着，debug 很烦恼，所以随便写个数独的解决来调节下身心健康。
数独有规则如下：
9*9空格中，填入 1~9 这 9 个数字某个- 每行，每列的9个数字不可重复。
- 将
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 有一道题也是讲数独的, 我为此准备了一个解在此处.
38 Comments
Leniy · February 7, 2014 at 09:28
怎么又想起来更新这篇文章了？
yu · February 7, 2014 at 12:57
@Leniy 删掉了1/3不喜欢的旧文，这个估计是一不小心更新的吧
Leniy · February 7, 2014 at 12:58
@Yu Jing 你修改评论的速度好快
yu · February 7, 2014 at 12:59
@Leniy 其实是不小心f5了下
Leniy · February 7, 2014 at 13:00
@Yu Jing 评论中的“的”的位置不一样啊
yu · February 7, 2014 at 13:02
@Leniy 就是不小心刷了下网页修改后重新提交，结果被判定为提交了两次，然后后台把第一次删掉这样的操作过程啊。
Leniy · February 7, 2014 at 13:03
@Yu Jing soga。你们开学没？
yu · February 7, 2014 at 13:04
@Leniy 实验室coding …顺手处理邮件之类的什么中
Leniy · February 7, 2014 at 13:05
@Yu Jing 好羡慕
Vespa · January 5, 2014 at 20:12
以前大一也写过数独的全解程序，也是C++，也是这条思路。。
yu · January 5, 2014 at 20:25
@Vespa 哈，9*9，遍历一遍都是小意思，轻松就能暴力，何乐而不为
小草元 · July 5, 2013 at 23:39
数独挺流行的，但我至今不了解其玩法。
看博主的解决方法没有理解。手机上看的难受，明天电脑再仔细顽味下。总感觉你的思路说的不清楚。。。或许还是我理解不到位
yu · July 6, 2013 at 19:56
表示其实就是最普通粗暴的遍历而已..谈不上思路
reizhi · May 1, 2013 at 22:35
当然，这种能够遍历/枚举的数学问题用编程再好不过了
yu · May 2, 2013 at 13:15
的确
这类东西和代码真是专业对口
Leniy · April 25, 2013 at 15:02
git管理感觉麻烦啊。还要同步
yu · April 25, 2013 at 15:09
设置好hook后push上去直接部署master那个branch
Leniy · April 25, 2013 at 15:31
git我只用过github给的那个软件
yu · April 25, 2013 at 16:08
github只是其中一个托管商而已。git对服务器要求不高，可以是任何的空间，https ssh连接都可以，对服务器配置也几乎没有要求。
超好用呢
Leniy · April 26, 2013 at 15:58
我能把自己的空间换成git管理么？
yu · April 26, 2013 at 17:44
可以。
我用的是自带的，不过自己写也很容易实现。
这东西在回复里面不能说的太细，我写个新的帖子说说吧。
Leniy · April 25, 2013 at 15:44
为嘛刚刚用python给你的站点post数据没有成功啊
yu · April 25, 2013 at 16:07
不知道…
难道cache问题
Leniy · April 25, 2013 at 07:52
能评论了么
yu · April 25, 2013 at 09:51
原来的IP被墙了，但是CDN转发没问题。
本来打算用CDN完全替代原IP用的，但CDN不怎么给力，老是拿缓存骗人。。。囧。。
另，评论通知邮件工作正常否？
Leniy · April 25, 2013 at 15:43
然后没见到邮件
yu · April 25, 2013 at 21:10
这个回复的邮件能否看到？
调了下插件，发现插件暗藏玄机。。所以，你从没有收到过这个小站发出的邮件提示。。。。？
Leniy · April 26, 2013 at 07:55
收到了。以前收到过几次，后来就没有反应了
yu · April 25, 2013 at 09:56
然后我换了个主机。。。
迁移数据麻烦了点，但搞主机什么的贼方便
用git管理就是爽
Leniy · April 25, 2013 at 15:03
我过几个月准备把我的博客放到dreamhost的主机上。目前只用那个主机的ssh功能，感觉很浪费啊
yu · April 25, 2013 at 15:12
$15 / month per month ？
看介绍配置很赞啊，不知道用起来怎么样。
等我自己赚钱了再转付费的吧。。。
Leniy · April 25, 2013 at 15:24
$119/y
和同学合租的。每人才几十元
yu · April 25, 2013 at 15:40
哦，对…root权限的vps可以自己配环境，N多个网站可以一起用的哈。。。
Leniy · April 25, 2013 at 15:51
不是vps
yu · April 25, 2013 at 16:05
web hosting 也可以多domain不混？
之前还不知道
Leniy · April 25, 2013 at 16:06
看主机是不是提供了
t.k. · April 24, 2013 at 18:53
没有玩过数独的路过。。
yu · April 24, 2013 at 19:53
我也不会 —
不过这并不妨碍代码轻松完破这些所谓难题