專題報告-(數領域)-數獨

專題領域：數學

引言：
數獨在短短的時間內就變得極為流行，來是令人想起1980年帶的魔術方塊風潮。

遊戲方式：
數獨與三維的魔術方塊不同，他是一個平面的方形格盤遊戲，包含了81個小格(九列九行)，其中又再分成九個小正方形(稱為宮)，每宮中有九小格。遊戲剛開始時，盤面上有些小格已經填了數字(稱為初盤)，遊戲者要在空白的小格中填入1到9的數字，使得最後每行、每列、美工都不出現重複的數字，而且每一個遊戲都只有一個唯一的解答(稱為終盤)。

特色：
反諷的是，儘管數獨號稱是一種數字遊戲，卻用不到一丁點兒數學。事實上，完成這個遊戲不需要任何數學運算(譬如加法或乘法)。理論上，我們可以將數字代換成另外九種不同的符號，例如字母、顏色、圖像等。不過，數獨到是提供數學家和電腦學家許多挑戰性的課題。

(數獨的族譜)
起源：

數獨的祖先並不是魔方陣(magic spuare，填滿整數的方陣，其中各行、各列、對角線的總和都必須相同)，這點有違一般人的認知。事實上，除了數字和方陣之外，數獨幾乎和魔方陣沒有瓜葛，反倒是和拉丁方陣(Latin square)頗有淵源。這個格盤遊戲的源頭，可以上溯倒中世紀。後來，18世紀的大數學家歐拉研究起這個遊戲，並且稱之為拉丁方陣。
拉丁方陣是一種含有n種符號的n*n方陣，其中每列或每行的n種符號都不可重複出現(如圖)。另一圖則是一個完成的標準數獨盤面(也稱為終盤)，符合9*9拉丁方陣，所增加的額外限制條件是必須滿足每一宮中，1倒9的數不能重複出現。

發明：
這個遊戲第一次出現於1979年5月的《戴爾的鉛筆與填字遊戲》(Dell Pencil Puzzles and Word Games)雜誌，根據《紐約時報》填字遊戲編輯薛爾茲的研究，數獨是一位退休建築師格昂斯(Howard Garns)所發明的。格昂斯1989年(或1981年，說法不一)逝世於美國印第安那波里斯，來不及看到自己的發明席捲全球。

新面貌：
戴爾本來稱這個遊戲為Number Place (數字的位置)，1984年這個遊戲出現在一本日本雜誌後，最後被稱為Sudoku(數獨)，大約是「單一數字」的意思。

席捲全球：
數獨後續的成功必須歸功於古爾德(Wayne Gould)，他是一位住在香港、喜歡出去旅行的退休法官。1997年古爾德造訪日本時，無意間發現這個遊戲，後來他就寫了一個可以自動產生數獨遊戲的程式。2004年底，倫敦《泰晤士報》接受他的建議，刊登這個遊戲，隔年1月《每日電訊報》跟著搭上順風車。此後，全球有幾十家日報相繼刊登數獨，有些甚至放在頭版上，作為促銷的手法。其他專門討論數獨的雜誌和專書如雨後春筍般出現在市場上，各種競賽、網站、部落格更是蜂擁而來。

(相關探索)
終盤的排列變化：
很快的，數學家就開始跟數獨玩起「到底有多少種」的遊戲。舉歷來說，他們追問到底有多少種數獨終盤的排列可能。顯然答案肯定比拉丁方針的姊來得少，因為數獨多了各宮限制的條件。
要確切知道數獨終盤的個數，是非常困難的事。如果把所有等價的化約形式算成一種，那麼數獨終盤的數目為5,472,730,538種，大概比地球的人口數少一點。愛好數獨的玩家完全不用擔心沒遊戲可玩。
特別要注意的是，一個完整的數獨終盤，可能來自各式各樣不同的出盤。還沒有人知道到底有多少種不同的初盤。而且，數學家真正感興趣的是，數字不能在更少的「極小初盤」。意思是說，如果從極小初盤再移走一個數字，就不可能有唯一解。目前沒有人知道有多少個極小初盤，這個數字相當於數獨遊戲的真正總數，勢必將是數學家短期之內要挑戰的問題。

