數獨樂，樂無窮 |
||
|
大家可能認為，只有很少數的人如數學家、電腦怪胎、嗜賭之徒，會對邏輯遊戲感興趣。但是，數獨在短短的時間內就變得極為流行，來勢令人想起1980年代的魔術方塊風潮。 數獨與三維的魔術方塊不同，它是一個平面的方形格盤遊戲，包含了81個小格（九列九行），其中又再分 成九個小正方形（稱為宮），每宮有九小格。遊戲剛開始時，盤面上有些小格已經填了數字（稱為初盤），遊戲者要在空白的小格中填入1到9的數字，使得最後每 行、每列、每宮都不出現重複的數字，而且每一個遊戲都只有一個唯一的解答（稱為終盤）。 反諷的是，儘管數獨號稱是一種數字遊戲，卻用不到一丁點兒數學。事實上，完成這個遊戲不需要任何數學運算（譬如加法或乘法）。理論上，我們可以將數字代換成另外九種不同的符號，例如字母、顏色、圖像等。不過，數獨倒是提供數學家和電腦學家許多挑戰性的課題。 數獨的族譜 有件事倒是解答得很清楚，那就是數獨的起源。數獨的祖先並不是魔方陣（magic square，填滿整數的方陣，其中各行、各列、對角線的總和都必須一樣），這點有違一般人的認知。事實上，除了數字和方陣之外，數獨幾乎和魔方陣沒有瓜 葛，反倒是和拉丁方陣（Latin square）頗有淵源。 n階拉丁方陣是每邊n小格，總共有n2小格的方陣，方陣裡填入n種符號，在每行每列中同，一種符號不能重複出現，因此每種符號各出現n次。這個格盤遊戲的源頭，可以上溯到中世紀。後來，18世紀的大數學家歐拉研究起這個遊戲，並且稱之為拉丁方陣。 標準的數獨遊戲就像一個九階的拉丁方陣，只是多了每宮也要包括數字1到9的額外條件。這個遊戲第一次 出現於1979年5月的《戴爾的鉛筆與填字遊戲》（Dell Pencil Puzzles and Word Games）雜誌，根據《紐約時報》填字遊戲編輯薛爾茲的研究，數獨是一位退休建築師格昂斯（Howard Garns）所發明的。格昂斯1989年（或1981年，說法不一）逝世於美國印第安那波里斯，來不及看到自己的發明席捲全球。 戴爾本來稱這個遊戲為Number Place（數字的位置），1984年這個遊戲出現在一本日本雜誌後，最後被稱為Sudoku（數獨），大約是「單一數字」的意思。當這本雜誌把這個名稱 註冊為商標後，日本的仿襲者只好回頭使用Number Place的名稱。這是另一個與數獨有關的反諷：日本人稱呼這個遊戲時，用的是英文名稱，而英語世界則使用日文名稱。 數獨後續的成功必須歸功於古爾德（Wayne Gould），他是一位住在香港、喜歡四處旅行的退休法官。1997年古爾德造訪日本時，無意間發現這個遊戲，後來他就寫了一個可以自動產生數獨遊戲的程 式。2004年底，倫敦《泰晤士報》接受他的建議，刊登這個遊戲，隔年1月《每日電訊報》跟著搭上順風車。此後，全球有幾十家日報相繼刊登數獨，有些甚至 放在頭版上，做為促銷的手法。其他專門討論數獨的雜誌和專書如雨後春筍般出現在市場上，各種競賽、網站、部落格更是蜂擁而來。 和全球人口一樣多 很快的，數學家就開始跟數獨玩起「到底有多少種」的遊戲。舉例來說，他們追問到底有多少種數獨終盤的排列可能。顯然答案肯定比拉丁方陣的解來得少，因為數獨多了各宮限制的條件。 目前已知三階拉丁方陣有12組解，四階拉丁方陣有576組解，至於九階拉丁方陣的解，多達 5,524,751,496,156,892,842,531,225,600組。不過如果運用群論，可以把從一種解所衍推出的所有解都視為等價。例如， 如果有系統地把數字相互調換（好比以1換2、以2換7等），又或者如果把兩列或兩行交換，這樣得到的結果，本質上和原來的解是相同的。假設考慮這種化約的 形式，那麼九階拉丁方陣的解，就剩下377,597,570,964,258,816種，這是貝米耳（Stanley E. Bammel）與羅思坦（Jerome Rothstein）1975年發表在《離散數學期刊》（Discrete Mathematics）的研究成果，當時他們還在美國俄亥俄州立大學。 要確切知道數獨終盤的個數，是非常困難的事。今天只有利用邏輯簡化問題，並且利用電腦有系統地檢驗所 有可能性，才有可能算出所有正確數獨終盤的數目：6,670,903,752,021,072,936,960組。這是德國德勒斯登工業科技大學的費爾根 豪爾（Bertram Felgenhauer）和英格蘭雪菲爾德大學的賈維士（Frazer Jarvis）的研究結果，並且經過多次的重複驗證（以這種方式得到的結果，驗證的工作十分重要）。 但是如果把所有等價的化約形式算成一種，那麼數獨終盤的數目就縮減到5,472,730,538種，大概比地球的人口數少一點。不過儘管數字大大縮水，愛好數獨的玩家還是不用擔心沒遊戲可玩。 |
特別要注意的是，一個完整的數獨終盤，可能來自各式各樣不同的初盤。還沒有人知道到底有多少種不同的 初盤。而且，數學家真正感興趣的是，數字不能再更少的「極小初盤」。意思是說，如果從極小初盤再移走一個數字，就不可能有唯一解。目前沒有人知道有多少個 極小初盤，這個數字相當於數獨遊戲的真正總數，勢必將是數學家短期之內所要挑戰的問題。
另外還有一類「極小」的問題也還沒有解決：在保證有唯一解的條件下，一個初盤至少需要幾個數字？答案似乎是17個。西澳大學的羅艾爾（Gordon Royle）已經蒐集了38000多個滿足這個條件的例子，這些例子是已經化約過，不能靠換行或換列來相互轉換的。
愛爾蘭國立大學梅努斯校區的麥蓋爾（Gary McGuire）正在徹底搜尋著，希望可以找出16數字初盤並且有唯一解的情形，然而到目前為止還沒有什麼成果，看來似乎是沒有這種可能性。另一方面，羅 艾爾和其他人已經各自在尋找16數字初盤只有兩個解的情形，不過迄今也還沒有找到更多的例子。
有沒有人已經快要證明16數字初盤不會有唯一解呢？麥蓋爾認為還早，假設電腦每秒可以分析一組方陣， 他說：「我們就可以在173年內搜尋完畢，很不幸，我們目前還做不到這一點，即使是現在的高速電腦也不行。」他認為不久之後，電腦會進步到平均每分鐘可以 處理一組方陣，但是以這種速度，將需要10380年才能完成搜尋。「即使分散到一萬部電腦，也還需要一年的時間，」麥蓋爾補上一句：「我們實在必須在理論 上有所突破，做搜尋才比較有可能。要嘛我們得縮減搜尋的空間，不然就需要更棒的搜尋算則。」
數學家倒是知道最少初始數字相反問題的答案，也就是不能保證唯一解的初盤的最多數字，答案是77。就80、79或78個數字的初盤而言，都很容易說明這些情況保證有唯一解，但是77個數字的初盤就無法保證了。
電腦解題者
除了「有多少種」的問題外，數學家和電腦科學家也很喜歡思考，在解出或生成數獨問題時，哪些是電腦能做？哪些是電腦不能做的事？就9×9的標準數獨遊戲來說，寫一個能解出所有正確初盤的程式說不上困難。
有好幾種方法可以用來寫解題程式，其中最常用的是回溯演算法，這是一種有系統地嘗試錯誤的方法：先提供部份解答，在發現錯誤時，再回頭略做修正。
基本回溯演算法的過程大致像這樣：程式在第一個空格填入1，如果這個選擇和盤面上已有的的線索沒有矛 盾，就繼續移到下一個空格，並且填入1，如果碰到衝突（這樣做很快就會遇到衝突），程式就抹除剛剛的1，改填2，如果這還不對，就再填入3或下一個滿足規 則的數字。每當找到一個符合規則的數字，程式就往後移一個空格，重複以上的步驟，再從1開始填起。
但是一旦填到9都還不對時，依標準數獨規則不能再往下加1，於是程式就得回到上一格，把上一格本來填 入的數字再加1，然後再依照前述的步驟繼續進行，直到再度遇到衝突。有時候，程式得往回走好幾格，才能夠再繼續往下進行。只要程式寫得正確，這個方法可以 窮盡所有可能的假設，直到試出解才停止（假設真的有解的話）。如果原來的初盤有瑕疵，可能存在好幾個解時，這個程式也可以把所有的解都找出來。
當然，我們可以利用更精確的方法，加快尋找唯一解的速度。有個常用的方法稱為「約束傳播」（constraint propagation），每當填入一個新數，程式就自動產生一張表，標明每個空格中還可以填入的數字，這樣程式只要考慮表上的數字組合就可以了。
回溯演算法可以寫成很短的解題程式。事實上，現在已經有以Prolog程式語言寫成的簡單數獨程式， 這是一種內附回溯演算法的程式語言。Prolog是法國馬賽大學的科莫勞厄（Alain Colmerauer）和魯賽爾（Philippe Rousell）在1970年代末期所發明的。
不過就人類玩家而言，想要運用電腦程式所使用的回溯演算法，相當困難，需要極端強韌的耐性。因此普通 人所使用的是更多變、更聰明的解題法則，只有到了山窮水盡的地步，才會考慮「嘗試錯誤」的方法。有些程式相當程度地模仿了這種方法，這種程式寫起來比較 長，但效果一樣好。這些模仿人類推理的程式，可以幫忙標示遊戲的困難度，十分有用。遊戲的困難度從「簡單級」（只需要簡單戰術）一直到「魔鬼級」或「殘酷 級」（需要用到更多消耗腦力的邏輯規則）都有。
【意猶未盡嗎？欲閱讀完整全文，請參閱科學人2006年7月號〈數獨樂，樂無窮〉】【挑戰題解答】
尤怪的家
數獨之出題方法
3D數獨(1)
3D數獨(2)
魔術方塊(1)
魔術方塊(2)
魔術方塊(3)
方塊試玩
留言列表