数独秘境：九宫格下的数学探索之旅

◆ ◆ ◆

作者 | 致宏

华东师大数学系

数独是什么

数独起源

数独是源自18世纪瑞典的一种数学游戏，在传入日本后，得名“数独”或“sudoku”。

数独盘面由九个宫格构成，因而也称为九宫格。

数独玩法

给出数独初盘，利用逻辑推理，在其他空格中填数。

使得每一行，每一列，以及每一宫格中，1-9均出现一次。

数独比赛

作为一项思维游戏，数独在世界各地备受欢迎。

从2006年起，世界数独锦标赛每年一届，已举办14届。

一些高校也会不定期举办比赛，各大书店不乏数独相关图书。

华师大桥牌与数独比赛

上海书城一角

形形色色的数独

数独初盘形态各异，且不乏有趣的例子

数字最少且完全对称的数独

中间空白矩形最大的数独

有趣的数独（答案很好玩）

前两行空白最大的数独

（专杀暴力求解软件）

“我单身都这么久了，上天啊

就让我恋爱一次吧”数独

部分数独摘自Matrix67的博客《牛!各种变态的数独谜题》，其中“专杀暴力求解”的数独从Gordon教授收集的十七数数独列表中筛找得到。

数独与编程

计算机解数独，有两种算法思路：

纯暴力破解（C）

算法思路

1.输入初盘数据

2.对第一个空位，依次填1-9，判断行，列，宫格是否有数字重复，重复则舍弃，否则：

3.对下一个空位，依次填1-9，判断是否重复，重复则舍弃，否则...

4.以此类推，直到填完最后一个位置。

集合筛算

（Python）

算法思路：

1.输入初盘数据

2.在空位上填集合，元素为通过行，列，宫格排除后，该位置可填的数字。（参看下图）

3.若某个集合只含一个数字，则将该数字填入所在空位，此时空位总数减1。

4.重复2,3，直至所有集合至少含两个数。

5.对第一个空位，将集合中元素依次填入，同算法1，重复至所有空位已填。

原理图

输入的字符串数据，需要转为数组格式，Python一行代码可以搞定，而同样的效果用C语言要写七行。

'''字符串数据 -> 二维数组数据'''
######## Python ########
str2list = lambda s:[[int(s[9*j+i]) for i in range(9)]for j in range(9)]
######## C语言 ########
void str2arr(char *s, int (*a)[9]){ //将字符串数据转化为二维数组
int i,j;
char c[2];
for(i=0;i<9;i++)
for(j=0;j<9;j++){
c[0] = s[9*i+j]; //截取字符串
a[i][j] = atoi(c);}} //转化字符串

运行效率：计算机解数独，通常1s内搞定。

制作数独图

Python 有丰富的函数库，用于编写 tex 代码和制图很方便，制作思路如下：

1. 函数库 pylatex：用于编写tex代码

2. 正则表达式 re：用于添加tex样式

3. 函数库 sympy：将tex代码导出为图片

参考代码：(长按识别二维码查看)

推送中出现的多数数独图片，均通过代码中函数导出。

数独初盘问题

魔方的上帝之数

魔方界，有著名的“上帝之数（God's number）”问题：所有打乱魔方都可在n步内还原，n的最小值被称为上帝之数。

2010年7月，Tomas Rokicki 等人通过谷歌超算，得到上帝之数为20。

God's number is 20 !

最小初盘问题

数独界也有类似问题，初盘最少给多少个数，可使数独有唯一解？

2012年1月，Gary McGuire的团队通过谷歌超算，得到这个数为17。

Gary McGuire 教授

图片来源：Fergal Phillips/Sunday Times

初盘17个数，有唯一解的数独，被称为十七数数独。

十七数数独的数量众多，数独爱好者Gordon Royle 就收集了49151个。

而初盘16个数，解最少的情况是2个。

十六数数独及其两个解

最大初盘问题

与最小初盘问题相反，人们还可以提出最大初盘问题：初盘最多给多少个数，可以使数独无唯一解？

这个问题在稿纸上便能解决：

初盘78个数，余下3个空位被行列确定，解唯一；

初盘77个数，下边例子解不唯一。

初盘77个数且有二解

综上：

- 初盘最少给17个数，可以使数独有唯一解

- 初盘最多给77个数，可以使数独无唯一解

- 初盘至少给78个数，才能保证数独必有唯一解

- 初盘16个数，数独至少有2个解

数独与数学

数独与群

魔方许多性质由魔方群控制，对魔方群的研究，极大地推进了“上帝之数”的求算。

数独也有关联的变换群，对研究数独起很大作用。

我们通过一些数据来体会：

1. 数独终盘总数约6.67x10²¹

2. 数独群的群阶约为1.22x10¹²

3. 群作用下，终盘分成5.47x10⁹个等价类（群轨道），几乎每个等价类包含的数独数目都等于群阶。

Gordon 教授收集了49151个互相不等价的十七数数独， 若按等价类展开，有将近6x10⁶个。

通过群作用，对原先6亿亿个数独的研究，可归结为对表中不到5万个的讨论！

网上能找得到的十七数数独几乎都与列表中的某一个等价，如果有发现新的数独，不妨在网站的个人主页与Gordon教授联系。

代数编程

GAP 和 Magma 是代数编程中专业性较强的两个软件，其中 Magma 是收费软件，而 GAP 自创立之初就规定了免费。

GAP 官方手册

最近翻看 sympy 的官方学习手册，发现原来 Python 在群论，李代数等数学方向上也有应用。

sympy 封面图

虽然 Python 中的函数没有 GAP 丰富，但最基础的工具都有了。

如果感兴趣，再开坑一篇，聊聊编程视角下，数独背后的数学奥秘。

推文中出现的代码，数据，以及 exe 文件，在公众号后台回复 "sudoku" 获取。