微信号:MathAndAlgorithm

介绍:从生活中挖掘数学之美,在实践中体验算法之奇,魅力旅程,从此开始!

拉丁方阵——数独的起源与发展

2018-06-13 21:03 算法与数学之美
1

数独起源与拉丁方阵

提到数独(sudoku),大家并不陌生,这是一种源自于瑞士、发展于美国、日本,风靡于全球的逻辑游戏,玩家需要根据9X9的方格中已知的数字,推理出剩余空格的数字,并满足每一行、每一列、每一个宫内的数字均包含1-9,九个数字且不重复。数独规则简洁、玩法简单,需要考验玩家逻辑与推理能力。


说到数独的起源,则要追溯到18世纪的欧洲,据说普鲁士的腓(féi)特列大帝曾组成一支仪仗队。仪仗队共有36名军官,来自6支部队,每支部队中,上校、中校、少校、上尉、中尉、少尉各一名。他希望这36名军官排成6×6的方阵,方阵的每一行,每一列的6名军官来自不同的部队并且军衔各不相同。后来,他去求教瑞士著名的大数学家欧拉。欧拉发现这是一个不可能完成的任务。


来自n个部队的n种军衔的n×n名军官,如果能排成一个正方形,每一行,每一列的n名军官来自不同的部队并且军衔各不相同,那么就称这个方阵叫正交拉丁方阵。

欧拉猜测在

n=2,6,10,14,18,…

时,正交拉丁方阵不存在。然而到了上世纪60年代,人们用计算机造出了n=10的正交拉丁方阵,推翻了欧拉的猜测。现在已经知道,除了n=2,6以外,其余的正交拉丁方阵都存在,而且有多种构造的方法。


2

如果你手边有扑克牌,可以自己动手制作一个拉丁方阵。用四种花色(梅花,方块,红心,黑桃)的1(即A)、2、3、4共16张牌,将它们排成4×4的方阵,每一行,每一列四种花色俱全,并且都有1、2、3、4。



这个方阵中不仅满足了每行每列花色、数字都不相同,还有其它的许多特点:

1. 一条对角线(从左上到右下)上全是4,另一条对角线(从右上到左下)上全是A。

2. 方块与梅花是左右对称的,红桃与黑桃也是左右对称的。就是说,如果沿中间的竖线将图对折,方块与梅花相合,红桃与黑桃相合。

3. 方块与黑桃,梅花与红桃上下对称。就是说,如果沿中间的横线将图对折,方块和黑桃相合,梅花与红桃相合。

4. A与4,2与3左右对称。

5. 两条对角线上四种四种花色齐全。

6. 方块与红桃中心对称,黑桃与梅花中心对称,就是说,如果将图形绕中心(图中横线与竖线的点)旋转180°,左上的方块与右下的红桃相合。


3

拉丁方阵体现着“数学美”:整齐、对称、有规律、简单、自然,当然也引发了人们对于拉丁方格更为具体的研究。1783年,瑞士数学家莱昂哈德·欧拉发明了一种当时称作“拉丁方块”(Latin Square)的游戏,这个游戏是一个n×n的数字方阵,每一行和每一列都是由不重复的n个数字或者字母组成的。其实拉丁方块就是没有宫的标准数独,只有两个限制条件,即行、列中的符号不能相同,这就是数独的雏形。不过相比于三条限制的数独(每行、每列、每宫)趣味性与难度都低了不少,所以这个游戏并没有在全球风靡起来。


4


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

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

1984年4月,在日本游戏杂志《字谜通讯Nikoil》(《パズル通信ニコリ》)上出现了“数独”游戏,提出了“独立的数字”的概念,意思就是“这个数字只能出现一次”或者“这个数字必须是惟一的”,并将这个游戏命名为“数独”(SU DOKU),其中“su”是数字的意思,“doku”是单一的意思,

一位前任香港高等法院的新西兰籍法官高乐德(Wayne Gould)在1997年3月到日本东京旅游时,无意中发现了。他首先在英国的《泰晤士报》上发表,不久其他报纸也发表,很快便风靡全英国,之后他用了6年时间编写了电脑程式,并将它放在网站上,使这个游戏很快在全世界流行。从此,这个游戏开始风靡全球。


下面就是一个拉丁方阵:需要把数字1-9填入下面的方格中,保证每行每列的数字都不相同,挑战一下,你能够完成它吗?


∑编辑 | Gemini

算法数学之美微信公众号欢迎赐稿

稿件涉及数学、物理、算法、计算机、编程等相关领域,经采用我们将奉上稿酬。

投稿邮箱:math_alg@163.com


 
算法与数学之美 更多文章 仅剩296个免费名额,AI工程师进阶必修课今日领取 数学思维与编程思维怎样可以完美的结合 众咖齐聚!2018智能汽车跨界融合高峰论坛开幕在即 为什么强化学习会成为当下机器学习最火的研究领域? 阿里、京东高级算法专家讲述数学在企业中的应用
猜您喜欢 【达内新闻】达内携手猎聘网启动“IT新锐”评选 寻找青春榜样 知道在哪里画条线么? 技术干货 | 引用计数 vs. GC MVP 与牛人 技术变化那么快,程序员如何做到不被淘汰?