中國工程師用回溯演算法,找出藏在 28 萬行唐詩裡的「對稱矩陣」

【我們為什麼挑選這篇文章】2019 年底,一個中國工程師開發了一款「文言文程式語言」(簡言之,就是用「中文字」編寫程式的語言),不只顛覆了大眾認為程式語言都用英文寫成的認知,同時也造成工程師社群轟動。不到兩年的時間,這位神人又有新作了——從 28 萬行唐詩中找出「對稱矩陣」,他怎麼做到的?(責任編輯:賴佩萱)

本文經 AI 新媒體量子位(公眾號 ID:QbitAI)授權轉載,轉載請連繫出處
作者:量子位

你能看出來,這首詩妙在哪裡嗎?

其實,橫著讀是一首詩,豎著讀還是這首詩!

而且,這首詩可不是亂編的,其中的詩句都來自《全唐詩》,讀起來也頗有意境。

創造這個奇妙組合的,不是文學研究大師,而是一位工程師小哥。

他用電腦,找出了所有符合規律的古詩,還在 Github 上開源了程式碼。

GitHub 傳送門>>https://github.com/

就連 README 文件,也頗具個性:

餘所用之程式,當以 gcc 編譯之如是
gcc -O3 mgsq5.c -o mgsq5

等一下。這個風格好像很熟悉?

沒錯,這位工程師,正是之前開發了火遍全網的文言文程式語言的 Huang Lingdong。

延伸閱讀>>>Python 弱掉了!中國工程師開發「文言文程式語言」,讓你的 coding 充滿文學情懷

文言文寫成的「Hello,World」

他用數學中的 3 階魔術方陣(九宮格)作比,把符合這種規律的詩命名為「唐詩魔術方陣」。

然而,這首詩真正的玄妙之處,還不止在這裡。

研究傳統文化的過程,發現「對稱矩陣」的奧秘

這首詩,初看只是橫豎都能讀,但如果把其中漢字寫程式成數字再看的話,會發現:

原來,這是個 對稱矩陣

不過,他遍歷了全唐詩裡所有五言詩共二十八萬七千句後,也只能得出兩個這樣的魔術方陣。

除了「風月清江夜」以外,還只有一個,不過意境上差了許多,不能令他滿意。

在 135600 行七言唐詩中,符合這個規律的七言「魔術方陣」,更是一個都沒有。

他只能退而求其次,只尋找奇數項對稱的,即每句第 1、3、5、7 個字對稱,偶數行用空行代替。

放寬標準後倒是能找出不少,但再想從其中挑選符合音韻格律、意思上還通順的,就不多了。

最後,他選擇了其中一個還稍微過得去的做例子,把空行中的字也加上,也能寫成對稱矩陣:

這位小哥,是在研究傳統文化時,從古代的洛書和璇璣圖中獲得的靈感。

洛書

洛書寫成數字就是三階幻方,特點是每一行、每一列及對角線中的數字之和都相等。

文字沒有求和這種操作,如果按照工程師思維,那就是字符串拼接起來相等。

就這樣,得出了要尋找的目標:第 n 行和第 n 列的文字相同。

璇璣圖中共 841 個字,按順讀、逆讀、橫讀、斜讀、蛇行讀、交叉讀、換行讀、換列讀、間句讀都能成詩,總共包含了 7958 首詩。

其中的關鍵之處在於, 按照不同順序讀,其文字都能組成有意義的詩句 。他自認沒有古人作詩的才華,就想到從唐詩中尋找符合條件的詩句。

而且是用現代人的方法——寫程式來解決。

怎麼做到的:暴力搜尋!

這位小哥,先是想到了用「八皇后問題」的電腦解法,來找出符合要求的唐詩。

八皇后問題,簡單來說是這樣的:

8×8 的國際象棋棋盤上,擺放 8 個不同的皇后,使其不能互相攻擊,即處在同一行、同一列、同一斜線上,求解擺放方法。

這個問題,可以用到一種名為「回溯法」的演算法來求解,原理如圖:

