延安大学数学与计算机科学学院，陕西 延安

收稿日期：2021年12月11日；录用日期：2022年1月1日；发布日期：2022年1月14日

摘要

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

关键词

拉丁方，分块矩阵，初等变换，数独

The Method of Elementary Transformation for Constructing Latin Square

Rongrong Zhang, Xingxiang Liu^*

College of Mathematics and Computer Science, Yan’an University, Yan’an Shaanxi

Received: Dec. 11^th, 2021; accepted: Jan. 1^st, 2022; published: Jan. 14^th, 2022

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.

Keywords:Latin Square, Partitioned Matrix, Elementary Transformation, Sudoku

Copyright © 2022 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

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)。

文章引用

张蓉蓉,刘兴祥. 构造拉丁方的初等变换法
The Method of Elementary Transformation for Constructing Latin Square[J]. 应用数学进展, 2022, 11(01): 78-83. https://doi.org/10.12677/AAM.2022.111012

参考文献