1. 引言
数独是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9 × 9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个宫(3 × 3)内的数字均含1~9,不重复。但凡想了解数独历史的玩家在网络、书籍中搜索时,共同会提到的就是欧拉的“拉丁方块”。拉丁方块的规则:每一行、每一列均含1-N (N即盘面的规格),不重复。这与前面提到的标准数独非常相似,但少了一个宫的规则。本文就拉丁方块和数独的联系展开研究,运用矩阵思想,结合幻方构造拉丁方的初等变换法,使得不需要通过运算只需观察和判断就可以填出9 × 9数独,并且为数独游戏的扩展找到理论依据。
2. 预备知识
定义1 设矩阵
两两互不相等,则称矩阵A是数域F上的n阶异元矩阵。
定义2 [1] 设F矩阵
,
两两互不相等,如果
,则称矩阵A为F上的n阶异元行和幻阵,并称
为F上的n阶异元行和幻阵A的行幻和。
定义3 [1] 设矩阵
,
两两互不相等,如果
,则称矩阵A为F上的n阶异元列和幻阵,并称
为F上的n阶异元列和幻阵A的列幻和。
定义4 [2] 设F是数域,矩阵
,
两两互不相等,如果矩阵A满足下列条件
1)
,
2)
,
则称矩阵A为F上的n阶异元弱和幻方,并称s为F上的n阶异元弱和幻方A的弱幻和。
定义5 [2] 设F是数域,矩阵
,
两两互不相等,如果矩阵A满足下列条件
1)
,
2)
,
3)
,
4)
,
则称矩阵A为F上的n阶异元和幻方,并称s为F上的n阶异元和幻方A的幻和。
定义6 [3] 设
,矩阵
,
两两互不相等,如果矩阵A满足下列条件
1)
,
2)
,
3)
,
4)
,
则称矩阵A为n阶始元和幻方,并称s为n阶始元和幻方A的幻和。
定义7 [4] [5] 设
,矩阵
,
两两互不相等,如果矩阵A满足下列条件
1)
,
2)
,
3)
,
4)
,
则称矩阵A为n阶连元和幻方,并称s为n阶连元和幻方A的幻和。
定义8 [6] 设
,矩阵
,
,当
时,有
,如果
且
时有
恒成立,则称矩阵A为n阶行拉丁方。
定义9 [6] 设
,矩阵
,
,当
时,有
,如果
且
时有
恒成立,则称矩阵A为n阶列拉丁方。
定义10 [7] [8] 设
,矩阵
,
,当
时,有
,如果矩阵A满足下列条件:
1)
且
时有
恒成立;
2)
且
时有
恒成立。
则称矩阵A为n阶拉丁方。
3. 构造拉丁方的初等变换
定理1设矩阵A是数域F上的异元矩阵,构造分块矩阵
,其中
则B是n2阶拉丁方。
证明:由于经过线性变换之后构造出来的分块矩阵B的每一行每一列都含有矩阵A中的所有元素,则分块矩阵B就是n2阶拉丁方。
接下来给出一个三阶异元矩阵的例子来验证。
例1. A为F上的一个三阶异元矩阵
,
,
,
,
,
,
得到
可得B为n2阶拉丁方。并且符合数独游戏的形式,满足每一行、每一列、每一个宫(3*3内的数字均含1~9,不重复。
由该定理可知数独不仅仅局限于1~9,而是可以进一步推广到1-n。同时发现当盘面为9*9时,我们只需要观察和判断就可以填出答案,不过当推广到n*n时,还是避免不了一定的运算才能顺利完成。
推论1设矩阵A是数域F上的行和异元矩阵,构造分块矩阵
,其中
则B是n2阶拉丁方。
推论2设矩阵A是数域F上的列和异元矩阵,构造分块矩阵
,其中
则B是n2阶拉丁方。
推论3设矩阵A是数域F上的异元弱和幻方,构造分块矩阵
,其中
则B是n2阶拉丁方。
推论4设矩阵A是数域F上的异元和幻方,构造分块矩阵
,其中
则B是n2阶拉丁方。
推论5设矩阵A是数域F上的始元和幻方,构造分块矩阵
,其中
则B是n2阶拉丁方。
推论6设矩阵A是数域F上的连元和幻方,构造分块矩阵
,其中
则B是n2阶拉丁方。
由定理1可知推论1至推论6成立。定理1中矩阵A为数域上的异元矩阵,推论1至推论6的证明将条件减弱即可得到。
4. 小结
本文利用矩阵思想,结合幻方,通过分块矩阵和矩阵的初等变换进行拉丁方的构造,定理1给出了数独的理论依据,并且从中可知数独不仅仅局限在1~9之间,而是可以进一步推广。
基金项目
地区科学基金项目(12161086)。
NOTES
*通讯作者。