挑戰初盤極限(極小)：
另外還有一類「極小」的問題也還沒有解決：在保證有唯一解的條件下，一個初盤至少需要幾個數字？答案似乎是17個。西澳大學的羅艾爾(Gordon Royle)已經蒐集了38000多個滿足這個條件的例子，這些例子是已經畫約過，不能靠換行或換列來互轉換的。
愛爾蘭國立大學梅努斯校區的麥蓋爾(Gary McGuire)正在徹底搜尋著，希望可以找出16數字初盤並且有唯一解的情形，然而到目前為止還沒有什麼效果，看來似乎是沒有這種可能性。另一方面，羅艾爾和其他人已經各自在尋找16數字初盤只有兩個解的情形，不過迄今也還沒有找到更多的例子。

挑戰初盤極限(極大)：
數學家倒是知道最少初始數字相反問題的答案，也就是不能保證唯一解的初盤的最多數字，答案是77。就80、79或78個數字的初盤而言，都很容易說明這些情況保證有唯一解，但是77個數字的初盤就無法保證了。
例圖中只有四個空格，卻有兩個解；第一行和第二行中的空格，1、2的填法可以互換。

出題&解題：
數學家思考在解出或生成數獨問題時，哪些是電腦能做、哪些是電腦不能做的事？就9*9的標準數獨遊戲來說，寫一個能解出所有正確初盤的程式說不上困難。
有好幾種方法可以用來寫解題程式，其中最常用的是回溯演算法。這是一種有系統地嘗試錯誤的方法：先提供部分解答，在發現錯誤時，再回頭絡作修正。這個方法可以窮盡所有可能的假設，直到試出解才停止。如果原來的初盤有瑕疵，可能存在好幾個解時，這個程式也可以把所有的解都找出來。
當然，還有更精確的方法可用，加快尋找唯一解的速度。有個常用的方法稱為「約束傳播」(constraint propagation)，每當填入一個新數，程式就自動產生一張表，標明每個空格中還可以填入的數字，這樣程式只要考慮表上的數字組合就可以了。

不單是遊戲：
電腦科學家思考數獨的一個角度，是把數獨等同於一類將圖著色的問題，這種圖有81個頂點，其中有些頂點在一開始就已經著好顏色，規則是相鄰的頂點(共用一邊的頂點)不准同色，而且色盤上只有九種顏色。這個著色問題非常複雜，因為9*9的格盤所對應的圖有幾百條邊。和某個頂點同一列的小格相當於其他八個頂點，同一行的小格又對應另外八個頂點，而同一宮的又還有四個不同的頂點(另外四個頂點在行列中已經算過了)。
把數獨遊戲轉換成一個著色問題，對科學家意義重大，因為這個性質讓數獨和一類重要的問題產生了關連。事實上日本東京大學的八登崇之與瀨田剛廣最近剛證明出數獨是一個NP完備問題，這類問題指的事無法在實際可行的時間內解出來的問題，知名的NP問題例子包刮三色問題，這個問題是要判斷能否以三種顏色為一個圖的頂點著色，而且其中相鄰共邊的頂點不得同色。

人腦攻略：
喜歡親自解決數獨遊戲的數獨迷，有許多攻略戰術可以選擇。想學習的人，可以從兩個基本的技巧開始。第一個方法是從提供填件最多的空格出發，例如找已經有足夠數字的列、行、宮中的空格，這時只要刪去不可能出現在該格的數(例如已經出現在該列、行、宮的數字)，有時候唯一可能的數就會浮現。通常，這個方法可以大大縮減選擇的範圍。
第二種方法則是，在特定的列、行、宮中搜尋某數可能出現的位置，有時候會發現該術可能出現的二或三個位置，最後也會有所幫助。
在網路上也很容易找到一些程式，可以輸出特定困難度的數獨問題，並且還會引導你找到解答(不過當然不會直接給出答案)。例如某些程式可以讓你在小格中加上或刪除暫時的標記，因此就不再需要使用鉛筆和橡皮擦，另外還有一些程式可以在小格之間建立連結。千萬不要小看這些程式，由於不需要處理擦拭這類冗贅的瑣事，這些功能可以幫助你在破解這個邏輯遊戲時，進入更精妙入神的大師境界。


資料來源：科學人雜誌Scientific American中文版 NO.53-2006年7月號
經站主整理!重新發表!