關於部落格
  • 5731

    累積人氣

  • 0

    今日人氣

    0

    訂閱人氣

數獨樂,樂無窮

《科學人》雜誌七月號   / 撰文/Jean-Paul Delahaye 翻譯/翁秉仁


想解數獨,不但用不到數學,甚至連算術都不需要。不過,這遊戲倒是含蘊了幾個有趣的數學問題。
大家可能認為,只有很少數的人如數學家、電腦怪胎、嗜賭之徒,會對邏輯遊戲感興趣。但是,數獨在短短的時間內就變得極為流行,來勢令人想起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月號〈數獨樂,樂無窮〉】 本文章由《科學人》雜誌授權刊登,更多內容請見本期《科學人》雜誌

資料來源 摘自:全球華文行銷知識庫

資料來源 :1758網誌

相簿設定
標籤設定
相簿狀態