春假第一天沒什麼事，來介紹一個有趣的NFT 項目 — Internet Game
Link: https://internet.game/
Twitter: https://twitter.com/internet__game
Internet Game 從字面上看就知道是一個以遊戲為主的 NFT，不過不同於多數 P2E (play to earn)的 NFT質押賺幣，這個項目是舉辦遊戲，並讓社群參與競賽，高分的拿到獎品。項目方一開始不限量的發行遊戲 token 賣多少就生多少 token，public mint 價格為 0.1 E，白名單價格為 0.05 E。目前為止總共有 8000 個 token 在市面上。
項目方利用這筆資金購買各式各樣的 NFT 作為獎品，大獎幾乎囊括了所有藍籌，並且每次購買都是在 discord 群組內投票，讓社群決定項目的獎品。
Internet Game 一年預計會舉辦四次比賽，這次比賽總共為時五天，每天一種遊戲，遊戲內容到前一天才會公布。
關卡
前兩個關卡沒什麼好介紹的，第一個遊戲是翻牌，所有的卡牌背朝上要把所有兩張一樣的卡牌翻開配對，直到配對所有卡牌。每次翻牌失敗，卡牌便會隨機旋轉並再蓋上。
第二個遊戲就蠻有意思，是一個類似賽局的遊戲。總共有 A, B, C三個選項。每個人選一個選項。遊戲最後會保留選到 『最多人選擇的選項』以及 『最少人選擇的選項』，並且淘汰所有選到『中間的選項』的人，另外選到『最多人選的選項』得到 50 分，『最少人選的選項』拿到 100 分。
遊戲的結果如下 A 共有 1483 票，B有 3253 票，C有 1411 票。有趣的是在遊戲期間 discord 有開投票給大家自由選擇，所以玩家可以觀察 discord 上面的票數作為參考，好玩的是投出來的結果與 discord 的票數接近，代表沒有很多人說謊！又或者是大家都說謊所以最後又平衡了不真實的票數 lol
第三關是這篇文章主要想分享的 — Gridswap (項目方名字取的有點爛 lol )
遊戲會給你一個 12 x 12 的矩陣方格如下，黑色的代表障礙物，遊戲目標是從原點出發將所有方格走過，每個方格只能走過一次，障礙物不能通過。
乍看之下是一個很單純的遊戲，相信很多人小時候可能也玩過，不過這在數學(物理)上或者電腦科學裡有專有名詞，叫做 Hamiltonian Path 又或是 Self-Avoiding walk。Hamiltonian path 相信學 CS 的應該都知道，就是在給定的 graph 裡面訪問所有 node 且每個 node只能訪問一次，如果有這條路徑則就是 Hamiltonian path，如果最後能走回原點則稱作 Hamiltonian cycle。而grid 圖形就是 Hamiltonian path的變形，因此這題可稱為 find a Hamiltonian path in a grid graph。
這個問題是一個 NP-complete 問題，所以可以預期並沒有一個很優秀的算法可以算出答案。我想在這邊給出我的解法，期望有其他人可以一起討論出更優秀的算法~
DFS
我使用 DFS 來找出解，基本算法就是朝任意四個方位走，遇到死路 (上下左右都是已經訪問過的方塊或者牆壁)時就會退回上一步，直到訪問完所有綠色格子。
然而眾所週知 DFS 算法最大的缺點之一就是會花費大量時間在搜索已經不可能為解的路徑上，所以通常 DFS 算法都會配上剪枝技巧。剪枝技巧的目的就是讓這個『搜索』更為聰明一點，讓已經確定不可能為解的路徑直接返回，而不再花費時間搜索後面的路徑。
剪枝 1 撞牆
當在搜索時，遇到牆壁且可以同時向左或向右走時(或向上或向下)，代表這條路徑將整個矩陣方塊一分為二，換句話說只要遇到這個狀況，後續的路徑都可以不再搜索，因為已經不可能成為一個 Hamiltonian path。參照圖片應該更好理解，下圖這樣的搜索結果很明顯看到矩陣被一分為二，因此不可能為解。
剪枝 2 撞到自己
當在搜索時，遇到已經訪問過的方塊，且此時可以向上或向下走 (或向左或向右走)時，也代表此條路徑已將整個矩陣一分為二，則不可能在後續的路徑中找出 Hamiltonian path。
陷阱 障礙物
遇到障礙物並不像遇到牆壁，不會將方塊一分為二，如下圖所示，路徑遇到障礙，並且可以同時向左或向右，但因為障礙物不會將矩陣方塊切分，所以遇到障礙物時不能直接返回。
我一開始在這個點上卡了一陣子，導致很多圖片算不出結果。
搜索圖示
最後用以上 DFS + 剪枝搜索算法，大部分的12 x 12 與 4 個 blocks的方塊都可以在數秒內搜索完畢。
以下是圖示:
謝謝閱讀！
歡迎留言討論更多優化方式～