◆ ◆ ◆
作者 | 致宏
华东师大数学系
数独是什么
数独起源
数独是源自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个解
数独与数学
数独与群
魔方许多性质由魔方群控制，对魔方群的研究，极大地推进了“上帝之数”的求算。
数独也有关联的变换群，对研究数独起很大作用。
我们通过一些数据来体会：
数独终盘总数约6.67x1021
数独群的群阶约为1.22x1012
群作用下，终盘分成5.47x109个等价类（群轨道），几乎每个等价类包含的数独数目都等于群阶。
Gordon 教授收集了49151个互相不等价的十七数数独， 若按等价类展开，有将近6x106个。
通过群作用，对原先6亿亿个数独的研究，可归结为对表中不到5万个的讨论！
网上能找得到的十七数数独几乎都与列表中的某一个等价，如果有发现新的数独，不妨在网站的个人主页与Gordon教授联系。
代数编程
GAP 和 Magma 是代数编程中专业性较强的两个软件，其中 Magma 是收费软件，而 GAP 自创立之初就规定了免费。
GAP 官方手册
最近翻看 sympy 的官方学习手册，发现原来 Python 在群论，李代数等数学方向上也有应用。
sympy 封面图
虽然 Python 中的函数没有 GAP 丰富，但最基础的工具都有了。
如果感兴趣，再开坑一篇，聊聊编程视角下，数独背后的数学奥秘。
推文中出现的代码，数据，以及 exe 文件，在公众号后台回复 "sudoku" 获取。
