PTT遊戲區 / puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)

[問題] 近乎不可能的西洋棋盤謎題

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者 (愛摺紙的村哥)時間1月前 (2025/03/17 11:16), 1月前編輯推噓11(11推 0噓 14→)
留言25則, 5人參與, 1月前最新討論串1/1
這個問題一般的說法是出自 2020 年的一個 YouTube 影片， 也已經有幾年的歷史了，不過最近在臉書上又有一些相關的討論， 爬了一下似乎沒有人貼在這邊過，就順手貼一下。 題目： 獄長給兩個囚犯出了一個謎題。 兩個囚犯將會依序進入一個房間， 房間裡面有一個西洋棋盤（註：其方向是確定的，例如可以想像棋盤旁邊有寫座標）， 棋盤的 64 個格子每個底下都是一個小收納空間， 其中恰有一個格子裡面藏了出獄的鑰匙， 而每一個格子上面都各放了一個硬幣，每個硬幣均可能是正面或反面。 第一個囚犯進入到房間之後，獄長會打開正確的格子讓他看鑰匙藏在哪一格裡面。 接下來，他唯一能做的事情就是把棋盤上其中一個格子的硬幣翻面 （且一定要翻一個），然後就必須離開房間、沒有機會傳遞其它訊息。 接著第二個囚犯進入到房間之後，他必須根據棋盤上的硬幣狀態來判斷出鑰匙藏在哪裡。 棋盤上的硬幣初始狀態會怎麼擺、以及鑰匙會藏在哪裡，都是無法事先知道的。 兩個囚犯之間的訊息傳遞，也僅限於第一個囚犯的翻面操作 （當然，第二個囚犯沒有任何方法知道第一個囚犯翻的是哪一個， 他只能看到翻面之後的全體狀態）。 不過兩個囚犯事前都完整地知道遊戲規則，他們可以盡情擬定策略。 難度（純屬個人見解）：★★★★☆ ======================================== 這個題目取名叫「近乎不可能的西洋棋盤謎題」、 就是因為兩個囚犯之間只能透過看似極少的操作、 來在龐大的解空間（64 * 2^64）裡面傳遞訊息。 但因為不是完全不可能，這謎題確實是有解的。 這幾年來在網路上解答這題的文章和影片一大堆， 但當然鼓勵各位自己解一遍。 這題我從看到題目開始在每天晚上邊想邊入睡，想了大概十天左右全部想出來。 要驗證各位的策略有效，一個簡單的方法就是寫程式來模擬整個過程， 如果編碼函數（第一個囚犯）和解碼函數（第二個囚犯）總是能正確合作， 那就對了～ 一個不算提示的提示：不妨先考慮棋盤很小很小的情況，再試著推廣到 64 格。 順便一提： 這個謎題的可行策略當然不只一種，但可以證明， 所有的可行策略本質上都是等價的（只差在格子的排列與正反面的定義而已）。 -- ▄ \ Terrorlone 西洋棋謎題專欄 為您獻上優質的精選謎題 ▄ ▄▄ \ ▄ ▄▄ \ 難度星級：1=3分鐘, 2=20分鐘, 3=2小時, 4=1天, 5=1週 ▄ \ 推文請小心不要洩漏關鍵字，答對者敬請簽到 XD ▄ ▄ \ 若覺得題意不清請盡量來信或水球詢問，不要用推的。 ▄ \ 剛入門者可先閱讀 #19x4xedc、#19y39PSk、#1A1TgpvR ▄ \ 等等幾篇文章。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.161.71 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/puzzle/M.1742181374.A.AC7.html ※ 編輯: terrorlone (49.216.161.71 臺灣), 03/17/2025 11:23:08
推
03/17 23:50, 1月前 , 1F
推，這題能自己想出來的都是強者
03/17 23:50, 1F
推
03/19 18:03, 1月前 , 2F
有趣！剛推導 n= 2 4 8 有簡單策略 但還沒想出64通解
03/19 18:03, 2F
→
03/19 20:14, 1月前 , 3F
要進一步深刻思考那些比較小的解之所以可行的本質理
03/19 20:14, 3F
→
03/19 20:14, 1月前 , 4F
由所在
03/19 20:14, 4F
推
03/20 09:04, 1月前 , 5F
找到2進位排列通解了 n不是2的次方數也能套用
03/20 09:04, 5F
推
03/20 09:07, 1月前 , 6F
原理相同 解法不唯一…有空再分享我的版本及idea
03/20 09:07, 6F
→
03/20 13:52, 1月前 , 7F
咦？可是這題當 n=3 的時候應該是無解的……
03/20 13:52, 7F
推
03/20 18:15, 1月前 , 8F
n=3可解 總共只有8種可能 必能定義區分出3類型
03/20 18:15, 8F
推
03/20 18:29, 1月前 , 9F
舉個簡單的 只需觀察前2個 00為a 01為b 10和11都代表c
03/20 18:29, 9F
推
03/20 18:32, 1月前 , 10F
抱歉…上面不夠精確
03/20 18:32, 10F
→
03/20 18:34, 1月前 , 11F
010與011代表a 100與101代表b 其餘為c
03/20 18:34, 11F
推
03/20 18:40, 1月前 , 12F
sorry 我想錯了…3真的無解…你說的才對 n要為2次方
03/20 18:40, 12F
→
03/20 20:37, 1月前 , 13F
基本上易看出：如果兩個佈局剛好只差兩個硬幣的正反
03/20 20:37, 13F
→
03/20 20:37, 1月前 , 14F
，那它們必然要屬於不同的「類」。由此很容易證明，n
03/20 20:37, 14F
→
03/20 20:37, 1月前 , 15F
=3 的情況怎樣都至少會跑出四個類，而無法分成三類，
03/20 20:37, 15F
→
03/20 20:37, 1月前 , 16F
因此無解
03/20 20:37, 16F
推
03/20 21:25, 1月前 , 17F
第一直覺把隨便一格與有鑰匙那格同面的硬幣翻面到有鑰
03/20 21:25, 17F
→
03/20 21:25, 1月前 , 18F
匙那格，這樣不就，這樣不就解了？
03/20 21:25, 18F
推
03/20 23:27, 1月前 , 19F
我一直是3x1x數學頻道的鐵粉 所以你知道的...跳過XD
03/20 23:27, 19F
→
03/20 23:28, 1月前 , 20F
另外給樓上 翻面完當然要放回同一格...否則就不是問題了
03/20 23:28, 20F
→
03/21 07:08, 1月前 , 21F
樓上沒自己解一遍？話說這題我自己解完之後我粗略翻
03/21 07:08, 21F
→
03/21 07:08, 1月前 , 22F
了幾篇解答文章，都覺得「怎麼寫那麼長」，我自己的
03/21 07:08, 22F
→
03/21 07:08, 1月前 , 23F
解法解釋起來用不到他們三分之一的篇幅就夠了（而且
03/21 07:08, 23F
→
03/21 07:08, 1月前 , 24F
當然程式驗證過的）
03/21 07:08, 24F
推
03/21 08:12, 1月前 , 25F
我嘗試寫看看好了
03/21 08:12, 25F
‣ 更多 terrorlone 的文章
文章代碼(AID): #1drvF-h7 (puzzle)
puzzle 近期熱門文章
更多 近期熱門文章 >>
PTT遊戲區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 terrorlone 的文章
文章代碼(AID): #1drvF-h7 (puzzle)