数学研发论坛

 找回密码
 欢迎注册
查看: 13317|回复: 49

[分享] 数独——全民数独,今天你玩了么

[复制链接]
发表于 2008-2-5 16:20:36 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
文章来源:http://baike.baidu.com/view/451932.htm
九宫格数独

  是一种源自18世纪末的瑞士,后在美国发展、并在日本得以发扬光大的数学智力拼图游戏。拼图是九宫格(即3格宽×3格高)的正方形状,每一格又细分为一个九宫格。在每一个小九宫格中,分别填上1至9的数字,让整个大九宫格每一列、每一行的数字都不重复。


[历史]
原来“Sudoku”起源于瑞士,是18世纪末大数学家欧拉发明的游戏。于1970 年代首先由美国的一家数学逻辑游戏杂志发表,当时名为 NumberPlace。现今流行的数独于1984年由日本游戏杂志《パズル通信ニコリ》发表并得了现时的名称。数独本是“独立的数字”的省略,因为每一个方格都填上一个个位数。 后来在日本流行起来。直至 2004 年,曾任香港高等法院法官的高乐德( Wayne Gould)在日本旅行的时候,发现杂志的这款游戏,便带回伦敦向《泰晤士报》推介并获得接纳。英国《每日邮报》也于三日后开始连载,使“数独”在英国正式掀起热潮,成为英国当下的流行游戏。其他国家和地区受其影响也开始连载“数独”。现在在几个国家的任何一个书店都可以看到“数独"游戏小册子,还有“ 数独”年历、“数独”游戏机等。


[解法举例]
先注意其中一个方格,限定该方格内可以填写的数字。
注意其中一列(或者其中一个小九宫格),寻找填写某数字的方格。
学过“资料结构”的人,可以尝试用Backtrack试试。
数独的通解方法及步骤:

根据以下方法可以确保最终得到数独的解,而且通过手工运算的时间基本可以控制在1.5个小时,不论难易程度,所以此方法可以作为取得数独答案的一般解法。
1、根据横列、竖列和方格的限制条件排除各个点不可能的数字,并从1-9将各个可能的数字用小字体逐个写进每个空白的格子。(该步骤大约需要15-20分钟,这是求解的初始,务必确保没有遗漏)。

2、审视第一步骤的结果,如果发现某个空格只有一个数字,即确定该空格为这个数字。并根据该数字审视其相关的横列、竖列和方格,并划除相同的数字。(该情况出现的可能往往不多,除了较简单的数独题,但这是一个必要的过程,而且在随后的过程中要反复使用此方法。)

3、审视各个横列、竖列和方格中罗列出的可能的数字结果,若发现某一个数字在各个横列、竖列或方格中出现的次数仅一次,则可以确定该空格的解为此数字。并根据第二条的方法排除与此空格相关列或方格中相同的数字。

4、审视各个横列、竖列和方格中罗列的各个可能的结果,找出相对称的两个数组合的空格(或3个、4个组合),并确定这两个空格(或3个、4个)的数字只可能为这两个数字,即两个数字在这两个空格的位置可以交换,但不可能到该行、该列或该方格的其他位置。根据此结果可以排除相关列或方格罗列出相关数字的可能,并缩小范围。(该步骤处理的难度相对复杂,需要在积累一定经验的基础上进行,也是最终求解的关键)

5、反复使用2、3、4提到的步骤,逐步得到一个一个空格的解,并将先前罗列的各种可能的结果一个一个排除,使可能的范围越来越小,直至得到最后结果。


提供数独在线游戏的网站
1.初级:http://www.51sudoku.com/  数独联盟  
2.有骨灰级:http://sudoku.oubk.com/index.html
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-5 16:46:49 | 显示全部楼层
kofeffect也喜欢数独游戏?
我写过一个玩数独的游戏的:
http://www.emath.ac.cn/download/mathe/sudoku.zip
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-5 17:56:02 | 显示全部楼层
嘎嘎,做ACM题的时候做过,本人喜欢暴搜~~~~~~~~~
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-2-5 18:00:59 | 显示全部楼层
原帖由 mathe 于 2008-2-5 16:46 发表
kofeffect也喜欢数独游戏?
我写过一个玩数独的游戏的:
http://www.emath.ac.cn/download/mathe/sudoku.zip



嘿嘿,还算蛮喜欢滴^_^

你的程序功能很多啊,先玩玩骨灰,
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-6 10:33:31 | 显示全部楼层

回复 2# 的帖子

啊哈,mathe 今天换了头像,是公子还是公主?
这么小,居然就在翻阅《The Art of Computer Programming》,真不简单啊。。。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-6 16:39:33 | 显示全部楼层
是乖乖女,喜欢玩书
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-2-6 21:26:24 | 显示全部楼层
嘿嘿,好可爱滴小小朋友^_^

估计长大了也是个编程高手数学奇才
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-7 08:45:28 | 显示全部楼层
呵呵,这个不期望,看她自己喜欢什么就做什么
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-2-7 11:46:09 | 显示全部楼层
引导是要滴

多在家里摆些数学的玩具,游戏,做些数独的贴图
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-8 16:02:04 | 显示全部楼层
呵呵,这个引导多了,孩子她妈要发彪了。
上次她妈妈从箱底掏出了一个华容道游戏,然后同我爸说这个很难的,一般人都很难玩过去。
我说,交给我吧,半天给你解决问题。
她冲我大叫一声:不许用计算机解
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-5-25 19:28 , Processed in 0.060069 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表