數(shù)獨游戲和長久以來的世界難題

18 世紀(jì)末，瑞士數(shù)學(xué)家歐拉發(fā)明了一種叫做“拉丁方陣（Latin Square）”的游戲。雖然最初這個游戲并沒有風(fēng)靡起來，但隨著時間的推移，在 20 世紀(jì) 70 年代的美國，這個游戲以“數(shù)字拼圖（Number Place）”的名字迅速流行起來，之后逐漸流傳到日本、英國，到現(xiàn)在已經(jīng)成為了紅遍全球的智力游戲。

數(shù)獨游戲基本規(guī)則是這樣的：在一個九宮格中給出一些初始數(shù)字。玩家需要在九宮格內(nèi)填入缺失的數(shù)字（1 - 9），保證：

每一行的 9 個數(shù)字各不相同

每一列的 9 個數(shù)字各不相同

每一個用粗線標(biāo)識出的 3 × 3 的小正方形內(nèi) 9 個數(shù)字也各不相同

雖然規(guī)則非常簡單，但其中包含的信息卻毫不簡單。數(shù)學(xué)家 Bertram Felgenhauer 在 2005 年證明，數(shù)獨的解共有 9! × 722 × 27 × 27,704,267,971 種不同的可能組合，上面這個乘式的最后一個數(shù)還是一個質(zhì)數(shù)。

一個經(jīng)典的數(shù)獨。圖像來源：wikipedia

而如此多變的變化，無疑也給數(shù)學(xué)家們出了不少難題。其中一個被討論了很久的問題是， 至少給定多少個初始數(shù)字，數(shù)獨才會有唯一解？ 此前已經(jīng)有人給出了一些包含 17 個初始數(shù)字的數(shù)獨，并利用計算機(jī)證明了其解是唯一的（對于某個給定了 17 個初始數(shù)字的數(shù)獨，計算機(jī)枚舉了所有可能的排列情況，只找到一個解），從而證明了 17 個初始數(shù)字的數(shù)獨是可以存在唯一解的。但是長久以來都沒有人知道， 16 個初始數(shù)字的數(shù)獨是否存在唯一解。終于，在 2012 的元旦，都柏林大學(xué)（University College Dublin）的數(shù)學(xué)家們給出了 答案：16 個初始數(shù)字的數(shù)獨不存在唯一解。

有沒有解試出來

消息一出，媒體爭相報道，報道中不乏復(fù)雜的算法、超級計算機(jī)等“雖然不知道在說什么，但看起來很厲害”的詞匯。事實上，研究人員用來證明這個問題的方法用一個字就可以總結(jié)，那就是——試。

解決這個問題幾位數(shù)學(xué)家最初的想法非?？蓯郏?只要把每一種有 16 個初始數(shù)字的數(shù)獨都嘗試著填一遍，自然就知道答案了。 但很可惜，因為數(shù)獨的組合實在是太多了，所以即使是現(xiàn)在最快的計算機(jī)，也不可能在我們的有生之年窮盡所有的組合。因此，必須用一些數(shù)學(xué)的方法來減少嘗試的次數(shù)，這個想法才能夠?qū)崿F(xiàn)。

他們發(fā)現(xiàn)，數(shù)獨雖然有很多種可能的組合，但是其中一些其實是等價的。如下圖，可以看到交換第一列和第二列對整個數(shù)獨并沒有影響。實際上任意一個合法數(shù)獨的解交換兩列后，都可以構(gòu)成一個新的合法數(shù)獨，而這個新數(shù)獨和原數(shù)獨就可以看做是等價的。

兩種等價的數(shù)獨組合

三位數(shù)學(xué)家總結(jié)了數(shù)獨的 4 種等價變換：

⒈ 列與列的重新排列（例如上圖）

⒉ 行與行的重新排列

⒊ 數(shù)字 1 到 9 的重新排列。如把原先是 1 的位置都填上 2，然后把原先是 2 的位置都填上……直到把原先是 9 的位置都填上 1 等

⒋ 網(wǎng)格的變換。如整個數(shù)獨順時針旋轉(zhuǎn)90度，整個數(shù)獨做鏡像對稱等

在 2006 年已經(jīng)有數(shù)學(xué)家證明，排除以上幾種重復(fù)后，數(shù)獨總共有 5,475,730,538 個等價類。因為每個等價類里的任意一種情況都可以通過這個等價類中的其它情況經(jīng)由以上 4 種變換得到，所以對每個等價類來說，我們只要考慮一種情況即可。如此一來，有非常多的組合都被我們直接排除了，計算量大大減小。

讓枚舉量少一點，再少一點

雖然等價類的數(shù)量已經(jīng)降低到了可以接受的范圍，但問題還遠(yuǎn)沒有結(jié)束。因為在選擇了某個等價類中的一種情形之后，我們還需要驗證這個情形的 81 個數(shù)字中是否可以選出 16 個，使得以這 16 個數(shù)為初始數(shù)字的數(shù)獨有唯一解。

