构造拉丁方的初等变换法

The Method of Elementary Transformation for Constructing Latin Square

摘要: 利用分块矩阵和矩阵的初等变换相结合的方法，不但给出了拉丁方的构造方法，而且给出了数独游戏存在的理论依据，也为数独扩展提供了可能性。

Abstract: Using the method of combining Partitioned matrix and Elementary transformation of matrix, not only the construction method of Latin square, but also the theoretical basis of the Sudoku is given; it also offers the possibility of Sudoku extension.

1. 引言

数独是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9 × 9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个宫(3 × 3)内的数字均含1~9，不重复。但凡想了解数独历史的玩家在网络、书籍中搜索时，共同会提到的就是欧拉的“拉丁方块”。拉丁方块的规则：每一行、每一列均含1-N (N即盘面的规格)，不重复。这与前面提到的标准数独非常相似，但少了一个宫的规则。本文就拉丁方块和数独的联系展开研究，运用矩阵思想，结合幻方构造拉丁方的初等变换法，使得不需要通过运算只需观察和判断就可以填出9 × 9数独，并且为数独游戏的扩展找到理论依据。

2. 预备知识

定义1 设矩阵 $A={\left(a_{ij}\right)}_{n\times n}\in F^{n\times n}$ 两两互不相等，则称矩阵A是数域F上的n阶异元矩阵。

定义2 [1] 设F矩阵 $A={\left(a_{ij}\right)}_{n\times n}\in F^{n\times n}$， $a_{ij}\left(i,j=1,2,\cdots ,n\right)$ 两两互不相等，如果 $A\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{E}_i}\left(n,1\right)\right)=s_r\left({\displaystyle \underset{i=1}{\overset{m}{\sum }}{E}_i}\left(m,1\right)\right)$，则称矩阵A为F上的n阶异元行和幻阵，并称 $s_r$ 为F上的n阶异元行和幻阵A的行幻和。

定义3 [1] 设矩阵 $A={\left(a_{ij}\right)}_{n\times n}\in F^{n\times n}$， $a_{ij}\left(i,j=1,2,\cdots ,n\right)$ 两两互不相等，如果 $\left({\displaystyle \underset{j=1}{\overset{m}{\sum }}{E}_j}\left(1,m\right)\right)A=s_c\left({\displaystyle \underset{j=1}{\overset{n}{\sum }}{E}_j}\left(1,n\right)\right)$，则称矩阵A为F上的n阶异元列和幻阵，并称 $s_c$ 为F上的n阶异元列和幻阵A的列幻和。

定义4 [2] 设F是数域，矩阵 $A={\left(a_{ij}\right)}_{n\times n}\in F^{n\times n}$， $a_{ij}\left(i,j=1,2,\cdots ,n\right)$ 两两互不相等，如果矩阵A满足下列条件

1) $A\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{E}_i}\left(n,1\right)\right)=s\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{E}_i}\left(n,1\right)\right)$，

2) $\left({\displaystyle \underset{j=1}{\overset{n}{\sum }}{E}_j}\left(1,n\right)\right)A=s\left({\displaystyle \underset{j=1}{\overset{n}{\sum }}{E}_j}\left(1,n\right)\right)$，

则称矩阵A为F上的n阶异元弱和幻方，并称s为F上的n阶异元弱和幻方A的弱幻和。

定义5 [2] 设F是数域，矩阵 $A={\left(a_{ij}\right)}_{n\times n}\in F^{n\times n}$， $a_{ij}\left(i,j=1,2,\cdots ,n\right)$ 两两互不相等，如果矩阵A满足下列条件

1) $A\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{E}_i}\left(n,1\right)\right)=s\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{E}_i}\left(n,1\right)\right)$，

2) $\left({\displaystyle \underset{j=1}{\overset{n}{\sum }}{E}_j}\left(1,n\right)\right)A=s\left({\displaystyle \underset{j=1}{\overset{n}{\sum }}{E}_j}\left(1,n\right)\right)$，

3) $\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{E}_i}\left(1,n\right)\right)A\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{E}_i}\left(n,1\right)\right)=s$，

4) $\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{E}_i}\left(1,n\right)\right)A\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{E}_{n+1-i}}\left(n,1\right)\right)=s$，

则称矩阵A为F上的n阶异元和幻方，并称s为F上的n阶异元和幻方A的幻和。

定义6 [3] 设 $F_1=\left\{i|i\left(i=1,2,\cdots ,n^2\right)\right\}$，矩阵 $A={\left(a_{ij}\right)}_{n\times n}\in F_1^{n\times n}$， $a_{ij}\left(i,j=1,2,\cdots ,n\right)$ 两两互不相等，如果矩阵A满足下列条件

