数独介绍_(顾立波).doc

有关数独知识的背景介绍数独Sudoku（日语：）是2005年风靡世界的智力填数游戏，在英国尤为狂热.在标准的99矩阵中，游戏者用从1到9九个数字填满空格，要求横竖各行都是从1到9的数字，而且每一行或者列没有重复数字.与普通的填字游戏相比，Sudoku的优势显而易见，第一，使用阿拉伯数字，全球通用；第二，游戏者具有一般的思考能力就够了；第三，规则非常简单.一数独发展的历史 数独的雏型首先于1970年代由美国的一家数学逻辑游戏杂志发表，当时名为Number Place.现今流行的数独于1984年由日本游戏杂志通信发表并确定为现在的名称.数独本是“独立的数字”的省略，因为每一个方格都填上一个个位数. Sudoku的流行与1997年香港回归有点渊源.新西兰人韦恩古尔德（Wayne Gould），在香港法院系统工作了大半生.随着香港回归的临近，他一边环球旅游，一边打算在退休之后找点事情做.就在退休前去东京的旅行时，他发现一种日本80年代中期出现的数字游戏.它就是Sudoku，这个游戏的推广商是一家叫做Nikoli的出版社，专门从事智力题业务，他们最早从一家叫戴尔杂志（Dell Magazine）的美国智力游戏杂志获得了灵感.早在1979年这家杂志推出了Sudoku，发明人是一位叫霍华德戛纳斯（Howard Garnes）的建筑师. 从来没有玩过Sudoku，古尔德很快就做完了，于是就想着多做一些.他不是数学天才，只不过是对数字感兴趣，一度希望退休了可以编编程序.结果在这样的兴趣驱动下，古尔德 花了6年的时间研究如何用计算机来随机产生Sudoku的矩阵，不想6年之后，当2004年11月，他的一个Sukodu游戏在泰晤士报刊登出来，他的兴趣引发了全球性的“数独迷幻”.Sudoku的规则看起来很简单，然而英国谢菲尔德大学和德国Dresden技术大学的研究表明，这样的99的矩阵，理论上说有6，670，903，752，021，072，936，960种组合.因此，这是一个穷尽一生的游戏.二现代科学家关于数独研究著名的程序是 爱尔兰数学教授麦盖尔 博士（Gary McGuire）的免费程序 SOLVER.EXE ，计算机专业的学生都可以写的出这个程序，. http:/www.math.ie/checker.html 下载这个程序 全部的数独解(Sudoku grids )有 6,670,903,752,021,072,936,960这是贝米耳（Stanley E. Bammel）与罗思坦（Jerome Rothstein）二位数学家计算出来的，有专门研究的报告 http:/www.afjarvis.staff.shef.ac.uk/sudoku/ 登陆这个网址可以查看报告内容 由于同一个数独可以变形，例如左右纵列交换、上下横行交换、数字代码交换(例如1和5交换，2和8、3和4.)重复前面几次之后，就分不清是来自同一个数独，但是专家们还是有法子的. 澳大利亚的大学(The University of Western Australia )教授Gordon Royle 博士利用图形理论，发展出辨识数独变形的方法.将数独谜题利用 Nauty 程序图形转化，然后作比对. .au/gordon/sudokumin.php 如果考虑经过变形的数独不算是新数独，那么数独解的数目会少很多！ 现在有数学、计算机、.等专家们正在研究， 三数独Sudoku背后的四个数学问题德国名画家丢勒的这幅木刻画忧郁症（Melencolia）描述的就是一个因为数学患上忧郁症的天使.让画中天使牵挂的就是墙上挂着的数字迷宫，横向、纵向、对角线数字的和都是34，在最下面一行的中间两格，画家自娱地留下了创作年代1514.古埃及石墙上的数字方阵也许是最古老的数独游戏 1.欧拉与拉丁方作为数学史上最传奇、最多产的大师之一，瑞士数学家欧拉（Euler，17071783）在18世纪研究了一种有趣的数字方阵：考虑一个阶数（亦即行数和列数）为n的方阵，在小格里填入n种符号或数字，在每一行/列中，每一个符号出现且仅出现一次.这种方阵源自中世纪的格盘游戏，其求解过程可归结为“染色问题”一个数学中最古老的问题之一.因为最初随手填入方阵内的是一个个拉丁字母，欧拉将这样的方阵命名为拉丁方.拉丁方在实验设计、数据检验和幻方构造等领域应用极广.2.终盘的可能性通常将一个完成了的数独题目称为终盘.在数独游戏风行后，人们很快便希望知道这个游戏究竟存在多少个终盘形式.对此，德国数学家BertramFelgenhauer在2005年给出了答案：数独的最大可能终盘数为6，670，903，752，021，072，936，960种.另一个方面，考虑到数独游戏的初始数字对称要求，以上结果可能有相当程度的重复，亦即其终盘结果会出现大量的雷同.据此，英国数学家FrazerJarvis和EdRussell给出了更准确的不同终盘数：5，472，730，538.这样一来，有志于破解所有数独题目的玩家又看到了希望的曙光，担心游戏被穷尽而没有游戏可玩的爱好者也不必焦虑：毕竟这个数目和地球人口一样多.3.最小初盘问题与终盘相对应，一个数独游戏给出的初始条件称为初盘.由于规则所限，给出的初盘数字个数必须在32以下.考试中给出的初盘数字为31个.一般常见的初盘数字个数在2228之间，而数独爱好者们常问的一个问题是：最少给出多少个数字，数独游戏才确保有唯一解？具体地说：最少需要在初盘中给出多少个数字，使得移除其中任何一个数字该数独游戏便没有唯一解.事实上，这个问题是数独中最有数学趣味的问题之一，并且至今仍未得到解决.但数学家们估计，这个数字很可能是17.17个数字的最小唯一解初盘是由一名日本数独爱好者发现的.澳大利亚数学家GordonRoyle已经收集了36628个17个数字的唯一解初盘，而爱尔兰数学家Gary McGuire则致力于寻找16个数字的唯一解初盘，但至今仍无发现.部分数学家开始退而求其次，转而寻找只有两个解的16个数字初盘.统计学家根据一个统计学原理曾随机地构造了大量17个数字的初盘，发现其中有唯一解的初盘只有数个未被GordonRoyle教授发现，这意味着，最小唯一解初盘问题的最终答案可能正是174.最大初盘问题与最小初盘问题相反，人们还可以提出最大初盘问题.也就是说：在一个数独初盘中，最多能给出多少个数字，使得再增加一个数字该问题便只有唯一解.相对于最小初盘问题，最大初盘问题容易解决得多.采用倒推法，在初始数字为80的情况下无需说明，缺啥补啥即可；在初始数字为79的初盘中也大约如此，因为考虑到必须满足每一个小九宫格内每个数字出现且仅出现一次，这意味着所缺少的数字都必须出现在同一个九宫格内，考虑到这个情况，还可以依次推出78的初盘也有唯一解.但当初盘中给定数字变为77的时候，该数独游戏便会出现至少两解.四数独正在成为一门科学经过两年的迅速发展，数独游戏已经“侵入”了几乎一切公共传播领域：数以千计的报纸提供数独游戏，数十种数独刊物，全球各地分别成立了数独爱好者团体，电视上已经出现了数独节目，而第一届数独世界锦标赛也在2006年3月意大利举行，在这次锦标赛上，一位35岁的捷克女会计师获得冠军。第二名是哈佛大学的研究生。第三名是在Google公司工作的华裔软件工程师。一个是天天和数字打交道，一个是高智商，另外一个是工程师。与大部分致力于探求数独游戏背后规律的数学家不同，另一些科学家则在尝试如何将数独作为一种新的手段解决其研究中的棘手问题.,康乃尔大学的物理系教授Veit Elser正是这群科学家中的一员.多年来，在Elser教授从事的生物成像技术领域中，相位修复问题始终困扰着研究人员.当观察一件精细的生物样本时，科学家常用的手段是X射线衍射，通过X射线的衍射图案从而获得该样本的详细信息.然而为了得到更理想的衍射图案，科学家不得不对样本进行着色处理，从而对样本有一定程度的破坏.即便是这样，在对衍射结果进行分析的过程中，许多重要的信息仍然会被遗漏，导致这种情况的正是一直以来对相位修复问题始终没有满意的处理方法.直到HIO（HybridInput- Output）算法被发明后，相位修复问题才得到了改善.“但当我仔细研究HIO算法，却发现几乎没有人明白它的原理是什么.”Elser教授说.近两年数独游戏风行欧美，Elser教授也成为了其中一员.听起来就像电影情节一样，当有一天Elser教授在做数独题目放松时，他突然意识到HIO算法的核心可能和数独问题的求解过程有相通之处.通过反复对比，一直被认为是一个谜的HIO算法终于找到了合适的表示手段数独.而这项发现对于数独迷而言也相当重要，因为经过验证，HIO算法对求解数独问题效果极佳.事实上，不光是Elser教授，不同学科的科学家也在把数独作为模型或载体，为自己的研究工作寻找易于接受的表达方式.例如计算机科学家将数独视为测试可满足性（TheSatisfiabilityProblem，简称SAT，是计算机科学的中心问题）