首页
论坛
课程
招聘
[作品提交]Kakuro数独问题
2008-6-28 22:43 8402

[作品提交]Kakuro数独问题

2008-6-28 22:43
8402
这是我参加数模的竞赛的作品。
虽然这个竞赛是数模竞赛,但题目偏重于算法,想了想我就发上来了。以下是题目介绍:


数独这个奇特的名字来源于日语Sudoku,是十八世纪瑞士数学家欧拉发明的。
后在美国发展,并在日本得以发扬光大。
Sudoku的规则十分简单,就是在9×9的九宫格里面填数字,每个方格中填人合适的数字以使得每行,每列以及每个九宫格都要包含从1~9的数字且互不相同.
数独的玩法逻辑简单,数字排列方式千变万化.不少教育者认为数独是锻炼脑筋的好方法。
谜题中会预先填入若干数字, 其它方格为空白, 玩家得依谜题中的数字分布状况, 逻辑推敲出剩下的空格里是什么数字。
由于规则简单, 在推敲之中完全不必用到数学计算, 
只需运用逻辑推理能力, 所以无论男女老幼, 人人都可以玩, 而且容易上手、容易入迷。
世界各地有很多数独俱乐部, 还有的国家如法国等专门举行过数独比赛, 其风靡程度可见一斑。目前网上流行一些经过变形的数独,其中Kakuro数独就是其中一种。
图1就是一道难度级别较高的Kakuro数独问题。
Kakuro数独规则如下:
1、在空格中填入数字1-9;数字0不能出现。
2、带斜线的方格,斜线上方的数字等于该方格右面对应的一组水平空格里的数字之和;斜线下方的数字,等于该方格下面对应一组垂直空格里的数字之和。
3、同一数字在每组水平(垂直)空格里只能出现一次。
针对Kakuro数独,完成以下问题:
讨论求解模型或方法


求解程序在附件中,c#写成,vs2005编译。
由于时间问题,就没写I/O接口了,数独地图的输入我采用下面三个矩阵:
 
         
  Map = new int[,]
                   {
                       {-1,-1,-1,-1,-1,-1,-1,-1},
                       {-1,-1, 0, 0,-1 ,0, 0,-1},
                       {-1, 0, 0, 0, 0, 0, 0,-1},
                       {-1, 0, 0,-1, 0, 0, 0, 0},
                       {-1,-1, 0, 0, 0,-1, 0, 0},
                       {-1, 0, 0, 0, 0, 0,-1,-1},
                       {-1, 0, 0, 0,-1 ,0, 0,-1},
                       {-1,-1,-1, 0, 0, 0, 0, 0},
                       {-1,-1, 0, 0, 0, 0, 0, 0},
                       {-1,-1, 0, 0, 0,-1,-1,-1}
                    
                   };
            MapDown = new int[,]//向下的条件
                     {
                   { -1,-1,-1,-1,-1,-1,-1,-1},
                       { -1, 3,-1,-1, 3,-1,-1,-1},
                       { 21,-1,-1,-1,-1,-1,-1,-1},
                       {  6,-1,-1,23,-1,-1,-1,-1},
                       { -1,21,-1,-1,-1,13,-1,-1},
                       { 22,-1,-1,-1,-1,-1,-1,-1},
                       {  7,-1,-1,-1, 3,-1,-1,-1},
                       { -1,-1,16,-1,-1,-1,-1,-1},
                       { -1,38,-1,-1,-1,-1,-1,-1},
                       { -1, 6,-1,-1,-1,-1,-1,-1}
                     };
            MapRight = new int[,]//向右的条件
                    {
                   {-1,-1,21, 6,-1,15,10,-1},
                   {-1, 3,-1,-1,26,-1,-1,-1},
                   {-1,-1,-1,-1,-1,-1,-1,15},
                   {-1,-1,-1,29,-1,-1,-1,-1},
                   {-1, 4,-1,-1,-1,11,-1,-1},
                   {-1,-1,-1,-1,-1,-1,17,-1},
                   {-1,-1,-1,-1,13,-1,-1, 7},
                   {-1,-1, 5,-1,-1,-1,-1,-1},
                   {-1,-1,-1,-1,-1,-1,-1,-1},
                   {-1,-1,-1,-1,-1,-1,-1,-1}
                     };

Map  表示整个的条件,正如图所示,所有可填的地方为0,不可填或表示条件的地方为-1。
MapDown 表示向下的条件,如图中(0,2)的地方为21,表示下面这一条相加之和为21.
同理MapRight 向右的条件。

