作者terrorlone (爱摺纸的村哥)
看板puzzle
标题[问题] 近乎不可能的西洋棋盘谜题
时间Mon Mar 17 11:16:08 2025
这个问题一般的说法是出自 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://webptt.com/cn.aspx?n=bbs/puzzle/M.1742181374.A.AC7.html
※ 编辑: terrorlone (49.216.161.71 台湾), 03/17/2025 11:23:08
1F：推 isnoneval: 推，这题能自己想出来的都是强者 03/17 23:50
2F：推 CHOIP: 有趣！刚推导 n= 2 4 8 有简单策略 但还没想出64通解 03/19 18:03
3F：→ terrorlone: 要进一步深刻思考那些比较小的解之所以可行的本质理 03/19 20:14
4F：→ terrorlone: 由所在 03/19 20:14
5F：推 CHOIP: 找到2进位排列通解了 n不是2的次方数也能套用 03/20 09:04
6F：推 CHOIP: 原理相同 解法不唯一…有空再分享我的版本及idea 03/20 09:07
7F：→ terrorlone: 咦？可是这题当 n=3 的时候应该是无解的…… 03/20 13:52
8F：推 CHOIP: n=3可解 总共只有8种可能 必能定义区分出3类型 03/20 18:15
9F：推 CHOIP: 举个简单的 只需观察前2个 00为a 01为b 10和11都代表c 03/20 18:29
10F：推 CHOIP: 抱歉…上面不够精确 03/20 18:32
11F：→ CHOIP: 010与011代表a 100与101代表b 其余为c 03/20 18:34
12F：推 CHOIP: sorry 我想错了…3真的无解…你说的才对 n要为2次方 03/20 18:40
13F：→ terrorlone: 基本上易看出：如果两个布局刚好只差两个硬币的正反 03/20 20:37
14F：→ terrorlone: ，那它们必然要属於不同的「类」。由此很容易证明，n 03/20 20:37
15F：→ terrorlone: =3 的情况怎样都至少会跑出四个类，而无法分成三类， 03/20 20:37
16F：→ terrorlone: 因此无解 03/20 20:37
17F：推 aragorn747: 第一直觉把随便一格与有钥匙那格同面的硬币翻面到有钥 03/20 21:25
18F：→ aragorn747: 匙那格，这样不就，这样不就解了？ 03/20 21:25
19F：推 DreamYeh: 我一直是3x1x数学频道的铁粉 所以你知道的...跳过XD 03/20 23:27
20F：→ DreamYeh: 另外给楼上 翻面完当然要放回同一格...否则就不是问题了 03/20 23:28
21F：→ terrorlone: 楼上没自己解一遍？话说这题我自己解完之後我粗略翻 03/21 07:08
22F：→ terrorlone: 了几篇解答文章，都觉得「怎麽写那麽长」，我自己的 03/21 07:08
23F：→ terrorlone: 解法解释起来用不到他们三分之一的篇幅就够了（而且 03/21 07:08
24F：→ terrorlone: 当然程式验证过的） 03/21 07:08
25F：推 DreamYeh: 我尝试写看看好了 03/21 08:12