什么是拉丁方阵:填好的数独也是其中一种

下面这张表,把1、2、3三个数字排成每行每列各出现一次。
1 2 3
2 3 1
3 1 2
这样的表叫作“拉丁方阵”。中文维基百科的拉丁方阵条目这样定义:n × n 的方阵里恰有 n 种不同的元素,每一种元素在同一行或同一列里只出现一次。上面这张表是3阶拉丁方阵。
填好的数独盘面也是拉丁方阵的一种。英文维基百科的 Latin square 条目写道,任何一个数独的答案都是拉丁方阵。这一点在数独和“ナンプレ”有什么不同和数独的答案盘面一共有多少种里简单提过。这篇文章来看拉丁方阵本身。
名称的由来
“拉丁方阵”这个名字来自18世纪的瑞士数学家欧拉。他用拉丁字母作为方阵里的符号。中英文维基百科都写了这个由来。
符号用数字、字母还是颜色都可以。把第一张表里的1换成A,2换成B,3换成C,就成了下面这样。
A B C
B C A
C A B
每行每列里,A、B、C 仍然各出现一次。这还是同一个拉丁方阵。
小的拉丁方阵有多少个
2阶的拉丁方阵只有两个。
1 2 2 1
2 1 1 2
阶数一大,个数就迅速增加。英文维基百科的 Latin square 条目里有按阶数列出的个数表,取前5阶如下。
| 阶数 | 全部拉丁方阵 | 标准形 |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 2 | 1 |
| 3 | 12 | 1 |
| 4 | 576 | 4 |
| 5 | 161,280 | 56 |
“标准形”是指第一行和第一列都按1、2、3……的顺序排列的拉丁方阵。3阶的标准形只有一个,就是本文开头那张表。
同一张表里,9阶拉丁方阵有 5,524,751,496,156,892,842,531,225,600 个。填好的数独盘面有 6,670,903,752,021,072,936,960 种。
数独和拉丁方阵的区别
拉丁方阵只要求每行每列没有重复的符号。数独在这之上再加一条3×3宫的规则。
用4×4来比较一下。4×4的数独用1到4,要求行、列和2×2的宫里都没有重复的数字。
1 2 | 3 4
2 1 | 4 3
3 4 | 1 2
4 3 | 2 1
这张表每行每列都有1到4各一次,所以是拉丁方阵。但左上的2×2宫里,1和2各出现了两次,不能算数独的答案。
把第2行和第3行对调,就成了下面这样。
1 2 | 3 4
3 4 | 1 2
2 1 | 4 3
4 3 | 2 1
这次四个宫里都是1到4各一次。它既是拉丁方阵,也是4×4数独的答案。
4阶拉丁方阵有576个。根据整数数列词典 OEIS 的 A107739,4×4数独的完成盘面有288种。在4阶时,正好一半的拉丁方阵是数独的答案。
1700年的崔锡鼎和欧拉
据英文维基百科的 Latin square 条目,第一个发表9阶拉丁方阵例子的,是朝鲜的数学家崔锡鼎,时间是1700年,比欧拉早67年。
拉丁方阵的一般理论是从欧拉开始的。欧拉在1782年发表了论文,题目意思是“关于一种新魔方阵的研究”,书目信息收在 Euler Archive 的 E530。
36军官问题
这篇论文讨论的,就是所谓的“36军官问题”。英文维基百科的 Mutually orthogonal Latin squares 条目引用了欧拉的原话:从6个不同的团里选出36名军官,排成一个方阵,使横的每一行和竖的每一列里,都有军衔不同、所属团也不同的6个人。
换一种说法,就是用团做一个拉丁方阵,用军衔再做一个拉丁方阵,两个叠在一起时,团和军衔的组合一个也不重复。能这样叠起来的两个拉丁方阵,叫作“正交”的拉丁方阵。
3阶的话可以这样做:
1 2 3 A B C 1A 2B 3C
2 3 1 + C A B = 2C 3A 1B
3 1 2 B C A 3B 1C 2A
右边的表里,1到3和A到C的9种组合各出现一次。欧拉在一个方阵里用拉丁字母,在另一个里用希腊字母,所以这样的一对也叫“希腊拉丁方阵”。
36军官问题,就是问能不能做出6阶的希腊拉丁方阵。欧拉猜想,凡是除以4余2的阶数,包括6在内,都做不出来。Euler Archive 的说明写道,他在论文里举了很多例子,但并没有严格的证明。
6阶的情况欧拉说对了。1901年,加斯东·塔里(Gaston Tarry)用穷举的方法证实了6阶不存在。而7阶以上,欧拉的猜想是错的:除了2阶和6阶,所有大于1的阶数都存在希腊拉丁方阵。
试验设计中的拉丁方阵
拉丁方阵在谜题以外也有用处。据英文维基百科的 Latin square 条目,它被用在农学研究的试验设计里,用来减小试验误差。互相正交的拉丁方阵组,还被用作纠错码。
第三条规则
在拉丁方阵的两条规则上,加上宫这第三条规则,就是数独。9阶完成的盘面仍然超过6.67×10²¹种。数独的规则本身写在数独规则:第一次玩之前要知道的事里,加了其他规则的同类谜题写在数独的种类:对角线、锯齿、杀手等里。
关于 Sudoku365
Sudoku365 是一款可以在 iPhone、iPad 和 Android 上玩的数独应用。盘面是标准的 9×9。有简单、中等、困难、专家四个难度,每个难度 300 题,共 1200 题。有每天一道的每日挑战和连续记录,还可以通过蓝牙两个人对战或合作。
打开“笔记”,就可以在格子里写候选数。把设置里的“从笔记中移除数字”(默认开启)打开,填入正确的数字时,相关格子里相同的笔记会自动擦掉。选中一个格子时,同一行、列、宫和相同数字的格子会高亮。
应用免费,带广告,可以一次性购买“移除广告”来关闭广告。一个人每天坚持的用法写在 Sudoku365 使用技巧 里,第一道题怎么开始,写在 Sudoku365 入门 里。
Sudoku365每日数独,也能两个人玩查看应用 →