数独探秘 | 藏在九宫格下的数学六合

khlee · 发表于 2022-4-25 10:09

◆ ◆ ◆

作者 | 致宏

华东师大数学系

数独是什么

数独起源

数独探秘 | 藏在九宫格下的数学六合-2.jpg

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

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

数独玩法

数独探秘 | 藏在九宫格下的数学六合-3.jpg

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

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

数独角逐

作为一项思维游戏，数独在天下各地备受接待。

从2006年起，天下数独锦标赛每年一届，已举行14届。

一些高校也会不定期举行角逐，各大书店不乏数独相关图书。

数独探秘 | 藏在九宫格下的数学六合-4.jpg

华师大桥牌与数独角逐

数独探秘 | 藏在九宫格下的数学六合-5.jpg

上海书城一角

五花八门的数独

数独初盘形状各异，且不乏风趣的例子

数独探秘 | 藏在九宫格下的数学六合-6.jpg

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

数独探秘 | 藏在九宫格下的数学六合-7.jpg

中心空缺矩形最大的数独

数独探秘 | 藏在九宫格下的数学六合-8.jpg

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

数独探秘 | 藏在九宫格下的数学六合-9.jpg

前两行空缺最大的数独

（专杀暴力图解软件）

数独探秘 | 藏在九宫格下的数学六合-10.jpg

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

就让我恋爱一次吧”数独

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

数独与编程

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

纯暴力破解（C）

算法思绪

1.输入初盘数据

2.对第一个空位，依次填1-9，判定行，列，宫格能否稀有字反复，反复则舍弃，否则：

3.对下一个空位，依次填1-9，判定能否反复，反复则舍弃，否则...

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

调集筛算

（Python）

算法思绪：

1.输入初盘数据

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

3.若某个调集只含一个数字，则将该数字填上天点空位，此时空位总数减1。

4.反复2,3，直至一切调集最少含两个数。

5.对第一个空位，将调集合元素依次填入，同算法1，反复至一切空位已填。

数独探秘 | 藏在九宫格下的数学六合-11.jpg

道理图

输入的字符串数据，需要转为数组格式，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[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" 获得。

数独探秘 | 藏在九宫格下的数学六合

使用高级回帖 (可批量传图、插入视频等)快速回复