1) $A\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{E}_i}\left(n,1\right)\right)=s\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{E}_i}\left(n,1\right)\right)$，

2) $\left({\displaystyle \underset{j=1}{\overset{n}{\sum }}{E}_j}\left(1,n\right)\right)A=s\left({\displaystyle \underset{j=1}{\overset{n}{\sum }}{E}_j}\left(1,n\right)\right)$，

3) $\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{E}_i}\left(1,n\right)\right)A\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{E}_i}\left(n,1\right)\right)=s$，

4) $\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{E}_i}\left(1,n\right)\right)A\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{E}_{n+1-i}}\left(n,1\right)\right)=s$，

则称矩阵A为n阶始元和幻方，并称s为n阶始元和幻方A的幻和。

定义7 [4] [5] 设 $F_{\text{2}}=\left\{a+i|i\left(i=1,2,\cdots ,n^2\right),a\in Z\right\}$，矩阵 $A={\left(a_{ij}\right)}_{n\times n}\in F_2^{n\times n}$， $a_{ij}\left(i,j=1,2,\cdots ,n\right)$ 两两互不相等，如果矩阵A满足下列条件

1) $A\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{E}_i}\left(n,1\right)\right)=s\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{E}_i}\left(n,1\right)\right)$，

2) $\left({\displaystyle \underset{j=1}{\overset{n}{\sum }}{E}_j}\left(1,n\right)\right)A=s\left({\displaystyle \underset{j=1}{\overset{n}{\sum }}{E}_j}\left(1,n\right)\right)$，

3) $\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{E}_i}\left(1,n\right)\right)A\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{E}_i}\left(n,1\right)\right)=s$，

4) $\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{E}_i}\left(1,n\right)\right)A\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{E}_{n+1-i}}\left(n,1\right)\right)=s$，

则称矩阵A为n阶连元和幻方，并称s为n阶连元和幻方A的幻和。

定义8 [6] 设 $F_{\text{3}}=\left\{x_i|i=1,2,\cdots ,n\right\}$，矩阵 $A={\left(a_{ij}\right)}_{n\times n}\in F_3^{n\times n}$， $\forall i,j\in \left\{1,2,\cdots ,n\right\}$，当 $i\ne j$ 时，有 $x_i\ne x_j$，如果 $\forall i,j,k\in \left\{1,2,\cdots ,n\right\}$ 且 $j\ne k$ 时有 $a_{ij}\ne a_{ik}$ 恒成立，则称矩阵A为n阶行拉丁方。

定义9 [6] 设 $F_{\text{3}}=\left\{x_i|i=1,2,\cdots ,n\right\}$，矩阵 $A={\left(a_{ij}\right)}_{n\times n}\in F_3^{n\times n}$， $\forall i,j\in \left\{1,2,\cdots ,n\right\}$，当 $i\ne j$ 时，有 $x_i\ne x_j$，如果 $\forall i,j,k\in \left\{1,2,\cdots ,n\right\}$ 且 $i\ne j$ 时有 $a_{ik}\ne a_{jk}$ 恒成立，则称矩阵A为n阶列拉丁方。

定义10 [7] [8] 设 $F_{\text{3}}=\left\{x_i|i=1,2,\cdots ,n\right\}$，矩阵 $A={\left(a_{ij}\right)}_{n\times n}\in F_3^{n\times n}$， $\forall i,j\in \left\{1,2,\cdots ,n\right\}$，当 $i\ne j$ 时，有 $x_i\ne x_j$，如果矩阵A满足下列条件：

1) $\forall i,j,k\in \left\{1,2,\cdots ,n\right\}$ 且 $j\ne k$ 时有 $a_{ij}\ne a_{ik}$ 恒成立；

2) $\forall i,j,k\in \left\{1,2,\cdots ,n\right\}$ 且 $i\ne j$ 时有 $a_{ik}\ne a_{jk}$ 恒成立。

则称矩阵A为n阶拉丁方。

3. 构造拉丁方的初等变换

定理1设矩阵A是数域F上的异元矩阵，构造分块矩阵 $B={\left(B_{ij}\right)}_{n\times n}$，其中

$\begin{array}{c}{B}_{ij}={\left(P_{n-1,n}{P}_{n-2,n-1}\cdots P_{2,3}{P}_{1,2}\right)}^{i-1}A{\left(P_{1,2}{P}_{2,3}\cdots P_{n-2,n-1}{P}_{n-1,n}\right)}^{j-1}\\ ={\left({\displaystyle \underset{n-1}{\overset{1}{\prod }}{P}_{i,i+1}}\right)}^{i-1}A{\left({\displaystyle \underset{1}{\overset{n-1}{\prod }}{P}_{i,i+1}}\right)}^{j-1}\end{array}$

