聊一聊Puzzle:从幻方到数独

2020-04-0214:14:30来源:新浪游戏

  ‘Puzzle’一词在词典中被定义为‘设计用于测验聪慧程度和知识水平的玩具、游戏或者谜题’,一般将其直接称为‘谜题’‘智力游戏’等。Puzzle的表现形式相当多,包含拼图、玩具、题目等等,可谓是无奇不有。同时,基于不同规则的puzzle分别有着不同的玩法和乐趣,并且puzzle的难易度灵活多变,当谜底被解开的时刻能够带给解答者独特的成就感,因此解答puzzle也算是一种相当有意思的娱乐活动,实打实的杀时间利器。

  逻辑谜题(Logic Puzzle)是puzzle中的一个大类。这类puzzle要求解答者综合利用谜题中给出的条件进行分析、推理,进而得到谜题的答案。数独(Sudoku)可能是这类谜题当中最为知名并且影响力最广的了,今天的数独已经发展成了一项风靡世界的游戏,而这项游戏本身,从历史到内涵,仍然有非常多值得说的内容。

  河图、洛书与幻方

  古代有两种祥瑞之兆,分别被称为‘河图’、‘洛书’,二者综合即为典故‘河图洛书’。《周易》记载有‘河出图,洛出书,圣人则之。’河图洛书也被视作是上天降下的旨意,用以辅佐君主治国安邦。

  在河图的传说当中,伏羲氏在孟津县境黄河与图河交汇处遇见了祥兽‘龙马’(……)。龙马这名字来得相当简单粗暴,其为龙与马交配而生,明清时期的书画家王铎在《龙马记》中记载:‘龙马者,天地之精,其为形也,马身而龙鳞,故谓之龙马。高八尺五寸,类骆有翼,蹈水不没,圣人在位,负图出于孟河之中焉。’其中提到龙马背上带了一张图,而伏羲氏便是看了这张图领悟出了八卦。《尚书》中也有‘伏羲王天下,龙马出河,遂则其文以画八卦,谓之河图,及典谟皆历代传宝之。’的说法。

  洛书的传说与河图很相似,相传在大禹治水时,在洛宁县洛河与其支流玄沪河交汇处出现了一只神龟,其背上(也有说法是在下腹壳上)刻有一副点图,谓之洛书。《尚书》记载‘天与禹洛出书,神龟负文而出,列于背,有数至于九。’《大戴礼记》卷八《明堂篇》有‘明堂者,古有之也。凡九室,……明堂月令,赤缀户也,白缀牖也。二九四,七五三,六一八。’

  其中也提到了明堂这种建筑按照洛书的数字‘二九四,七五三,六一八’来排列,这也是比较早的关于洛书用在建筑风水上的记录。虽然在很长一段时间里洛书河图基本都是像这样被用作风水占卜或者描述周易哲学,但是洛书在数学上却有着更值得研究的内容。 

  河图

  洛书

  大话西游2里的召唤兽,另一位大家都熟就不放图了(逃

  首先,将洛书中的图形改写成3×3的九宫格,每格当中填入对应的数字,那么这个九宫格每行每列包括两条对角线的3个数字之和均等于15。现在人们将这种由不同数字(通常为1到阶数平方的连续整数)排列而成且满足行、列、对角线和相等的方阵称为‘幻方’(Magic square),而行列对角线的数字和也被称为‘幻方常数’。目前可以认为洛书是世界上最早被发现的最小幻方。顺便补充一句,由幻方的定义易知2阶幻方是不存在的,留给读者证明((

  除了前文提到的行列和相等之外,幻方当中还存在非常多其他的数学性质。在这里就仅举一个简单的例子:如果将洛书对应的3阶幻方每行视作一个3位数,那么这3个3位数的和与逆转后的3位数和相等,并且对于平方和也成立,即有 

  强烈建议机核加入公式编辑器

  虽然幻方的发现和记载都发生在非常早的时候,但是对于幻方进一步的数学研究要等到南宋时期了,天知道中间过的这几千年都发生了什么。南宋数学家杨辉(就是搞出杨辉三角的那位)是最早对幻方进行数学研究的人,他把研究成果记录在了《续古摘奇算法》里。在书中,他将幻方称为‘纵横图’,并将3阶幻方的构造方法总结为‘九子斜排,上下对易,左右相更,四维挺出,戴九履一,左三右七,二四为肩,六八为足。’,意思是说把1到9按照顺序斜着排成3×3的方阵,交换1和9、3和7的位置后整理便可得到3阶幻方。

  同时,杨辉还给出了4阶到10阶的幻方,且4阶到8阶幻方都给出了两种排列方法,谓之曰‘阴阳图’。

  遗憾的是,高于4阶的幻方构造方法杨辉并未给出说明,不过可以想象在当时的技术水平下这绝对是一件非常繁杂的工作。实际上,杨辉给出的10阶幻方‘百子图’便存在对角线之和不同的错误,而这一错误直到清初才被改正。张潮于《心斋杂俎》中提到了这一问题,对原10阶幻方作出了修改并命名为‘更定百子图’。

  3阶幻方构造方法

  杨辉4阶幻方

  更定百子图

  除了国内,印度和中东地区也被认为是较早开始对幻方进行研究的国家和地区。在1956年,宁夏元代安西王府旧址发掘出了一块幻方铁板,上面刻着用真·阿拉伯文数字制作的6阶阿拉伯幻方,这件文物也被认为是我国数学史上应用阿拉伯数字最早的实物资料。同时也有一种说法认为杨辉的研究是受到这个阿拉伯幻方的影响,不过该说法存在一定争议。目前,这件文物被收藏在陕西历史博物馆内。 

  现在一般认为幻方约在14世纪左右,即文艺复兴时期传入欧洲。幻方在欧洲也很快与神秘学、宗教、星座这类学说联系了起来。一个名为海因里希·康奈利·阿格里帕·冯·内特斯海姆(Heinrich Cornelius Agrippa von Nettesheim)的德国学者制作了3至9阶的幻方,并且用土星、木星等太阳系行星的名字来给幻方分别命名;卢卡·帕西奥利(Luca Pacioli)在其作品《数字的力量》(De Viribus Quantitatis)中提到了3阶和9阶的幻方;更有名的例子出自版画家丢勒在1514年的作品《忧郁 I》,在这副版画中有一个有趣的彩蛋:画中人物背后的强上有一个明显的4阶幻方,同时幻方最后一行中间的两个数字组成了作品的创作年份1514。这个作品的影响非常深远,直到今天仍然有各类文献对其进行解读。

  还有一个值得一提的幻方研究者是印刷在100美元钞票上的那位本杰明·富兰克林,这位先生一生成就颇多,他最有名的幻方创作是一个8阶幻方,并且这个幻方也被称为‘富兰克林幻方’(Franklin Magic Square)。据说他本人曾经表示过当他觉得无聊的时候就会琢磨幻方来解闷。遗憾的是,这个幻方存在和百子图一样的错误:两条对角线的数字之和并不相等。有趣的是后来富兰克林在和别人比较过幻方之后觉得自己的幻方不够牛逼,结果楞是又搞出来一个16阶的特大幻方。当然这个幻方对角线还是存在和不相等的问题,传统艺能。

  Melencolia I, Albrecht Dürer, 1514

  幻方铁板

  富兰克林幻方

  除了正方形之外,幻方的形式也被拓展到了其他图形当中,如三角形、星形、立体情况等,这些不同形式的幻方样式被统称为Magic polygons。杨辉在他的《续古摘奇算法》里给出了几个基于圆形制作的‘幻圆’,并命名为攒九图、八阵图、连环图等等。另一种有趣的形式是蜂窝状的Magic hexagon,国内的文献中有个有趣的译名‘魔蜂窝’。

  魔蜂窝有一个别称叫做‘38 puzzle’,这个名称得来的原因是魔蜂窝任意直线上数字之和均为38。而正因如此,魔蜂窝的制作无比困难,有趣的是最早的魔蜂窝诞生记录可以追溯到1887年,但是之后的几十年中仍然有几个人宣称自己首先发明了魔蜂窝。据说其中一个制作者花了近50年才找到解法,中途还把解法弄丢过一次,因此等到他最终整理好时已经到1962年了。 

  杨辉‘八阵图’

  幻立方体

  魔蜂窝,‘38 puzzle’

  目前,幻方的研究方向众多,并且也有了很多成熟的理论研究成果。幻方本身甚至也被尝试应用到了艺术设计等领域。今天的幻方已经基本摆脱了古时候神秘学的色彩,现在人们一般仅把幻方视为数学问题来研究。由于高阶幻方有着远超于3阶幻方的对称性,并且不同种类、不同阶数的幻方还有着更为复杂的性质,再加上俗话说多一个公式少一半读者,…因此在这里就不再多作详细介绍了。当然,国内外关于幻方的研究文献和科普书籍等材料也非常丰富,有兴趣的各位可以去进行更深入的了解。

  最后再补充一点关于puzzle的内容。实际上,制作幻方本身已经是一个难度较高的谜题了,所以幻方相关的谜题往往都很相似,基本形式就是给出一个图形并要求填上数字,使得各边数字之和相等,或者满足其他条件。这类谜题的区别一般只体现在幻方的各种表现形式上。下图就是一个非常巧妙的谜题,这个图形里需要填入1到11这十一个数字使每条直线上数字之和相等,其中有标记的几个空是题目的突破口。这个谜题非常值得去挑战一下!

  题目出自《趣味数学300题》

  答案

  由拉丁幻方到数独游戏

  在18世纪,大名鼎鼎的数学家欧拉提出过这样一种特殊的方阵:与幻方类似,但是方阵组成的元素不是数字而是拉丁字母;并且每一个字符在每行每列中仅出现一次。这种方阵被称为‘拉丁幻方’(Latin square)。拉丁幻方有很强的实用价值,一个典型的应用案例是将拉丁幻方利用在统计学中的试验设计中,通过使用拉丁幻方的形式来设置安排试验个体,可以有效提高试验的精确性,达到减少误差的目的。这种方法也被称为‘拉丁方设计’。 

  拉丁幻方

  很容易看出,目前的9×9形式的数独就是非常标准的拉丁幻方。当然并不是每个9阶拉丁幻方都是数独,因为拉丁幻方本身并没有限制自身3×3的子幻方(在数独术语中, 这部分被称为‘宫’)也要有不存在重复数字的要求。实际上,数独作为拉丁幻方特殊情况,只占全体拉丁幻方中的极小一部分。全部的标准数独组合数量在大约为6.67×10^21个,而9阶拉丁幻方的全部组合一共有5.5×10^27个,对比相当悬殊。不过即便如此,数独的不同组合情况总数也是一个天文数字,同时每一个数独的盘面都可以对应制作成千上万道不同的题目,因此完全不需要去担心数独的题库会被刷干净。

  虽然欧拉搞出来了拉丁幻方,但是数独的诞生就和他关系不大了。实际上,在19世纪末期便出现了几个刊登在法国报纸上的谜题,但是这几个谜题和现代数独还有着一些细微的差别。目前认为,现代数独的发明者是来自美国的Howard Garns,那时数独被称为Number Place,最早发布在1979年的Dell Pencil Puzzles and Word Games杂志上。虽然名字里带个Dell但是这个杂志和大家熟悉的美国神舟没什么关系,它隶属于Dell Publishing这家美国出版社,并且杂志主打的是填字游戏和纸笔谜题(pencil puzzle)这类内容。目前杂志已经停更,不过相应的谜题集合书籍仍然在制作发售。

  接下来要说到日本。

  1980年时,一位名叫鍜治真起的印刷厂员工和几个人合伙创办了名为‘パズル通信ニコリ’(Nikoli谜题通信)的杂志,这本杂志被认为是日本最早的专注于谜题的商业杂志。早期的Nikoli杂志内容仅仅包括填字游戏、虫食算这种经典题目,而到了1984年,鍜治真起发现了Dell杂志上的填数字谜题,觉得卧槽这玩意儿嫩牛B呢,于是立刻决定也整一个。只是他觉得不太喜欢谜题原本的名字,于是他想出了‘数字は独身に限る’(Suuji wadokushin ni kagiru)这么一说,大意是指‘每个数字只能出现一次’,并且取‘数’‘独’之意,就有了现在的‘数独’(Sudoku)这个名字。

  目前,一道恰当的数独题目要求是可以在不进行‘试数’的情况下,能够利用题目给出的线索全部推理出整个盘面的所有数字,并且题目仅存在唯一解。正因如此,最早的那个数独谜题放在今天是不合格的;它只能通过一个一个数字试错来解决。Nikoli制作的数独还有另一个设计标准,即要求盘面对称。虽然严格来说盘面对称并非设计数独题目的硬性要求,不过这可以视为是传统出题人的一点匠人精神。

  19世纪末期的报纸谜题

  Nikoli数独出版物

  再后来到了1997年,一个名为Wayne Gould的法官在东京机场时随手买了本介绍数独的书,结果他也感觉卧槽这玩意儿嫩牛B呢,楞是在完全不懂日语的情况下和他老婆一块儿沉迷了进去。之后他花了6年的时间自己写了个可以自动解决数独问题的程序,并在大约2004年把数独介绍给了《泰晤士报》,从此之后数独便正式开始火爆全球,成为了现在家喻户晓的游戏。数独传入国内的具体时间已经不可考,大约是在2005年左右。而直到2007年,北京晚报智力休闲数独俱乐部正式加入世界谜题联合会,数独才算是正式被引进了中国大陆,也标志着国内的数独发展正式走上了国际舞台。

  数独也是目前的puzzle系列里发展得最完善的几个项目之一。也许是因为数独发展出了过多变种,从2006年开始,世界谜题锦标赛(World Puzzle Championship)就将数独单独分了出去,同时开始举办世界谜题锦标赛和世界数独锦标赛(World Sudoku Championship)。大赛考察内容除标准数独外,另外包括相当多不同规则的变体数独。中国作为主办国在北京举办了2013年的两场锦标赛,也预计将于2020年在上海会继续举办赛事。

  当时写这段的时候完全没想到今年这个新冠肺炎疫情的情况,不过比赛是安排在10月份,至于会不会继续举办…。。。应该不会受到啥影响吧? 

  ‘Lucky 7’,数度大赛变种谜题之一。要求行列宫及对角线不得有重复数字,折线上为连续数字且灰格均为偶数

  例题解答

  今天的数独不但有了相应的组织和庞大的爱好者群体,甚至除了国际大赛之外,还发展出了相应的段位认定考试。但是如果想通过这类考试的话就务必会涉及到更多的专业知识和更高深的理论,题海战术是免不了的;不过这部分内容不在本文的探讨范围之内,因为我自己对考证这块儿实在不太熟悉,在这里就不班门弄斧啦╮( ̄▽ ̄)╭

  能不能再给力一点啊,老师?

  虽说数独游戏规则非常清晰明了,但是题目的难易程度却千差万别。关于数独盘面的提示数字数量上,有理论证明了数独盘面内在存在唯一解的情况下,最小的提示数字是17个。要注意的是,题目的难易程度和提示数字的数量关系不大,因此偶尔会出现盘面提示数字极为稀疏,但解起来却极为顺畅;或者盘面提示数字特别多但是却一个数都填不进去,感觉哪个数字似乎都没起到啥提示作用的情况。前者一般只需要用到直观的排除法,这类题目被称为‘一刀流’数独;而后者则是高级题目的代表,解题的技巧要求也相当之高。

  另一方面,直接把题目盘面内所有格子的候选数全部填满再一个一个排除的暴力方法看似万能,但是这个方法一是效率奇低,再就是面对那些难题也真不见得管用。而这类题目中的部分‘卡点’往往需要综合各种技巧进行多步推理,才能得出目标格对应的数字。因此,掌握一定的解题技巧在求解难题时是必不可少的。 

  例题1,仅有17提示数字的简单数独,题目来源数度无双

  例题2,难题代表,作者Haasan

  例题1解答

  例题2解答

  最为常用且简洁直观的数独解题技巧包括‘排除法’和‘唯余法’。顾名思义,排除法即利用行列和宫内线索,用‘划线’的方法排除掉不可能填入目标数字的格子;而唯余法则意味着目标格‘除了这个数,别的都不能填’。‘宫排除法’较为直观,相比下‘行列排除法’和‘唯余法’在观察上会更难一点,也比较容易在解题时被忽略。 

  在‘宫排除法’思维下,蓝色格子应填数字1

  在‘行(列)排除法’思维下,蓝色格子应填数字1

  ‘唯余法’,蓝色格子只能填数字5

  让我们更进一步,考虑如下的的情况。虽说下面这个盘面使用‘行排除法’也可以得到第三宫蓝色格子填1的结果,不过如果仔细观察第二宫,容易得知第二宫的数字1只能填在红色的两个格子内。即使我们并不确定究竟1要填进哪一个格子,但是不管哪种情况,这两个格子都给第三宫作了和‘宫排除法’一样的提示。这种情况下的将多个格子视为一个整体进行排除的方法,称为‘区块排除法’。 

  接下来是一个技巧性更强一点的方法。容易发现,一宫内的数字1、2只能填在一宫里的两个红色格子里。虽然我们也同样不能确定1和2的具体位置,但是这两个数字‘占据’了这两个格子,因此对数字5来说,通过简单的宫排除法可以得到一宫内5只能填在蓝色格子的结论。这种将多个数字确定于多个格子的方法在日文中被称为‘予约’,中文常称‘占位法’。 

  另外介绍两种相对比较容易理解的技巧,分别是‘X-wing’和‘唯一矩形’。实际上,需要用上这俩方法的题目基本上就属于难题了,应用上也并不算频繁,这里也就简单提一下就好。 

  ‘唯一矩形’:反向利用数独题目仅有唯一解的技巧,绿色格子如果不填8就会造成多解的情况,因此绿色格子只能填8

  ‘X-wing’,又称‘井桁理论’,3列和7列中数字3只能填入绿格,也意味着3行和7行内红格均不能填入3

  使用列排除法得到X-wing后的应用,八宫中数字1应当填入橙格内

  就我自己的看法来说,区块排除和占位已经属于在直观易懂的情况下学习性价比最高的技巧;更高级的技巧在理解、发现和使用的上难度较高,实在没必要一开始就在技巧上下太多功夫。并且,能够综合应用排除、唯余、占位法,已经足以应付不少的题目了。不过相信你已经学会了以上的几个简单小技巧,那现在去试试综合应用口巴! 

  例1:区块+宫排除得到占位

  例2:宫排除占位和唯余占位

  例3:综合宫列排除得到数组占位后利用区块+列排除得到橙格填数字7

  最后要说的就是有关于数独题库的选择。一般来说,好的数独题目往往会在求解过程中暗藏着对解题人解题技巧的考察。比如说,简单难度下的题目一般只需要用到排除法,中等难度的题目开始用到了占对和唯余法,高级难度就需要综合以上乃至更多的技巧了。但是数独麻烦的地方在于不上手做根本不清楚题目设计的好坏,毕竟它们看上去都差不多。所以,选择一些相对名气较大的组织的作品,能很大程度上降低遇见水题的可能,减少试错成本。

  因此,Nikoli、康思(Conceptis puzzles)这样的老牌谜题设计厂商的产品基本上可以无脑选择。这两家都有自己的移动端app。康思旗下有包括‘康思数独’在内的十几种谜题app,采用每周限免题目加大量收费套题的形式。Nikoli旗下app名为‘Smart Nikoli’,会不定时更新免费的数独和美术馆(Akari)两种谜题。只不过Nikoli更注重出版物那块,这个app属于玩票性质,用的还是观看广告换取代币解锁题目的形式,所以体验上并不算那么好。Nikoli的出版物这两年也开始逐渐有了中译本,不过他们家的书籍内容相当多,值得单开一篇文章介绍了。

  除此之外,独·数之道、欧泊颗数独也都是非常值得推荐的中文数独社区,国内的出版物的话可以选择科学出版社出版,或者由北京市数独运动协会、数独无双,以及一些数独大赛选手或者其他大佬写的书。除了题目质量能够保证之外,这类书籍也会涉及到更多高级技巧的讲解与题目解析思路,方便提高自己的解题水平。至于一些便宜量足的书籍还是谨慎一点比较好,谁知道书里面的内容是不是程序一键生成的…

  …这个看上去就不大靠谱

  虽然这个看上去更不靠谱,然而这本书内容很不错,非常值得推荐

  一点点别的

  这篇文章最早开始写的时候一鼓作气写了大半,后来忙活别的事情去了就搁在了草稿箱里,然后就这样放了了快一年…。。。虽然中间偶尔有几次想起要继续写下去,但是总感觉自己对数独这块儿内容了解得还不够深入,想沉淀下再继续补完。结果拖得太久连文中资料的参考文献都整丢了,内容也还是没深到哪里去。。。…算了,就这样吧。

  回忆起从正式动笔到刚刚写完的这大段时间,真的发生了太多的事情。自己所期待的电影也好游戏也好,都慢慢有了结果,无论是好是坏。比较有意思的就是去年年底的死亡搁浅,通关了后自己还有些恍惚,仿佛死亡搁浅仍旧是一个距离发售遥不可及的游戏,还是得慢慢等待下去。不过我相信不管怎样,事情总会一点点好起来的,你看搁浅都等过来了不是么!

  而在等待以及其他无所事事的空档期中,像是数独这样的puzzle真是极好的杀时间利器。虽说这东西不一定有什么价值,不过,能够在慵懒的午后,拿一根木杆铅笔在纸上写写画画,真的是一件非常惬意的事情。 

  来源:机核

新浪声明:新浪网登载此文出于传递更多信息之目的,并不意味着赞同其观点或证实其描述。
精彩推荐
相关新闻
CGWR

中国游戏排行榜(China Game Weight Rank)是由新浪游戏推出的国内最全面、最专业、最公正、最客观的多平台游戏评测排行榜,包含了目前市场上所有的手游、端游、主机游戏、VR游戏、智能电视游戏及H5游戏,力图为中国玩家打造最值得信赖的游戏推荐平台。

评天下游戏、测产品深浅—新浪中国游戏排行榜CGWR!http://top.sina.com.cn