程序运行即可得到解。如要修改图示中的条件,可自行修改Map  MapDown MapRight  三个二维数组。大家也可改成gui形式,呵呵,这里我就不做了

看雪招聘平台创建简历并且简历完整度达到90%及以上可获得500看雪币~

上传的附件:
收藏
点赞0
打赏
分享
最新回复 (14)
雪    币: 250
活跃值: 活跃值 (83)
能力值: ( LV12,RANK:450 )
在线值:
发帖
回帖
粉丝
weolar 活跃值 10 2008-6-28 22:51
2
0
代码已经贴上
雪    币: 87
活跃值: 活跃值 (293)
能力值: ( LV6,RANK:80 )
在线值:
发帖
回帖
粉丝
frozenrain 活跃值 2008-6-28 22:57
3
0
好深奥哦 !
作品好象要source code
雪    币: 250
活跃值: 活跃值 (83)
能力值: ( LV12,RANK:450 )
在线值:
发帖
回帖
粉丝
weolar 活跃值 10 2008-6-28 22:59
4
0
不好意思,这网速有问题,我提交了两个重复的。相关代码已经贴出
雪    币: 250
活跃值: 活跃值 (83)
能力值: ( LV12,RANK:450 )
在线值:
发帖
回帖
粉丝
weolar 活跃值 10 2008-6-28 23:37
5
0
刚才我发重复了……
雪    币: 220
活跃值: 活跃值 (16)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
萝卜 活跃值 1 2008-6-29 18:37
6
0
学习一下,没想到这个还在小日本能发扬光大
雪    币: 201
活跃值: 活跃值 (10)
能力值: ( LV9,RANK:250 )
在线值:
发帖
回帖
粉丝
zeal 活跃值 6 2008-6-30 09:33
7
0
好像那本<<编程之美>>--微软面试技术心得里面也有,很详细
雪    币: 250
活跃值: 活跃值 (83)
能力值: ( LV12,RANK:450 )
在线值:
发帖
回帖
粉丝
weolar 活跃值 10 2008-7-3 17:50
8
0
哈,《编程之美》也讲了Kakuro吗,那我一定要买来好好看看。不过我的算法可是自己写的,虽然可能比较垃圾,但搜索加回溯的方法效率还是比较高的
雪    币: 201
活跃值: 活跃值 (10)
能力值: ( LV9,RANK:250 )
在线值:
发帖
回帖
粉丝
zeal 活跃值 6 2008-7-3 18:13
9
0
是的,还有很多算法,当然,他里面的算法也不是最美的,呵呵
雪    币: 250
活跃值: 活跃值 (83)
能力值: ( LV12,RANK:450 )
在线值:
发帖
回帖
粉丝
weolar 活跃值 10 2008-7-3 19:44
10
0
呵呵,这位大侠可否留个联系方式呢,想交流算法的经验,或聊些工作的感言,我想往这方面转行呢
雪    币: 201
活跃值: 活跃值 (10)
能力值: ( LV9,RANK:250 )
在线值:
发帖
回帖
粉丝
zeal 活跃值 6 2008-7-3 22:47
11
0
已经加你的QQ了
雪    币: 1201
活跃值: 活跃值 (10)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
ljtt 活跃值 1 2008-7-4 02:37
12
0
正好前段时间也想了解下数独,网上搜索了下,下面这个网站介绍的还不错。
http://blog.csdn.net/mathe/archive/2007/08/23/1755672.aspx
雪    币: 250
活跃值: 活跃值 (83)
能力值: ( LV12,RANK:450 )
在线值:
发帖
回帖
粉丝
weolar 活跃值 10 2008-7-6 19:06
13
0
谢谢楼上这位,我会好好看看的,呵呵。
不过我这个数独是要算各行各列之和的,和其他的数独有些不同,要不当时数模竞赛的时候大家岂不是在网上搜索一下就能找到代码了,呵呵
雪    币: 1201
活跃值: 活跃值 (10)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
ljtt 活跃值 1 2008-7-7 13:55
14
0
我只是提供一个链接介绍一下数独,让大家都有所了解而已。
没有对你提交的作品有什么意见,也没有对你能够写出算法表示过怀疑。
如有误解非常抱歉。
雪    币: 250
活跃值: 活跃值 (83)
能力值: ( LV12,RANK:450 )
在线值:
发帖
回帖
粉丝
weolar 活跃值 10 2008-7-8 17:58
15
0
嗯,就算 是怀疑我也很欢迎的,呵呵,希望和 大家多交流
游客
登录 | 注册 方可回帖
返回