九宫格数独？藏在九宫格下的数学天地

大家好，如果您还对九宫格数独不太了解，没有关系，今天就由本站为大家分享九宫格数独的知识，包括藏在九宫格下的数学天地的问题都会给大家分析到，还望可以解决大家的问题，下面我们就开始吧！

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

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

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

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

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

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

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

形形色色的数独

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

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

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

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

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

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

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

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

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

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

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

'''字符串数据->二维数组数据'''########Python########str2list=lambdas:[[int(s[9*j+i])foriinrange(9)]forjinrange(9)]########C语言########voidstr2arr(char*s,int(*a)[9]){//将字符串数据转化为二维数组inti,j;charc[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'snumber）”问题：所有打乱魔方都可在n步内还原，n的最小值被称为上帝之数。

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

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

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

图片来源：FergalPhillips/SundayTimes

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

文章分享结束，九宫格数独和藏在九宫格下的数学天地的答案你都知道了吗？欢迎再次光临本站哦！