close
 

數獨背後的四個數學問題

轉自http://bbs.mathbar.com/TopicOther.asp?t=5&BoardID=54&id=14798

數獨(Sudoku),一種起源於日本、流行於歐美的數字游戲,雖然進入中國內地的時間不久,但已經占據了很多媒體的游戲版面,吸引越來越多的玩家投身數字的迷宮。不過數獨愛好者們可能不知道,這個小游戲的雛形,卻是一個讓數學家傷透腦筋的問題。即使在今天,還有眾多研究人員為弄清楚數獨背後的規律而絞盡腦汁。

  即使是天使也會為數學問題苦思冥想。德國名畫家丟勒的這幅木刻畫《憂郁症》(Melencolia)描述的就是一個因為數學患上憂郁症的天使。


  讓畫中天使牽掛的就是牆上掛著的數字迷宮,橫向、縱向、對角線數字的和都是34,在最下面一行的中間兩格,畫家自娛地留下了創作年代1514.

  1 歐拉與拉丁方

  作為數學史上最傳奇、最多產的大師之一,瑞士數學家歐拉(LeonardEuler,1707—1783)在18世紀研究了一種有趣的數字方陣:考慮一個階數(亦即行數和列數)為n的方陣,在小格裡填入n種符號或數字,在每一行/列中,每一個符號出現且僅出現一次。這種方陣源自中世紀的格盤游戲,其求解過程可歸結為“染色問題”———一個數學中最古老的問題之一。因為最初隨手填入方陣內的是一個個拉丁字母,歐拉將這樣的方陣命名為拉丁方(Latin Square)。拉丁方在實驗設計、數據檢驗和幻方構造等領域應用極廣。

  很容易發現,數獨其實正是一種特殊的拉丁方。惟一不同的是,數獨加上了兩個額外的條件:一、在每個小九宮格的區域內,每個數字同樣出現且只出現一次;二、給出的初始數字必須對稱。

  2 終盤的可能性

  通常將一個完成了的數獨題目稱為終盤。在數獨游戲風行後,人們很快便希望知道這個游戲究竟存在多少個終盤形式。對此,德國數學家BertramFelgenhauer在2005年給出了答案:數獨的最大可能終盤數為6,670,903,752,021,072,936,960種。

  Felgenhauer的算式為9!×722×27×27,704,267,971,最後的數字是一個大質數。雖然這個天文數字已經足夠驚人,但考慮到作為一種特殊限制的拉丁方,數獨終盤的可能性只是可能存在的九階拉丁方數目的0.00012%!

  另一個方面,考慮到數獨游戲的初始數字對稱要求,以上結果可能有相當程度的重復,亦即其終盤結果會出現大量的雷同。據此,英國數學家FrazerJarvis和EdRussell給出了更准確的不同終盤數:5,472,730,538.這樣一來,有志於破解所有數獨題目的玩家又看到了希望的曙光,擔心游戲被窮盡而沒有游戲可玩的愛好者也不必焦慮:畢竟這個數目和地球人口一樣多。

  3 最小初盤問題

  與終盤相對應,一個數獨游戲給出的初始條件稱為初盤。由於規則所限,給出的初盤數字個數必須在32以下。

  一般常見的初盤數字個數在22—28之間,而數獨愛好者們常問的一個問題是:最少給出多少個數字,數獨游戲才確保有惟一解?具體地說:最少需要在初盤中給出多少個數字,使得移除其中任何一個數字該數獨游戲便沒有惟一解。

  事實上,這個問題是數獨中最有數學趣味的問題之一,並且至今仍未得到解決。但數學家們估計,這個數字很可能是17.17個數字的最小惟一解初盤是由一名日本數獨愛好者發現的。澳大利亞數學家GordonRoyle已經收集了36628個17個數字的惟一解初盤,而愛爾蘭數學家Gary McGuire則致力於尋找16個數字的惟一解初盤,但至今仍無發現。部分數學家開始退而求其次,轉而尋找只有兩個解的16個數字初盤。

  統計學家根據一個統計學原理曾隨機地構造了大量17個數字的初盤,發現其中有惟一解的初盤只有數個未被GordonRoyle教授發現,這意味著,最小惟一解初盤問題的最終答案可能正是17:因為從理論上說,如果16個數字的惟一解終盤存在,那麼每一個必將引起65個17個數字惟一解終盤的增加,而在研究中至今沒有觀察到這一效應。

  4 最大初盤問題

  與最小初盤問題相反,人們還可以提出最大初盤問題。

  也就是說:在一個數獨初盤中,最多能給出多少個數字,使得再增加一個數字該問題便只有惟一解。

  相對於最小初盤問題,最大初盤問題容易解決得多。采用倒推法,在初始數字為80的情況下無需說明,缺啥補啥即可;在初始數字為79的初盤中也大約如此,因為考慮到必須滿足每一個小九宮格內每個數字出現且僅出現一次,這意味著所缺少的數字都必須出現在同一個九宮格內,考慮到這個情況,還可以依次推出78的初盤也有惟一解。但當初盤中給定數字變為77的時候,該數獨游戲便會出現至少兩解。

  數字游戲

  “數獨”可以被定義為一種邏輯智力拼圖游戲,也可以被稱為“數字游戲”。顧名思義,“數獨”可以理解為一組獨立的數字,將這組數字以一定的規則組合在一定區域內,便是數獨游戲的主要內容。

  具體地說,拼圖是大九宮格(即3格寬×3格高)的正方形狀,由9個小九宮格組成。游戲的目標是在每一個小九宮格中,不重復地填上1至9的數字,讓整個大九宮格每一列、每一行的數字都不重復。一般而言,一條數獨題會給出1/3左右的數字作為初始條件,剩下的2/3空白處由讀者完成。

  也許正是因為規則簡單,所以數獨才能迅速風靡世界。既然玩數獨游戲無需數學運算或證明,似乎完全可以將其稱為“數字游戲”。

  傳播史

  Nikoli是所有數獨愛好者需要感謝的第一個名字。

  數獨游戲在1979年前後已經在美國Dell雜志上刊登,但在眾多填字游戲中並未引起特別注意。直到1984年,日本的填字游戲出版商Nikoli公司的煆治真起從美國發現了這個游戲,決定引入日本並將其命名為Sudoku,意思是“每個數字只能出現一次”。

  隨著Sudoku游戲在日本國內大受歡迎,Nikoli公司在1986年對其進行了兩項改良:其一是題目中給出的初始數字限定在32個以內,其二是給出數字的分布采用對稱形式。這就是今天我們看到的數獨游戲的面貌。

  很難解釋為何在此後的十多年裡,數獨游戲一直只在日本國內流行。但可以肯定的是,將數獨游戲重新發現並推廣到國際市場的,是一名香港高等法院退休法官、新西蘭人高樂德。他在1997年一次日本旅行中,在書店內發現數獨游戲,立刻被其吸引住。此後高樂德花了六年時間開發數獨出題程序,並向英國《泰晤士報》等報社出售其編寫的數獨題目。英國市場反應極佳,數獨開始風行全球,而高樂德本人也因此獲得巨額收入。

  經過兩年的迅速發展,數獨游戲已經“侵入”了幾乎一切公共傳播領域:數以千計的報紙提供數獨游戲,數十種數獨刊物,全球各地分別成立了數獨愛好者團體,電視上已經出現了數獨節目,而第一屆數獨世界錦標賽也在今年的3月舉行,捷克一名女會計師奪冠。

 

arrow
arrow
    全站熱搜
    創作者介紹
    創作者 等會見 的頭像
    等會見

    等會見的部落格

    等會見 發表在 痞客邦 留言(0) 人氣()