◆ ◆ ◆
作者 | 致宏
華東師大數學系
數獨是什麼
數獨起源
數獨是源自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語言要寫七行。
<code>'''字符串數據 -> 二維數組數據'''
######## 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);}} //轉化字符串
/<code>
運行效率：計算機解數獨，通常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" 獲取。
