|藏在九宫格下的数学世界‘/ 　　

　　作者|洪智。 　　

　　华东师范大学数学系。 　　

　　数独是什么 　　

　　数独起源 　　

　　|藏在九宫格下的数学世界‘/ 　　

　　数独是18世纪起源于瑞典的一种数学游戏。它传入日本后，被命名为数独。 　　

　　数独盘由九个方块组成，所以也叫九方块。 　　

　　数独游戏。 　　

　　|藏在九宫格下的数学世界‘/ 　　

　　给数独初始盘，用逻辑推理，填其他空格。 　　

　　打造每一行，每一列，以及每一宫格中，1-9均出现一次. 　　

　　数独比赛 　　

　　数独作为一种思维游戏，风靡全球。 　　

　　从2006年开始，世界数独锦标赛每年举办一次，共举办14届。 　　

　　一些高校会不定期举办比赛，各大书店都有很多与数独相关的书籍。 　　

　　|藏在九宫格下的数学世界‘/ 　　

　　中国师范大学的桥牌和数独比赛。 　　

　　|藏在九宫格下的数学世界‘/ 　　

　　上海书城一角 　　

　　形形色色的数独 　　

　　数独的初级阶段形式多样，有很多有趣的例子。 　　

　　|藏在九宫格下的数学世界‘/ 　　

　　数最少、完全对称的数独。 　　

　　《九宫格》下隐藏的数学世界/ 　　

　　空白矩形最大的数独。 　　

　　|藏在九宫格下的数学世界‘/ 　　

　　有趣的数独(答案很有趣)。 　　

　　|藏在九宫格下的数学世界‘/ 　　

　　前两行空白最大的数独。 　　

　　(杀人暴力解决软件) 　　

　　《九宫格》下隐藏的数学世界/ 　　

　　“我单身了这么久，老天！ 　　

　　让我恋爱一次。“数独。 　　

　　部分数独取自Matrix67的《牛!各种变态的数独谜题》博客，其中“专杀暴力”的数独从戈登教授收集的十七数数独榜单中筛选出来。 　　

　　数独与编程 　　

　　计算机解数独有两种算法： 　　

　　纯蛮力破解(三) 　　

　　算法思维 　　

　　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.67x1021

2. 数独群的群阶约为1.22x1012

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

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

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

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

代数编程

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

| 藏在九宫格下的数学天地' /> 　　

GAP 官方手册

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

| 藏在九宫格下的数学天地' /> 　　

sympy 封面图

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

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

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

| 藏在九宫格下的数学天地' />