数独Sudoku精选教学文档.docx

数独Sudoku精选教学文档.docx

《数独Sudoku精选教学文档.docx》由会员分享，可在线阅读，更多相关《数独Sudoku精选教学文档.docx（6页珍藏版）》请在冰点文库上搜索。

数独Sudoku精选教学文档

数独（Sudoku）

　　数独（Sudoku），一种起源于日本、流行于欧美的数字游戏，虽然进入中国内地的时间不久，但已经占据了很多媒体的游戏版面，吸引越来越多的玩家投身数字的迷宫。

不过数独爱好者们可能不知道，这个小游戏的雏形，却是一个让数学家伤透脑筋的问题。

即使在今天，还有众多研究人员为弄清楚数独背后的规律而绞尽脑汁。

即使是天使也会为数学问题苦思冥想。

德国名画家丢勒的这幅木刻画《忧郁症》（Melencolia）描述的就是一个因为数学患上忧郁症的天使。

让画中天使牵挂的就是墙上挂着的数字迷宫，横向、纵向、对角线数字的和都是34，在最下面一行的中间两格，画家自娱地留下了创作年代1514.

1　欧拉与拉丁方

作为数学史上最传奇、最多产的大师之一，瑞士数学家欧拉（LeonardEuler，1707—1783）在18世纪研究了一种有趣的数字方阵：

考虑一个阶数（亦即行数和列数）为n的方阵，在小格里填入n种符号或数字，在每一行/列中，每一个符号出现且仅出现一次。

这种方阵源自中世纪的格盘游戏，其求解过程可归结为“染色问题”———一个数学中最古老的问题之一。

因为最初随手填入方阵内的是一个个拉丁字母，欧拉将这样的方阵命名为拉丁方（LatinSquare）。

拉丁方在实验设计、数据检验和幻方构造等领域应用极广。

很容易发现，数独其实正是一种特殊的拉丁方。

惟一不同的是，数独加上了两个额外的条件：

一、在每个小九宫格的区域内，每个数字同样出现且只出现一次；二、给出的初始数字必须对称。

2　终盘的可能性

通常将一个完成了的数独题目称为终盘。

在数独游戏风行后，人们很快便希望知道这个游戏究竟存在多少个终盘形式。

对此，德国数学家BertramFelgenhauer在2019年给出了答案：

数独的最大可能终盘数为6，670，903，752，021，072，936，960种。

Felgenhauer的算式为9！

×722×27×27，704，267，971，最后的数字是一个大质数。

虽然这个天文数字已经足够惊人，但考虑到作为一种特殊限制的拉丁方，数独终盘的可能性只是可能存在的九阶拉丁方数目的0.00012%！

另一个方面，考虑到数独游戏的初始数字对称要求，以上结果可能有相当程度的重复，亦即其终盘结果会出现大量的雷同。

据此，英国数学家FrazerJarvis和EdRussell给出了更准确的不同终盘数：

5，472，730，538.这样一来，有志于破解所有数独题目的玩家又看到了希望的曙光，担心游戏被穷尽而没有游戏可玩的爱好者也不必焦虑：

毕竟这个数目和地球人口一样多。

3　最小初盘问题

与终盘相对应，一个数独游戏给出的初始条件称为初盘。

由于规则所限，给出的初盘数字个数必须在32以下。

一般常见的初盘数字个数在22—28之间，而数独爱好者们常问的一个问题是：

最少给出多少个数字，数独游戏才确保有惟一解？

具体地说：

最少需要在初盘中给出多少个数字，使得移除其中任何一个数字该数独游戏便没有惟一解。

事实上，这个问题是数独中最有数学趣味的问题之一，并且至今仍未得到解决。

但数学家们估计，这个数字很可能是17.17个数字的最小惟一解初盘是由一名日本数独爱好者发现的。

澳大利亚数学家GordonRoyle已经收集了36628个17个数字的惟一解初盘，而爱尔兰数学家GaryMcGuire则致力于寻找16个数字的惟一解初盘，但至今仍无发现。

部分数学家开始退而求其次，转而寻找只有两个解的16个数字初盘。

统计学家根据一个统计学原理曾随机地构造了大量17个数字的初盘，发现其中有惟一解的初盘只有数个未被GordonRoyle教授发现，这意味着，最小惟一解初盘问题的最终答案可能正是17：