则B是n²阶拉丁方。

证明：由于经过线性变换之后构造出来的分块矩阵B的每一行每一列都含有矩阵A中的所有元素，则分块矩阵B就是n²阶拉丁方。

接下来给出一个三阶异元矩阵的例子来验证。

例1. A为F上的一个三阶异元矩阵

$A=\left(\begin{array}{ccc}3& 1& 5\\ 4& 2& 6\\ 7& 9& 8\end{array}\right)$， $B_{12}=\left(\begin{array}{ccc}4& 2& 6\\ 7& 9& 8\\ 3& 1& 5\end{array}\right)$， $B_{13}=\left(\begin{array}{ccc}7& 9& 8\\ 3& 1& 5\\ 4& 2& 6\end{array}\right)$

$B_{21}=\left(\begin{array}{ccc}1& 5& 3\\ 2& 6& 4\\ 9& 8& 7\end{array}\right)$， $B_{22}=\left(\begin{array}{ccc}2& 6& 4\\ 9& 8& 7\\ 1& 5& 3\end{array}\right)$， $B_{23}=\left(\begin{array}{ccc}9& 8& 7\\ 1& 5& 3\\ 2& 6& 4\end{array}\right)$

$B_{31}=\left(\begin{array}{ccc}5& 3& 1\\ 6& 4& 2\\ 8& 7& 9\end{array}\right)$， $B_{32}=\left(\begin{array}{ccc}6& 4& 2\\ 8& 9& 7\\ 5& 3& 1\end{array}\right)$， $B_{33}=\left(\begin{array}{ccc}8& 7& 9\\ 5& 3& 1\\ 6& 4& 2\end{array}\right)$

得到

$B=\left(\begin{array}{ccc}\left(\begin{array}{lll}3\hfill & 1\hfill & 5\hfill \\ 4\hfill & 2\hfill & 6\hfill \\ 7\hfill & 9\hfill & 8\hfill \end{array}\right)& \left(\begin{array}{lll}4\hfill & 2\hfill & 6\hfill \\ 7\hfill & 9\hfill & 8\hfill \\ 3\hfill & 1\hfill & 5\hfill \end{array}\right)& \left(\begin{array}{lll}7\hfill & 9\hfill & 8\hfill \\ 3\hfill & 1\hfill & 5\hfill \\ 4\hfill & 2\hfill & 6\hfill \end{array}\right)\\ \left(\begin{array}{lll}1\hfill & 5\hfill & 3\hfill \\ 2\hfill & 6\hfill & 4\hfill \\ 9\hfill & 8\hfill & 7\hfill \end{array}\right)& \left(\begin{array}{lll}2\hfill & 6\hfill & 4\hfill \\ 9\hfill & 8\hfill & 7\hfill \\ 1\hfill & 5\hfill & 3\hfill \end{array}\right)& \left(\begin{array}{lll}9\hfill & 8\hfill & 7\hfill \\ 1\hfill & 5\hfill & 3\hfill \\ 2\hfill & 6\hfill & 4\hfill \end{array}\right)\\ \left(\begin{array}{lll}5\hfill & 3\hfill & 1\hfill \\ 6\hfill & 4\hfill & 2\hfill \\ 8\hfill & 7\hfill & 9\hfill \end{array}\right)& \left(\begin{array}{lll}6\hfill & 4\hfill & 2\hfill \\ 8\hfill & 7\hfill & 9\hfill \\ 5\hfill & 3\hfill & 1\hfill \end{array}\right)& \left(\begin{array}{lll}8\hfill & 9\hfill & 7\hfill \\ 5\hfill & 3\hfill & 1\hfill \\ 6\hfill & 4\hfill & 2\hfill \end{array}\right)\end{array}\right)$

