趨勢報報 ........

關於部落格
就是想追索下一步!
  • 65481

    累積人氣

  • 1

    今日人氣

    0

    訂閱人氣

數獨樂

數獨的前身:數獨的數盤是一種特殊的拉丁方陣。拉丁方陣的名稱出自於18世紀的數學家歐拉,是一種含有n種符號的n × n方陣,其中每列或每行的n種符號都不可重複出現(例如上圖左)上圖右則是一個完成的標準數獨盤面(也稱作終盤),符合9 × 9拉丁方陣,所增加的額外限制條件是必須滿足每一宮中,1到9的數不能重複出現。

數獨與三維的魔術方塊不同,它是一個平面的方形格盤遊戲,包含了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種,大概比地球的人口數少一點。不過儘管數字大大縮水,愛好數獨的玩家還是不用擔心沒遊戲可玩。

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