因为从理论上说，如果16个数字的惟一解终盘存在，那么每一个必将引起65个17个数字惟一解终盘的增加，而在研究中至今没有观察到这一效应。

4　最大初盘问题

与最小初盘问题相反，人们还可以提出最大初盘问题。

也就是说：

在一个数独初盘中，最多能给出多少个数字，使得再增加一个数字该问题便只有惟一解。

相对于最小初盘问题，最大初盘问题容易解决得多。

采用倒推法，在初始数字为80的情况下无需说明，缺啥补啥即可；在初始数字为79的初盘中也大约如此，因为考虑到必须满足每一个小九宫格内每个数字出现且仅出现一次，这意味着所缺少的数字都必须出现在同一个九宫格内，考虑到这个情况，还可以依次推出78的初盘也有惟一解。

但当初盘中给定数字变为77的时候，该数独游戏便会出现至少两解。

数字游戏

“数独”可以被定义为一种逻辑智力拼图游戏，也可以被称为“数字游戏”。

顾名思义，“数独”可以理解为一组独立的数字，将这组数字以一定的规则组合在一定区域内，便是数独游戏的主要内容。

具体地说，拼图是大九宫格（即3格宽×3格高）的正方形状，由9个小九宫格组成。

游戏的目标是在每一个小九宫格中，不重复地填上1至9的数字，让整个大九宫格每一列、每一行的数字都不重复。

一般而言，一条数独题会给出1/3左右的数字作为初始条件，剩下的2/3空白处由读者完成。

也许正是因为规则简单，所以数独才能迅速风靡世界。

既然玩数独游戏无需数学运算或证明，似乎完全可以将其称为“数字游戏”。

传播史

Nikoli是所有数独爱好者需要感谢的第一个名字。

数独游戏在1979年前后已经在美国Dell杂志上刊登，但在众多填字游戏中并未引起特别注意。

直到1984年，日本的填字游戏出版商Nikoli公司的煅治真起从美国发现了这个游戏，决定引入日本并将其命名为Sudoku，意思是“每个数字只能出现一次”。

随着Sudoku游戏在日本国内大受欢迎，Nikoli公司在1986年对其进行了两项改良：

其一是题目中给出的初始数字限定在32个以内，其二是给出数字的分布采用对称形式。

这就是今天我们看到的数独游戏的面貌。

很难解释为何在此后的十多年里，数独游戏一直只在日本国内流行。

但可以肯定的是，将数独游戏重新发现并推广到国际市场的，是一名香港高等法院退休法官、新西兰人高乐德。

他在2019年一次日本旅行中，在书店内发现数独游戏，立刻被其吸引住。

此后高乐德花了六年时间开发数独出题程序，并向英国《泰晤士报》等报社出售其编写的数独题目。

英国市场反应极佳，数独开始风行全球，而高乐德本人也因此获得巨额收入。

经过两年的迅速发展，数独游戏已经“侵入”了几乎一切公共传播领域：

数以千计的报纸提供数独游戏，数十种数独刊物，全球各地分别成立了数独爱好者团体，电视上已经出现了数独节目，而第一届数独世界锦标赛也在今年的3月举行，捷克一名女会计师夺冠。

瑞士数学家莱昂哈德·欧拉

Elser教授

吴硕辛先生

匈牙利建筑学教授和雕塑家厄尔诺·鲁比克

数学家JessicaFridrich女士

具体资料：

数谜（Kakuro）

当大家还在钻研数独Sudoku，究竟填写1至9这几个数字的窍门时，另一个相类的游戏于最近迅速火爆，这就是Kakuro。

Kakuro在英美等地人气急升，它的好玩之处在于既有Sudoku的逻辑推理，还多了加数运算。

在空格内选添1-9中一个数字，最终目的使那些数字加起来之和与所给的数字相等。

说起来简单，实际上想在游戏中过关可不是那么容易的。

Kakuro相比Sudoku更难玩，除了涉及逻辑推理，更要大家计算加数。

与Sudoku一样，是将一串数字加到面板上，大前提是加入的数字是空格旁边数字的总和，还有该总和算式内的数字不能重复。

