数独——全民数独，今天你玩了么

kofeffect

文章来源：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

mathe

kofeffect也喜欢数独游戏？
我写过一个玩数独的游戏的:
http://www.emath.ac.cn/download/mathe/sudoku.zip

troy

嘎嘎，做ACM题的时候做过，本人喜欢暴搜~~~~~~~~~

kofeffect

原帖由 mathe 于 2008-2-5 16:46 发表
kofeffect也喜欢数独游戏？
我写过一个玩数独的游戏的:
http://www.emath.ac.cn/download/mathe/sudoku.zip

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

你的程序功能很多啊，先玩玩骨灰，

gxqcn

啊哈，mathe 今天换了头像，是公子还是公主？
这么小，居然就在翻阅《The Art of Computer Programming》，真不简单啊。。。

mathe

是乖乖女，喜欢玩书

kofeffect

嘿嘿，好可爱滴小小朋友^_^

估计长大了也是个编程高手数学奇才

mathe

呵呵，这个不期望，看她自己喜欢什么就做什么

kofeffect

引导是要滴

多在家里摆些数学的玩具，游戏，做些数独的贴图

mathe

呵呵，这个引导多了，孩子她妈要发彪了。
上次她妈妈从箱底掏出了一个华容道游戏，然后同我爸说这个很难的，一般人都很难玩过去。
我说，交给我吧，半天给你解决问题。
她冲我大叫一声：不许用计算机解