如果用回溯法來找「魔術方陣」,電腦需要先隨機「找出半句詩」,再挨個兒往後面搜索合適的詩句。

例如,電腦先從 13 萬行唐詩中,隨機找出詩句「風月清江夜」:

根據對稱矩陣的原理,第二句詩的開頭,就應該以「月」為首:

(以月開頭的詩句,應該還是有不少的,像月上柳梢頭)

以此類推,第三句詩的開頭,就應該以「清夜」為首:

(以清夜開頭的詩句,就少了許多)

而第四句詩的開頭,就應該以「江山歸」打頭:

最後一句詩的開頭,就必須與前 4 句詩的結尾完全一致,「夜深來客」:

難度逐漸變成地獄級……

在這幾步操作中,要是有任何一步無法滿足條件,就得全部推倒重來。

這樣的話,最初的第一步,就顯得尤為重要:從什麼類型的詩句開始遍歷,才能最快地找到答案?

他為此用上了啟發式搜索,從已知問題訊息入手,對這些空格進行評估,找到限制條件最多、即最容易「下筆」的那個位置,再從這個位置開始找詩。

具體寫成程式碼求解的話,就是利用 遞歸法 的結構。

同時,用上 剪枝法 ,縮小剩下位置的查找範圍。

也就是說,要用到 約束函數 ,在擴展節點處剪去不滿足約束條件的子樹;再用限界函數,剪去得不到最優解的子樹。

這樣一來,就能降低問題複雜度。

然而在運行程式碼時,作者卻發現,這樣做效率並不高。

這種方法,雖然可以求解「N」皇后問題,卻不太適合求漢字矩陣。

因為,要填進格子裡的,可不只 8 個皇后,每一格可以填的漢字,就有 5000+ 種選擇!

採用遞歸法的話,電腦在填上前面的漢字時,實際上就縮小了剩下漢字可以搜查的範圍。

如果沒有找到最初那個合適的字,往往搜到一半後,能用的詩句就沒了,又得重新再猜,效率不升反降。

越想越煩躁,這位小哥乾脆一拍大腿:不如暴力搜尋!

當然,也不是普通的暴力搜尋。

會有兩個搜尋條件:

其一,以五言詩為例,第五列的前 4 個字,和第五行的前 4 個字,內容是否完全一樣?如果不一樣,就扔掉。

第五行和第五列的前 4 個字

其二,這首詩是不是對稱矩陣?不是的話,就扔掉。

利用 C 語言寫好後,不用 1 小時就能跑出所有的「對稱詩」。

作者表示,自己並非文學研究的專家,也不是演算法專家,因此,這種方法可能並不是最好的辦法。

諸君若有更好的求解思路,可以來找他玩耍~

那位文言文工程師是何方神聖?

作者 Huang Lingdong,在發布文言文程式語言時還在卡耐基梅隆大學上本科。現在已畢業,在母校的 Studio for Creative Inquiry 做研究助理,為博物館和學校等組織開發互動式多媒體專案。

這位小哥熱愛寫程式和傳統文化,還開發過寫詩 IDE,能自動檢查平仄等格律規則,內置韻書和康熙字典做參考。

還能透過機器學習分析用戶作品,並與《全唐詩》中的詩句做比對,看你寫的詩像哪位詩人的風格。

除了詩詞古文,他對傳統美術也頗有研究,開發過無限生成隨機山水畫的工具,和多款中文字體。

(本文經 AI 新媒體量子位 授權轉載,並同意 TechOrange 編寫導讀與修訂標題,原文標題為 〈妙哉!那個用文言文編程的小哥,竟從 28 萬行唐詩中找出了對稱矩陣 〉。)

你可能會有興趣


參加線上講堂抽 AirPods!重磅解密 4 大雲端新技術

報名 《Cloud Innovation Summit》 觀看影片,並填寫問卷,就能參加 AirPods 抽獎! 2021 年微軟集結 K8s 聯合創辦人、 全球開源領域重量級廠商、台灣第一線雲端專家群,解析 4 大雲端主題 #開源 #數據與 AI #資安 #雲端原生 >> 立即報名

點關鍵字看更多相關文章: