◆ ◆ ◆

作者 | 緻宏

華東師大數學系

數獨是什麼

數獨起源

數獨是源自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" 獲取。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!