聊一聊Puzzle:從幻方到數獨
2020年04月02日14:14

  ‘Puzzle’一詞在詞典中被定義為‘設計用於測驗聰慧程度和知識水平的玩具、遊戲或者謎題’,一般將其直接稱為‘謎題’‘智力遊戲’等。Puzzle的表現形式相當多,包含拚圖、玩具、題目等等,可謂是無奇不有。同時,基於不同規則的puzzle分別有著不同的玩法和樂趣,並且puzzle的難易度靈活多變,當謎底被解開的時刻能夠帶給解答者獨特的成就感,因此解答puzzle也算是一種相當有意思的娛樂活動,實打實的殺時間利器。

  邏輯謎題(Logic Puzzle)是puzzle中的一個大類。這類puzzle要求解答者綜合利用謎題中給出的條件進行分析、推理,進而得到謎題的答案。數獨(Sudoku)可能是這類謎題當中最為知名並且影響力最廣的了,今天的數獨已經發展成了一項風靡世界的遊戲,而這項遊戲本身,從曆史到內涵,仍然有非常多值得說的內容。

  河圖、洛書與幻方

  古代有兩種祥瑞之兆,分別被稱為‘河圖’、‘洛書’,二者綜合即為典故‘河圖洛書’。《周易》記載有‘河出圖,洛出書,聖人則之。’河圖洛書也被視作是上天降下的旨意,用以輔佐君主治國安邦。

  在河圖的傳說當中,伏羲氏在孟津縣境黃河與圖河交彙處遇見了祥獸‘龍馬’(……)。龍馬這名字來得相當簡單粗暴,其為龍與馬交配而生,明清時期的書畫家王鐸在《龍馬記》中記載:‘龍馬者,天地之精,其為形也,馬身而龍鱗,故謂之龍馬。高八尺五寸,類駱有翼,蹈水不沒,聖人在位,負圖出於孟河之中焉。’其中提到龍馬背上帶了一張圖,而伏羲氏便是看了這張圖領悟出了八卦。《尚書》中也有‘伏羲王天下,龍馬出河,遂則其文以畫八卦,謂之河圖,及典謨皆曆代傳寶之。’的說法。

  洛書的傳說與河圖很相似,相傳在大禹治水時,在洛寧縣洛河與其支流玄滬河交彙處出現了一隻神龜,其背上(也有說法是在下腹殼上)刻有一副點圖,謂之洛書。《尚書》記載‘天與禹洛出書,神龜負文而出,列於背,有數至於九。’《大戴禮記》卷八《明堂篇》有‘明堂者,古有之也。凡九室,……明堂月令,赤綴戶也,白綴牖也。二九四,七五三,六一八。’

  其中也提到了明堂這種建築按照洛書的數字‘二九四,七五三,六一八’來排列,這也是比較早的關於洛書用在建築風水上的記錄。雖然在很長一段時間里洛書河圖基本都是像這樣被用作風水占卜或者描述周易哲學,但是洛書在數學上卻有著更值得研究的內容。

  河圖

  洛書

  大話西遊2里的召喚獸,另一位大家都熟就不放圖了(逃

  首先,將洛書中的圖形改寫成3×3的九宮格,每格當中填入對應的數字,那麼這個九宮格每行每列包括兩條對角線的3個數字之和均等於15。現在人們將這種由不同數字(通常為1到階數平方的連續整數)排列而成且滿足行、列、對角線和相等的方陣稱為‘幻方’(Magic square),而行列對角線的數字和也被稱為‘幻方常數’。目前可以認為洛書是世界上最早被發現的最小幻方。順便補充一句,由幻方的定義易知2階幻方是不存在的,留給讀者證明((

  除了前文提到的行列和相等之外,幻方當中還存在非常多其他的數學性質。在這裏就僅舉一個簡單的例子:如果將洛書對應的3階幻方每行視作一個3位數,那麼這3個3位數的和與逆轉後的3位數和相等,並且對於平方和也成立,即有

  強烈建議機核加入公式編輯器

  雖然幻方的發現和記載都發生在非常早的時候,但是對於幻方進一步的數學研究要等到南宋時期了,天知道中間過的這幾千年都發生了什麼。南宋數學家楊輝(就是搞出楊輝三角的那位)是最早對幻方進行數學研究的人,他把研究成果記錄在了《續古摘奇算法》里。在書中,他將幻方稱為‘縱橫圖’,並將3階幻方的構造方法總結為‘九子斜排,上下對易,左右相更,四維挺出,戴九履一,左三右七,二四為肩,六八為足。’,意思是說把1到9按照順序斜著排成3×3的方陣,交換1和9、3和7的位置後整理便可得到3階幻方。

  同時,楊輝還給出了4階到10階的幻方,且4階到8階幻方都給出了兩種排列方法,謂之曰‘陰陽圖’。

  遺憾的是,高於4階的幻方構造方法楊輝並未給出說明,不過可以想像在當時的技術水平下這絕對是一件非常繁雜的工作。實際上,楊輝給出的10階幻方‘百子圖’便存在對角線之和不同的錯誤,而這一錯誤直到清初才被改正。張潮於《心齋雜俎》中提到了這一問題,對原10階幻方作出了修改並命名為‘更定百子圖’。

  3階幻方構造方法

  楊輝4階幻方

  更定百子圖

  除了國內,印度和中東地區也被認為是較早開始對幻方進行研究的國家和地區。在1956年,寧夏元代安西王府舊址發掘出了一塊幻方鐵板,上面刻著用真·阿拉伯文數字製作的6階阿拉伯幻方,這件文物也被認為是我國數學史上應用阿拉伯數字最早的實物資料。同時也有一種說法認為楊輝的研究是受到這個阿拉伯幻方的影響,不過該說法存在一定爭議。目前,這件文物被收藏在陝西曆史博物館內。

  現在一般認為幻方約在14世紀左右,即文藝複興時期傳入歐洲。幻方在歐洲也很快與神秘學、宗教、星座這類學說聯繫了起來。一個名為海因里希·康奈利·阿格里帕·馮·內特斯海姆(Heinrich Cornelius Agrippa von Nettesheim)的德國學者製作了3至9階的幻方,並且用土星、木星等太陽系行星的名字來給幻方分別命名;盧卡·帕西奧利(Luca Pacioli)在其作品《數字的力量》(De Viribus Quantitatis)中提到了3階和9階的幻方;更有名的例子出自版畫家丟勒在1514年的作品《憂鬱 I》,在這副版畫中有一個有趣的彩蛋:畫中人物背後的強上有一個明顯的4階幻方,同時幻方最後一行中間的兩個數字組成了作品的創作年份1514。這個作品的影響非常深遠,直到今天仍然有各類文獻對其進行解讀。

  還有一個值得一提的幻方研究者是印刷在100美元鈔票上的那位本傑明·富蘭克林,這位先生一生成就頗多,他最有名的幻方創作是一個8階幻方,並且這個幻方也被稱為‘富蘭克林幻方’(Franklin Magic Square)。據說他本人曾經表示過當他覺得無聊的時候就會琢磨幻方來解悶。遺憾的是,這個幻方存在和百子圖一樣的錯誤:兩條對角線的數字之和並不相等。有趣的是後來富蘭克林在和別人比較過幻方之後覺得自己的幻方不夠牛逼,結果楞是又搞出來一個16階的特大幻方。當然這個幻方對角線還是存在和不相等的問題,傳統藝能。

  Melencolia I, Albrecht Dürer, 1514

  幻方鐵板

  富蘭克林幻方

  除了正方形之外,幻方的形式也被拓展到了其他圖形當中,如三角形、星形、立體情況等,這些不同形式的幻方樣式被統稱為Magic polygons。楊輝在他的《續古摘奇算法》里給出了幾個基於圓形製作的‘幻圓’,並命名為攢九圖、八陣圖、連環圖等等。另一種有趣的形式是蜂窩狀的Magic hexagon,國內的文獻中有個有趣的譯名‘魔蜂窩’。

  魔蜂窩有一個別稱叫做‘38 puzzle’,這個名稱得來的原因是魔蜂窩任意直線上數字之和均為38。而正因如此,魔蜂窩的製作無比困難,有趣的是最早的魔蜂窩誕生記錄可以追溯到1887年,但是之後的幾十年中仍然有幾個人宣稱自己首先發明了魔蜂窩。據說其中一個製作者花了近50年才找到解法,中途還把解法弄丟過一次,因此等到他最終整理好時已經到1962年了。

  楊輝‘八陣圖’

  幻立方體

  魔蜂窩,‘38 puzzle’

  目前,幻方的研究方向眾多,並且也有了很多成熟的理論研究成果。幻方本身甚至也被嚐試應用到了藝術設計等領域。今天的幻方已經基本擺脫了古時候神秘學的色彩,現在人們一般僅把幻方視為數學問題來研究。由於高階幻方有著遠超於3階幻方的對稱性,並且不同種類、不同階數的幻方還有著更為複雜的性質,再加上俗話說多一個公式少一半讀者,…因此在這裏就不再多作詳細介紹了。當然,國內外關於幻方的研究文獻和科普書籍等材料也非常豐富,有興趣的各位可以去進行更深入的瞭解。

  最後再補充一點關於puzzle的內容。實際上,製作幻方本身已經是一個難度較高的謎題了,所以幻方相關的謎題往往都很相似,基本形式就是給出一個圖形並要求填上數字,使得各邊數字之和相等,或者滿足其他條件。這類謎題的區別一般只體現在幻方的各種表現形式上。下圖就是一個非常巧妙的謎題,這個圖形里需要填入1到11這十一個數字使每條直線上數字之和相等,其中有標記的幾個空是題目的突破口。這個謎題非常值得去挑戰一下!

  題目出自《趣味數學300題》

  答案

  由拉丁幻方到數獨遊戲

  在18世紀,大名鼎鼎的數學家歐拉提出過這樣一種特殊的方陣:與幻方類似,但是方陣組成的元素不是數字而是拉丁字母;並且每一個字符在每行每列中僅出現一次。這種方陣被稱為‘拉丁幻方’(Latin square)。拉丁幻方有很強的實用價值,一個典型的應用案例是將拉丁幻方利用在統計學中的試驗設計中,通過使用拉丁幻方的形式來設置安排試驗個體,可以有效提高試驗的精確性,達到減少誤差的目的。這種方法也被稱為‘拉丁方設計’。

  拉丁幻方

  很容易看出,目前的9×9形式的數獨就是非常標準的拉丁幻方。當然並不是每個9階拉丁幻方都是數獨,因為拉丁幻方本身並沒有限製自身3×3的子幻方(在數獨術語中, 這部分被稱為‘宮’)也要有不存在重複數字的要求。實際上,數獨作為拉丁幻方特殊情況,只占全體拉丁幻方中的極小一部分。全部的標準數獨組合數量在大約為6.67×10^21個,而9階拉丁幻方的全部組合一共有5.5×10^27個,對比相當懸殊。不過即便如此,數獨的不同組合情況總數也是一個天文數字,同時每一個數獨的盤面都可以對應製作成千上萬道不同的題目,因此完全不需要去擔心數獨的題庫會被刷乾淨。

  雖然歐拉搞出來了拉丁幻方,但是數獨的誕生就和他關係不大了。實際上,在19世紀末期便出現了幾個刊登在法國報紙上的謎題,但是這幾個謎題和現代數獨還有著一些細微的差別。目前認為,現代數獨的發明者是來自美國的Howard Garns,那時數獨被稱為Number Place,最早發佈在1979年的Dell Pencil Puzzles and Word Games雜誌上。雖然名字裡帶個Dell但是這個雜誌和大家熟悉的美國神舟沒什麼關係,它隸屬於Dell Publishing這家美國出版社,並且雜誌主打的是填字遊戲和紙筆謎題(pencil puzzle)這類內容。目前雜誌已經停更,不過相應的謎題集合書籍仍然在製作發售。

  接下來要說到日本。

  1980年時,一位名叫鍜治真起的印刷廠員工和幾個人合夥創辦了名為‘パズル通信ニコリ’(Nikoli謎題通信)的雜誌,這本雜誌被認為是日本最早的專注於謎題的商業雜誌。早期的Nikoli雜誌內容僅僅包括填字遊戲、蟲食算這種經典題目,而到了1984年,鍜治真起發現了Dell雜誌上的填數字謎題,覺得臥槽這玩意兒嫩牛B呢,於是立刻決定也整一個。只是他覺得不太喜歡謎題原本的名字,於是他想出了‘數字は獨身に限る’(Suuji wadokushin ni kagiru)這麼一說,大意是指‘每個數字只能出現一次’,並且取‘數’‘獨’之意,就有了現在的‘數獨’(Sudoku)這個名字。

  目前,一道恰當的數獨題目要求是可以在不進行‘試數’的情況下,能夠利用題目給出的線索全部推理出整個盤面的所有數字,並且題目僅存在唯一解。正因如此,最早的那個數獨謎題放在今天是不合格的;它只能通過一個一個數字試錯來解決。Nikoli製作的數獨還有另一個設計標準,即要求盤面對稱。雖然嚴格來說盤面對稱並非設計數獨題目的硬性要求,不過這可以視為是傳統出題人的一點匠人精神。

  19世紀末期的報紙謎題

  Nikoli數獨出版物

  再後來到了1997年,一個名為Wayne Gould的法官在東京機場時隨手買了本介紹數獨的書,結果他也感覺臥槽這玩意兒嫩牛B呢,楞是在完全不懂日語的情況下和他老婆一塊兒沉迷了進去。之後他花了6年的時間自己寫了個可以自動解決數獨問題的程序,並在大約2004年把數獨介紹給了《泰晤士報》,從此之後數獨便正式開始火爆全球,成為了現在家喻戶曉的遊戲。數獨傳入國內的具體時間已經不可考,大約是在2005年左右。而直到2007年,北京晚報智力休閑數獨俱樂部正式加入世界謎題聯合會,數獨才算是正式被引進了中國大陸,也標誌著國內的數獨發展正式走上了國際舞台。

  數獨也是目前的puzzle系列里發展得最完善的幾個項目之一。也許是因為數獨發展出了過多變種,從2006年開始,世界謎題錦標賽(World Puzzle Championship)就將數獨單獨分了出去,同時開始舉辦世界謎題錦標賽和世界數獨錦標賽(World Sudoku Championship)。大賽考察內容除標準數獨外,另外包括相當多不同規則的變體數獨。中國作為主辦國在北京舉辦了2013年的兩場錦標賽,也預計將於2020年在上海會繼續舉辦賽事。

  當時寫這段的時候完全沒想到今年這個新冠肺炎疫情的情況,不過比賽是安排在10月份,至於會不會繼續舉辦…。。。應該不會受到啥影響吧?

  ‘Lucky 7’,數度大賽變種謎題之一。要求行列宮及對角線不得有重複數字,折線上為連續數字且灰格均為偶數

  例題解答

  今天的數獨不但有了相應的組織和龐大的愛好者群體,甚至除了國際大賽之外,還發展出了相應的段位認定考試。但是如果想通過這類考試的話就務必會涉及到更多的專業知識和更高深的理論,題海戰術是免不了的;不過這部分內容不在本文的探討範圍之內,因為我自己對考證這塊兒實在不太熟悉,在這裏就不班門弄斧啦╮( ̄▽ ̄)╭

  能不能再給力一點啊,老師?

  雖說數獨遊戲規則非常清晰明了,但是題目的難易程度卻千差萬別。關於數獨盤面的提示數字數量上,有理論證明了數獨盤面內在存在唯一解的情況下,最小的提示數字是17個。要注意的是,題目的難易程度和提示數字的數量關係不大,因此偶爾會出現盤面提示數字極為稀疏,但解起來卻極為順暢;或者盤面提示數字特別多但是卻一個數都填不進去,感覺哪個數字似乎都沒起到啥提示作用的情況。前者一般只需要用到直觀的排除法,這類題目被稱為‘一刀流’數獨;而後者則是高級題目的代表,解題的技巧要求也相當之高。

  另一方面,直接把題目盤面內所有格子的候選數全部填滿再一個一個排除的暴力方法看似萬能,但是這個方法一是效率奇低,再就是面對那些難題也真不見得管用。而這類題目中的部分‘卡點’往往需要綜合各種技巧進行多步推理,才能得出目標格對應的數字。因此,掌握一定的解題技巧在求解難題時是必不可少的。

  例題1,僅有17提示數字的簡單數獨,題目來源數度無雙

  例題2,難題代表,作者Haasan

  例題1解答

  例題2解答

  最為常用且簡潔直觀的數獨解題技巧包括‘排除法’和‘唯餘法’。顧名思義,排除法即利用行列和宮內線索,用‘劃線’的方法排除掉不可能填入目標數字的格子;而唯餘法則意味著目標格‘除了這個數,別的都不能填’。‘宮排除法’較為直觀,相比下‘行列排除法’和‘唯餘法’在觀察上會更難一點,也比較容易在解題時被忽略。

  在‘宮排除法’思維下,藍色格子應填數字1

  在‘行(列)排除法’思維下,藍色格子應填數字1

  ‘唯餘法’,藍色格子只能填數字5

  讓我們更進一步,考慮如下的的情況。雖說下面這個盤面使用‘行排除法’也可以得到第三宮藍色格子填1的結果,不過如果仔細觀察第二宮,容易得知第二宮的數字1只能填在紅色的兩個格子內。即使我們並不確定究竟1要填進哪一個格子,但是不管哪種情況,這兩個格子都給第三宮作了和‘宮排除法’一樣的提示。這種情況下的將多個格子視為一個整體進行排除的方法,稱為‘區塊排除法’。

  接下來是一個技巧性更強一點的方法。容易發現,一宮內的數字1、2只能填在一宮里的兩個紅色格子裡。雖然我們也同樣不能確定1和2的具體位置,但是這兩個數字‘佔據’了這兩個格子,因此對數字5來說,通過簡單的宮排除法可以得到一宮內5只能填在藍色格子的結論。這種將多個數字確定於多個格子的方法在日文中被稱為‘予約’,中文常稱‘占位法’。

  另外介紹兩種相對比較容易理解的技巧,分別是‘X-wing’和‘唯一矩形’。實際上,需要用上這倆方法的題目基本上就屬於難題了,應用上也並不算頻繁,這裏也就簡單提一下就好。

  ‘唯一矩形’:反向利用數獨題目僅有唯一解的技巧,綠色格子如果不填8就會造成多解的情況,因此綠色格子只能填8

  ‘X-wing’,又稱‘井桁理論’,3列和7列中數字3只能填入綠格,也意味著3行和7行內紅格均不能填入3

  使用列排除法得到X-wing後的應用,八宮中數字1應當填入橙格內

  就我自己的看法來說,區塊排除和占位已經屬於在直觀易懂的情況下學習性價比最高的技巧;更高級的技巧在理解、發現和使用的上難度較高,實在沒必要一開始就在技巧上下太多功夫。並且,能夠綜合應用排除、唯餘、占位法,已經足以應付不少的題目了。不過相信你已經學會了以上的幾個簡單小技巧,那現在去試試綜合應用口巴!

  例1:區塊+宮排除得到占位

  例2:宮排除占位和唯餘占位

  例3:綜合宮列排除得到數組占位後利用區塊+列排除得到橙格填數字7

  最後要說的就是有關於數獨題庫的選擇。一般來說,好的數獨題目往往會在求解過程中暗藏著對解題人解題技巧的考察。比如說,簡單難度下的題目一般只需要用到排除法,中等難度的題目開始用到了占對和唯餘法,高級難度就需要綜合以上乃至更多的技巧了。但是數獨麻煩的地方在於不上手做根本不清楚題目設計的好壞,畢竟它們看上去都差不多。所以,選擇一些相對名氣較大的組織的作品,能很大程度上降低遇見水題的可能,減少試錯成本。

  因此,Nikoli、康思(Conceptis puzzles)這樣的老牌謎題設計廠商的產品基本上可以無腦選擇。這兩家都有自己的移動端app。康思旗下有包括‘康思數獨’在內的十幾種謎題app,採用每週限免題目加大量收費套題的形式。Nikoli旗下app名為‘Smart Nikoli’,會不定時更新免費的數獨和美術館(Akari)兩種謎題。只不過Nikoli更注重出版物那塊,這個app屬於玩票性質,用的還是觀看廣告換取代幣解鎖題目的形式,所以體驗上並不算那麼好。Nikoli的出版物這兩年也開始逐漸有了中譯本,不過他們家的書籍內容相當多,值得單開一篇文章介紹了。

  除此之外,獨·數之道、歐泊顆數獨也都是非常值得推薦的中文數獨社區,國內的出版物的話可以選擇科學出版社出版,或者由北京市數獨運動協會、數獨無雙,以及一些數獨大賽選手或者其他大佬寫的書。除了題目質量能夠保證之外,這類書籍也會涉及到更多高級技巧的講解與題目解析思路,方便提高自己的解題水平。至於一些便宜量足的書籍還是謹慎一點比較好,誰知道書裡面的內容是不是程序一鍵生成的…

  …這個看上去就不大靠譜

  雖然這個看上去更不靠譜,然而這本書內容很不錯,非常值得推薦

  一點點別的

  這篇文章最早開始寫的時候一鼓作氣寫了大半,後來忙活別的事情去了就擱在了草稿箱里,然後就這樣放了了快一年…。。。雖然中間偶爾有幾次想起要繼續寫下去,但是總感覺自己對數獨這塊兒內容瞭解得還不夠深入,想沉澱下再繼續補完。結果拖得太久連文中資料的參考文獻都整丟了,內容也還是沒深到哪裡去。。。…算了,就這樣吧。

  回憶起從正式動筆到剛剛寫完的這大段時間,真的發生了太多的事情。自己所期待的電影也好遊戲也好,都慢慢有了結果,無論是好是壞。比較有意思的就是去年年底的死亡擱淺,通關了後自己還有些恍惚,彷彿死亡擱淺仍舊是一個距離發售遙不可及的遊戲,還是得慢慢等待下去。不過我相信不管怎樣,事情總會一點點好起來的,你看擱淺都等過來了不是麼!

  而在等待以及其他無所事事的空檔期中,像是數獨這樣的puzzle真是極好的殺時間利器。雖說這東西不一定有什麼價值,不過,能夠在慵懶的午後,拿一根木杆鉛筆在紙上寫寫畫畫,真的是一件非常愜意的事情。

  來源:機核

關注我們Facebook專頁
    相關新聞
      更多瀏覽