不知道各位看倌們會不會玩西洋棋,其實 Jason 小時候非常瘋棋類遊戲,象棋、西洋棋、圍棋、五子棋... 都會玩,國小的時候都還有跑去參加鄉鎮公所辦的比賽,然後贏一些鍋碗瓢盆啥的回家 xD 不過後來再長大一點點,可能小六還是國一吧,在人生第一次接觸 Computer、Online Game 之後,誰還跟你下啥棋啊 哈哈哈 簡單介紹一下,西洋棋可說跟中國的象棋非常相似,都是一種模擬古代行軍打仗的回合制遊戲,雙方各自可以控制一些功能不同的棋子在棋盤中移動 e.g. 統帥、士兵、騎士等等,遊戲的 Endgame 就是將對方的統帥給擊殺。 而在西洋棋中有一顆特別強大的棋子 - 皇后,她可以在棋盤中向任意的線性方向移動,見下圖:
然後在十八世紀有一個德國的西洋棋手 Max Bezzel,提出了一個有趣的問題:
如果在一個八乘八的棋盤上擺上八個皇后,並希望她們彼此能相安無事 ( 即任兩皇后都不能處於同一橫行、縱行或者斜線上 ),那會有多少種擺法呢? 韋小寶也才七個老婆,他一個人卻想坐擁八個皇后,還把問題丟出來給別人解,也是一個精銳 >"< 後來陸續有一些數學加投入研究這個問題,像我們的高斯大神也有研究過這個問題,並且他猜測這個問題應該有96個解,不過後來證實其實只有92個,如果再合併掉那些用旋轉跟對稱可以得到的解的話,那只有12個獨立解。
後來這個問題也被推廣成 N皇后問題,即在 N * N 的棋盤上擺 N 個皇后有幾種解,不過截至今日為止,目前仍沒有任何已知公式可以用來計算 N 皇后問題的解的個數。
好的,那在了解八皇后問題後,另一個問題是:那又為什麼資工人一定要寫程式來解八皇后? 其實八皇后問題就像 Jason 在上一篇 【演算法】資工人必爬的一座塔 - 河內塔 Tower of Hanoi 裡面提到的河內塔問題一樣,它們都是資工人在學習「程式設計」、「演算法」、「資料結構」的經典問題。 像河內塔問題就是遞回法的經典應用;而八皇后問題則是回溯法的經典應用。 【回溯演算法 Backtracking Algorithm】
回溯演算法其實就是一個類似窮舉搜索的嘗試過程,主要就是在整個解空間中去窮舉搜索問題的解,一旦發現搜尋的方向已不滿足求解條件的時後,它就會回溯改去嘗試其他的路。回溯法是一種選優搜尋演算法,按照選優的條件往前搜尋,以達目標。基本上就是它在搜尋的過程中,發現原先的選擇並不優,或者違背我們當初設定的條件,他就會退一步,然後重新選擇。
像這種往前走然後發現路走不通,一言不合就往回退,再重新來過的方法就叫回溯法。 其實比起八皇后問題,我更喜歡 "老鼠走迷宮" ,我覺得它可以更好、更直觀的理解回溯法。 不過這東西可能就等下次有空再寫吧xD
最後附上 Eight Queen 用 C 語言的實現:
Code Editor
0 評論
發表回覆。 |
Jason Chen人不光是生來就擁有一切,而是靠他從學習中得到的一切來造就自己。- 歌德 文章分類
全部
封存檔
九月 2023
|