如果檢查所有的可能情況，對于每一個等價類，我們要檢查的次數(shù)就是：

這顯然很不幸：好不容易通過排除等價變換的方法把計算量減下去，怎么能在這里再加回來呢！所以這又需要數(shù)學(xué)家再做一些工作，把 3.4 × 10 ¹⁶ 這個數(shù)減小，讓枚舉量少一點，再少一點。

因此，幾位數(shù)學(xué)家利用了 “不可避免集”的概念：如下圖所示，如果表示顏色的 4 個數(shù)字中任何一個都沒有在初始數(shù)字中給出，那么這個數(shù)獨一定沒有唯一解——因為在沒有給出的情況下這 4 個數(shù)字都是由玩家填進(jìn)去的，玩家既可以以左圖的方式填入這 4 個數(shù)字，也可以以右圖的方式填入，而得到的兩個解都是合法的。具有這種屬性的數(shù)個方格就叫做不可避免集，一旦出現(xiàn)了不可避免集，我們就必須要在其中至少選出一個格子用來填寫初始數(shù)字。

不可避免集

不可避免集大大化簡計算量

在論文中，數(shù)學(xué)家們采用了 Ed Russell 總結(jié)的一套不可避免集的模板，總共記錄了 525 種不同的不可避免集。因為一開始所說的 4 種等價變換對不可避免集也適用，所以他們對不可避免集進(jìn)行了一些標(biāo)準(zhǔn)化的處理，以保證這 525 種不可避免集互相之間不能通過 4 種等價變換得到。

此時，枚舉算法就被改造成這樣：數(shù)學(xué)家給所有的不可避免集都設(shè)定一個狀態(tài)，分為“被擊中”或“未被擊中”兩種。初始時九宮格 81 個方格內(nèi)都沒有填入數(shù)字，所有不可避免集的初始狀態(tài)均為“未被擊中”。之后開始每次選擇一個最小的未被擊中的不可避免集，枚舉其中的每個格子。即每次選擇不可避免集中的一個格子填充初始數(shù)字，直至試完不可避免集中的所有空格。同時將這個不可避免集標(biāo)記為“被擊中”狀態(tài)，每次枚舉都有 4 種可能。

● 如果這個格子也出現(xiàn)在了其它不可避免集中，那么將這些被涉及到的不可避免集也標(biāo)記為“被擊中”狀態(tài)；

● 如果枚舉了 16 個格子后還有不可避免集未被擊中，說明以這 16 個格子為初始狀態(tài)的數(shù)獨一定沒有唯一解；

● 恰好枚舉了 16 個格子后所有的不可避免集全部被擊中；

● 如果枚舉了不到 16 個格子后所有不可避免集已經(jīng)全部被擊中，則從剩下的所有格子中再枚舉幾個格子使初始填充了數(shù)字的格子達(dá)到 16 個。

完成上面這個工作后，就要用解數(shù)獨的程序來驗證所有枚舉的情況是否有唯一解。為了進(jìn)一步加快枚舉速度，數(shù)學(xué)家們還加入了一些可行性剪枝和最優(yōu)化剪枝，如提前判斷“當(dāng)前情況下已經(jīng)不可能擊中所有不可避免集”并終止枚舉等。

在這一系列優(yōu)化之后，算法的復(fù)雜度終于降低到了可以接受的范圍內(nèi)。但即使這樣，整個計算過程還是耗費(fèi)了 700 萬小時的 CPU 時間。幸而這個算法最終給出了一個確定的結(jié)果：所有僅包含 16 個初始數(shù)字的數(shù)獨，都不存在唯一解！

暴力與美學(xué)的結(jié)合

當(dāng)然，上述結(jié)果的正確性還有待其他科學(xué)家進(jìn)一步驗證，因為算法耗時極高，所以驗證過程也需要花費(fèi)比較長的時間。但無論這次 3 位數(shù)學(xué)家給出的結(jié)論正確與否，隨著驗算結(jié)果的公布，這個問題終將得到一個解答。

粗略看來，這個算法的實現(xiàn)是非常暴力和機(jī)械化的：嘗試每一種可能的情況。但是在實現(xiàn)的過程中，數(shù)學(xué)家們又在借助于數(shù)學(xué)的力量，不斷地試圖減少枚舉的數(shù)量，最終將不可能的事情化為了現(xiàn)實。怪不得西澳大利亞大學(xué)的數(shù)學(xué)家 Gordon Royle 這樣評價道：“這個挑戰(zhàn)性的問題讓人們把計算的能力和數(shù)學(xué)的技巧發(fā)揮到了極限，這就像是在攀登最高聳的山峰?！?/p>

現(xiàn)在關(guān)于數(shù)獨的 puzzle 越來越難越來越精彩了。你做過的最難的數(shù)獨是什么？在這里拋一塊磚：

參考資料： There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem