拉丁方（数独）的构造方法
文章目录
前言
因为最近在学习组合数学，里面有专门的一个章节是阐述拉丁方的来源、构造，欧拉提出了是否存在6阶的正交拉丁方问题，欧拉猜测：对应整数6、10、14、16、4k+2、…不存在相应阶数的拉丁方。早在1901年，Tarry就用枚举法验证了欧拉猜测的正确性。（1901年中国签订了《辛丑条约》，瑞典首次颁发诺贝尔奖）课本中也阐述了集中构造拉丁方的方法，现将这些方法做一个整理，以供大家参考。（版权侵删）
一、拉丁方的定义
- 设 n 为正整数，并设 A 为 n 个不同正整数元素的集合。在集合A上的 n 阶拉丁方是一个 n 行 n 列的数组，他的每一项是 A 的元素，使得 A 的 n 个元素的每一个元素在每一行上出现一次，在每一列上出现一次。
- 通常把 A 取为
Z
n
=
{
0
,
1
,
⋯
,
n
−
1
}
\ Z_n = \{0,1,\cdots,n-1\}
Zn={0,1,⋯,n−1},
Z
n
\ Z_n
Zn是指mod n 整数运算
此时我们把拉丁方的行列计数为0，1， ⋯ \ \cdots ⋯，n-1，而不是我们经常用的1,2, ⋯ \ \cdots ⋯，n（1行1列的数组总是只有一个元素组成的拉丁方）
以下为拉丁方例子： [ 0 1 1 0 ] , [ 0 1 2 1 2 0 2 0 1 ] \begin{bmatrix} 0 & 1\\ 1 & 0 \end{bmatrix}\,, \begin{bmatrix} 0 & 1 & 2 \\ 1 & 2 & 0 \\ 2 & 0 & 1 \end{bmatrix} [0110],⎣⎡012120201⎦⎤
二、乘法逆元构造法
设 n 是正整数，r 是
Z
n
\ Z_n
Zn中的非零整数，是的 r 和 n 的GCD为 1。（即互为逆元）设A 为n 行n 列数组，其 i 行j 列上的元素是
a
i
j
=
r
∗
i
+
j
(
m
o
d
n
运
算
)
(
i
,
j
=
0
,
1
,
⋯
,
n
−
1
)
a_{ij} = r*i+j(mod\ n 运算) \ (i,j=0,1,\cdots,n-1)
aij=r∗i+j(mod n运算) (i,j=0,1,⋯,n−1)
则 A 是
Z
n
\ Z_n
Zn上的n 阶拉丁方
三、两个低阶构造高阶法
首先，先用下面4行4列的数组代替
A
1
A_1
A1中的每一项
a
i
j
1
a^1_{ij}
aij1
再按字典序将此数组内的序偶数与0到11的数进行一一对应，便由一个3阶和一个4阶的低阶拉丁方，生成了一个12阶的高阶拉丁方，对应关系如下：
由
A
1
A_1
A1和
B
1
B_1
B1生成的12阶拉丁方如下：
由
A
2
A_2
A2和
B
2
B_2
B2生成的12阶拉丁方如下：
总结
以上就是生成拉丁方的方法，对于我们平常做的数独游戏，通常都是由以上两种方法构造出来的，关键点在于r的选择，不同的r构造出不同的拉丁方。解数独的精髓就是紧紧把握拉丁方的定义（即每行每列不会出现重复的元素），祝各位在数独路上收货快乐！