可得B为n²阶拉丁方。并且符合数独游戏的形式，满足每一行、每一列、每一个宫(3*3内的数字均含1~9，不重复。

由该定理可知数独不仅仅局限于1~9，而是可以进一步推广到1-n。同时发现当盘面为9*9时，我们只需要观察和判断就可以填出答案，不过当推广到n*n时，还是避免不了一定的运算才能顺利完成。

推论1设矩阵A是数域F上的行和异元矩阵，构造分块矩阵 $B={\left(B_{ij}\right)}_{n\times n}$，其中

$\begin{array}{c}{B}_{ij}={\left(P_{n-1,n}{P}_{n-2,n-1}\cdots P_{2,3}{P}_{1,2}\right)}^{i-1}A{\left(P_{1,2}{P}_{2,3}\cdots P_{n-2,n-1}{P}_{n-1,n}\right)}^{j-1}\\ ={\left({\displaystyle \underset{n-1}{\overset{1}{\prod }}{P}_{i,i+1}}\right)}^{i-1}A{\left({\displaystyle \underset{1}{\overset{n-1}{\prod }}{P}_{i,i+1}}\right)}^{j-1}\end{array}$

则B是n²阶拉丁方。

推论2设矩阵A是数域F上的列和异元矩阵，构造分块矩阵 $B={\left(B_{ij}\right)}_{n\times n}$，其中

$\begin{array}{c}{B}_{ij}={\left(P_{n-1,n}{P}_{n-2,n-1}\cdots P_{2,3}{P}_{1,2}\right)}^{i-1}A{\left(P_{1,2}{P}_{2,3}\cdots P_{n-2,n-1}{P}_{n-1,n}\right)}^{j-1}\\ ={\left({\displaystyle \underset{n-1}{\overset{1}{\prod }}{P}_{i,i+1}}\right)}^{i-1}A{\left({\displaystyle \underset{1}{\overset{n-1}{\prod }}{P}_{i,i+1}}\right)}^{j-1}\end{array}$

则B是n²阶拉丁方。

推论3设矩阵A是数域F上的异元弱和幻方，构造分块矩阵 $B={\left(B_{ij}\right)}_{n\times n}$，其中

$\begin{array}{c}{B}_{ij}={\left(P_{n-1,n}{P}_{n-2,n-1}\cdots P_{2,3}{P}_{1,2}\right)}^{i-1}A{\left(P_{1,2}{P}_{2,3}\cdots P_{n-2,n-1}{P}_{n-1,n}\right)}^{j-1}\\ ={\left({\displaystyle \underset{n-1}{\overset{1}{\prod }}{P}_{i,i+1}}\right)}^{i-1}A{\left({\displaystyle \underset{1}{\overset{n-1}{\prod }}{P}_{i,i+1}}\right)}^{j-1}\end{array}$

则B是n²阶拉丁方。

推论4设矩阵A是数域F上的异元和幻方，构造分块矩阵 $B={\left(B_{ij}\right)}_{n\times n}$，其中

$\begin{array}{c}{B}_{ij}={\left(P_{n-1,n}{P}_{n-2,n-1}\cdots P_{2,3}{P}_{1,2}\right)}^{i-1}A{\left(P_{1,2}{P}_{2,3}\cdots P_{n-2,n-1}{P}_{n-1,n}\right)}^{j-1}\\ ={\left({\displaystyle \underset{n-1}{\overset{1}{\prod }}{P}_{i,i+1}}\right)}^{i-1}A{\left({\displaystyle \underset{1}{\overset{n-1}{\prod }}{P}_{i,i+1}}\right)}^{j-1}\end{array}$

则B是n²阶拉丁方。

推论5设矩阵A是数域F上的始元和幻方，构造分块矩阵 $B={\left(B_{ij}\right)}_{n\times n}$，其中

$\begin{array}{c}{B}_{ij}={\left(P_{n-1,n}{P}_{n-2,n-1}\cdots P_{2,3}{P}_{1,2}\right)}^{i-1}A{\left(P_{1,2}{P}_{2,3}\cdots P_{n-2,n-1}{P}_{n-1,n}\right)}^{j-1}\\ ={\left({\displaystyle \underset{n-1}{\overset{1}{\prod }}{P}_{i,i+1}}\right)}^{i-1}A{\left({\displaystyle \underset{1}{\overset{n-1}{\prod }}{P}_{i,i+1}}\right)}^{j-1}\end{array}$

则B是n²阶拉丁方。

推论6设矩阵A是数域F上的连元和幻方，构造分块矩阵 $B={\left(B_{ij}\right)}_{n\times n}$，其中

$\begin{array}{c}{B}_{ij}={\left(P_{n-1,n}{P}_{n-2,n-1}\cdots P_{2,3}{P}_{1,2}\right)}^{i-1}A{\left(P_{1,2}{P}_{2,3}\cdots P_{n-2,n-1}{P}_{n-1,n}\right)}^{j-1}\\ ={\left({\displaystyle \underset{n-1}{\overset{1}{\prod }}{P}_{i,i+1}}\right)}^{i-1}A{\left({\displaystyle \underset{1}{\overset{n-1}{\prod }}{P}_{i,i+1}}\right)}^{j-1}\end{array}$

则B是n²阶拉丁方。

由定理1可知推论1至推论6成立。定理1中矩阵A为数域上的异元矩阵，推论1至推论6的证明将条件减弱即可得到。

4. 小结

本文利用矩阵思想，结合幻方，通过分块矩阵和矩阵的初等变换进行拉丁方的构造，定理1给出了数独的理论依据，并且从中可知数独不仅仅局限在1~9之间，而是可以进一步推广。

基金项目

地区科学基金项目(12161086)。

NOTES

^*通讯作者。