玩Kakuro，会用到在小学时期的加数运算法，如要填入3个方格，单是总和9便已经有3个配搭，包括1+2+6、1+3+5、2+3+4；再者，数字的次序可以不同，这样便有18个组合，究竟哪个才是正确答案，这就是游戏的最困难地方。

Kakuro是一款在游戏中需要增加运算（加法）的智力游戏，逻辑推理性很强。

与数独玩法相近但趣味更丰富、挑战性更大。

Kakuro的玩法与数独相似，也是由3乘以3的9个方格组成，每个方格又分成3乘以3的9格，在空格内选添1至9中的一个数字，最终目的是使那些数字加起来之和与所给出的数字相等。

■你知道是最先发明数独的吗？

1783年，瑞士数学家莱昂哈德·欧拉发明了一种当时称作“拉丁方块”的游戏，这个游戏是一个n×n的数字方阵，每一行和每一列都是由不重复的n个数字或者字母组成的。

■你知道是哪一本杂志最先推广数独的吗？

19世纪70年代，美国的一家数学逻辑游戏杂志《戴尔铅笔字谜和词语游戏》（DellPuzzleMαgαzines）开始刊登现在称为“数独”的这种游戏，当时人们称之为“数字拼图”，在这个时候，9×9的81格数字游戏才开始成型。

■你知道“数独”这个游戏名称是怎么来的吗？

1984年4月，在日本游戏杂志《字谜通讯Nikoil》上出现了“数独”游戏，提出了“独立的数字”的概念，意思就是“这个数字只能出现一次”或者“这个数字必须是惟一的”，并将这个游戏命名为“数独”（SUDOKU），从此，这个游戏开始风靡全球。

与大部分致力于探求数独游戏背后规律的数学家不同，另一些科学家则在尝试如何将数独作为一种新的手段解决其研究中的棘手问题。

尽管听起来有点不可思议，但他们确实取得了一定进展。

康乃尔大学的物理系教授VeitElser正是这群科学家中的一员。

多年来，在Elser教授从事的生物成像技术领域中，相位修复问题始终困扰着研究人员。

当观察一件精细的生物样本时，科学家常用的手段是X射线衍射，通过X射线的衍射图案从而获得该样本的详细信息。

然而为了得到更理想的衍射图案，科学家不得不对样本进行着色处理，从而对样本有一定程度的破坏。

即便是这样，在对衍射结果进行分析的过程中，许多重要的信息仍然会被遗漏，导致这种情况的正是一直以来对相位修复问题始终没有满意的处理方法。

直到HIO（HybridInput-Output）算法被发明后，相位修复问题才得到了改善。

“但当我仔细研究HIO算法，却发现几乎没有人明白它的原理是什么。

”Elser教授说。

近两年数独游戏风行欧美，Elser教授也成为了其中一员。

听起来就像电影情节一样，当有一天Elser教授在做数独题目放松时，他突然意识到HIO算法的核心可能和数独问题的求解过程有相通之处。

通过反复对比，一直被认为是一个谜的HIO算法终于找到了合适的表示手段———数独。

而这项发现对于数独迷而言也相当重要，因为经过验证，HIO算法对求解数独问题效果极佳。

事实上，不光是Elser教授，不同学科的科学家也在把数独作为模型或载体，为自己的研究工作寻找易于接受的表达方式。

例如计算机科学家将数独视为测试可满足性（TheSatisfiabilityProblem，简称SAT，是计算机科学的中心问题）的绝佳对象，而匹兹堡大学的化学教授们干脆将数独题目作为课堂测验的一种形式，因为他们认为这最能反映一个学生的逻辑能力———当然了，填在空格里的不再是数字，而是一堆化学元素。

手工劳动

怎样出一道数独题

骨灰级数独玩家对用计算机程序编写的数独题目始终抱有成见，认为其偏离了数独的初衷，日本Nikoli公司多年来就一直坚持其出版的所有数独题目皆由人工算出。

对于那些既不擅长编程序，又不愿意费时耗力慢慢推算的数独爱好者而言，吴硕辛先生介绍的一种出题方法可谓简单易行。

吴硕辛先生多年来一直从事高阶幻方研究，其发表的mi（q）理论被誉为是幻方研究的最前沿成果之一。

年届七旬的吴先生最初被数独游戏吸引，也正是因为在其中看到了拉丁方的影子：

“对我们搞幻方的人来说，构造对角拉丁方是最常用的手段之一。

”吴先生在研究中发现，如果将九阶拉丁方（当然空格里填的必须是1-9的数字）与已有的一道数独题相结合，可以很方便地得出一道新的数独题。

具体做法是：

准备任意一个完整的九阶拉丁方（81格都填满，后文以A代表）和任意一道现有的数独题（后文以B代表）。

将B中所出的数字的位置分别标为b1，b2，b3……bn，然后在A中找到相对应的位置a1，a2，a3……an，再将B中b1至bn的数值分别替换为a1至an的数值，空白的格子仍旧留为空白，这样就能得到一个新的数独题，并且保证有解。

数独与魔方

稍加观察即可发现，“数独”中的数字1－9可以被替换为任意不重复的数组，也可以换为a、b、c、d等非数字序列，甚至可以替换为9种不同的颜色，只要这些颜色之间有明显区别。

这让人们想起了80年代风靡全球的魔方游戏，事实上，数独的游戏规则看起来正像是一个平面化了的魔方的逆过程。

魔方（RubiksCube）是匈牙利建筑学教授和雕塑家厄尔诺·鲁比克于1974年发明的机械益智玩具，最初被用于帮助学生们认识空间立方体的组成和结构。

最初的魔方是三阶立方体，每个面上有九个带颜色的小方块，其中包含6个处于面最中心无法移动的块，12个位于棱上的块和8个角块。

一个复原好的魔方六个面各由同一种颜色组成，一般来说，标准的魔方的颜色应该是蓝、白、红、绿、黄和橙色，其中蓝白相对、绿黄相对、红橙相对。

唐宋或更早之前，针对“经学”“律学”“算学”和“书学”各科目，其相应传授者称为“博士”，这与当今“博士”含义已经相去甚远。

而对那些特别讲授“武事”或讲解“经籍”者，又称“讲师”。

“教授”和“助教”均原为学官称谓。

前者始于宋，乃“宗学”“律学”“医学”“武学”等科目的讲授者；而后者则于西晋武帝时代即已设立了，主要协助国子、博士培养生徒。

“助教”在古代不仅要作入流的学问，其教书育人的职责也十分明晰。

唐代国子学、太学等所设之“助教”一席，也是当朝打眼的学官。

至明清两代，只设国子监（国子学）一科的“助教”，其身价不谓显赫，也称得上朝廷要员。

至此，无论是“博士”“讲师”，还是“教授”“助教”，其今日教师应具有的基本概念都具有了。

“师”之概念，大体是从先秦时期的“师长、师傅、先生”而来。

其中“师傅”更早则意指春秋时国君的老师。

《说文解字》中有注曰：

“师教人以道者之称也”。

“师”之含义，现在泛指从事教育工作或是传授知识技术也或是某方面有特长值得学习者。

“老师”的原意并非由“老”而形容“师”。

“老”在旧语义中也是一种尊称，隐喻年长且学识渊博者。

“老”“师”连用最初见于《史记》，有“荀卿最为老师”之说法。

慢慢“老师”之说也不再有年龄的限制，老少皆可适用。

只是司马迁笔下的“老师”当然不是今日意义上的“教师”，其只是“老”和“师”的复合构词，所表达的含义多指对知识渊博者的一种尊称，虽能从其身上学以“道”，但其不一定是知识的传播者。

今天看来，“教师”的必要条件不光是拥有知识，更重于传播知识。

与当今“教师”一称最接近的“老师”概念，最早也要追溯至宋元时期。

金代元好问《示侄孙伯安》诗云：

“伯安入小学，颖悟非凡貌，属句有夙性，说字惊老师。

”于是看，宋元时期小学教师被称为“老师”有案可稽。

清代称主考官也为“老师”，而一般学堂里的先生则称为“教师”或“教习”。

可见，“教师”一说是比较晚的事了。

如今体会，“教师”的含义比之“老师”一说，具有资历和学识程度上较低一些的差别。

辛亥革命后，教师与其他官员一样依法令任命，故又称“教师”为“教员”。

三阶魔方的常用解法由七个步骤组成，一般玩家记住这七个步骤可以在一分钟内将魔方复原。

后经数学家JessicaFridrich女士研究，采用新的方法可以在四个步骤内复原一个三阶魔方，但熟练运用这四个步骤需要记住119个数学公式。