15数字推盘（1880） — 萨姆·劳埃德骗倒世界的那一步无解棋局

序言

1880年的冬天，整个美国被一个手掌大的小盒子所迷住。方形框架内排列着1到15的号码牌，借助唯一的空格滑动牌片，将乱序的数字重新排列整齐。就是这样一件玩具，无论在酒吧、办公室还是火车上，都让人们的手指停不下来，报纸也写道「这股热病正在麻痹工作」。这就是后来被称为「15数字推盘」的滑块游戏的第一次全球性流行。

The goal state. Tiles run 1 to 15 in order, with the blank settled in the bottom-right. In 1880 the whole world was gripped by this simple act of rearrangement.

但我这次想要挖掘的，与其说是流行本身，不如说是世间长久以来记忆为这个盒子「发明者」的人物真相。他的名字是萨姆·劳埃德（Samuel Loyd, 1841-1911）。身为美国首屈一指的谜题作家兼前象棋棋手，他声称自己正是掀起这股狂潮的幕后推手，并悬赏千美元征解。然而，他的主张中混入了决定性的谎言。

本文将追溯1880年狂潮的真实来源，挖掘劳埃德以悬赏为名的那块盘面早在他自称发明的1879年便已被证明「数学上永远无法到达」的事实。并从历史角度重读这个古老木盒留给现代数字谜题的问题：「如何保证谜题可解」。

时代背景

滑块机制本身，据认为是1874年前后由纽约州卡纳斯托塔的邮政局长诺伊斯·帕尔默·查普曼（Noyes Palmer Chapman）发明的。此后数年间口耳相传，作为商品量产后，1880年1月在美国引发了爆炸性的流行。浪潮于同年4月传至欧洲，随后在7月前后骤然退去。这场狂潮只是短短半年的短暂热病。

萨姆·劳埃德开始宣称这个谜题是「自己的发明」，是在流行已经消退很久之后的事。他发表第一篇关于15数字推盘的文章是在1896年，距狂潮最高潮已过去整整十六年。他与实际流行期间毫无关联的痕迹。尽管如此，劳埃德在生命中漫长的岁月里反复主张自己的发明权。

这一冒充行为被彻底揭穿，是近年的事。谜题史学家杰里·斯洛卡姆（Jerry Slocum）与迪克·松内费尔特（Dic Sonneveld）在2006年的著作《The 15 Puzzle》中，对照当时的第一手资料，细致地证明了劳埃德的主张不过是延续了一百一十五年的虚构。发明的荣誉，本应归于那位无名的邮政局长。

规则

规则极为简单。4×4的框架内有15枚牌与一个空格，只能将紧邻空格的牌滑入。目标是将数字从1到15按顺序排列，并将空格归位到指定角落。步数没有上限，人人都能上手。正是这种朴素，成就了1880年人们为之着迷的魅力。

The board Loyd offered as his prize. Tiles 1–13 sit in order, with only the 14 and 15 swapped (dashed). The goal is to sequence them from the top-left and send the blank to the bottom-right — yet this arrangement has reversed parity and can never be reached, however you slide.

然而，这个游戏有一道隐形的墙。美国数学家威廉·约翰逊（William Woolsey Johnson）与威廉·斯托里（William E. Story）于1879年在《美国数学杂志》发表「关于15数字推盘的备忘录」，以置换奇偶性论证，证明了初始配置中有一半无论经过多少步都绝对无法复原。换言之，某块盘面是否可解，并非取决于运气或毅力，而是从最初就由数学决定了。

劳埃德以千美元为注的盘面，正属于这「无解的一半」。他出的题目，是14与15对调的、几乎完成的配置。看似只差一步，却因奇偶性相反而永远无法到达答案。悬赏金是安全的。他将数学上的不可能性以「看似可解的难题」形式出售，让众人竞相做无用之功。这不是发明，而是对不可能性的一场演出。

现代的传承

约翰逊与斯托里开创的「用数学解读盘面状态空间」的视角，直接延伸至其后的计算机科学。1990年，丹尼尔·拉特纳（Daniel Ratner）与曼弗雷德·沃尔穆斯（Manfred Warmuth）证明了将15数字推盘推广到n×n的问题中「求最短步数是NP难的」（首次发表于1986年的AAAI）。棋盘越大，最优解搜索在计算量上便越难以驾驭。1879年的奇偶性问题，与现代的难度理论一脉相承。

Generalize the board to n×n and finding a shortest solution becomes computationally intractable (NP-hard). The parity question of 1879 runs continuous with the modern theory of 'hardness.'

这一传承，如今静静却沉重地压在所有以数字方式处理滑块的创作者身上。实现随机打乱出题的拼图游戏的人，必须面对约翰逊-斯托里定理——若随意散乱牌片，有一半概率会将「绝对无法解开的盘面」摆在玩家面前。因此，现代滑块拼图生成器在内部检验奇偶性，只分发可解的盘面。1879年的证明至今仍作为实现的前提存活着。

劳埃德留下的，不是发明的荣誉，而是更棘手的教训。谜题的难度有时可以越过「困难」直达「不可能」；而看不穿这种不可能性的人，无法区分无解的盘面与仅仅困难的盘面。「出题者负有保证解的存在的责任」——这一现代谜题设计的伦理，讽刺地被他的千美元谎言照得最为清晰。

参考文献

本文所参考的信息来源：

・Wikipedia: 15 puzzle

・Cut the Knot: Sam Loyd's Fifteen, the history of the puzzle

・David Richeson: A picture of frustration — Sam Loyd's 15 puzzle

・MacTutor History of Mathematics: Samuel Loyd (1841-1911)

・Wikipedia: Sam Loyd

・Jerry Slocum & Dic Sonneveld, The 15 Puzzle: How It Drove the World Crazy (Slocum Puzzle Foundation, 2006)

・W. W. Johnson & W. E. Story, "Notes on the '15' Puzzle," American Journal of Mathematics, vol. 2, no. 4 (1879), pp. 397–404

・D. Ratner & M. Warmuth, "The (n²−1)-puzzle and related relocation problems," Journal of Symbolic Computation, vol. 10 (1990), pp. 111–138（初次发表于 AAAI 1986）

・Wolfram MathWorld: 15 Puzzle

结语

我认为，15数字推盘在历史上揭示了两件事。其一，极为简单的滑块规则，将「状态空间」这一近代数学的对象放到了普通大众的手心里。1880年的人们，不知道自己的手指正在摩挲偶置换与奇置换的边界，却在纯粹的逻辑之墙上磨损着指尖。这是谜题将数学民主化的稀有瞬间。

其二，是出题者的诚实问题。萨姆·劳埃德并非发明者，但他在悬赏中埋下的「无解的盘面」，讽刺地将谜题设计的核心突入后世。无法保证解的存在的出题，不是难题而是欺骗。1879年的证明与1880年的狂潮，经过一百四十年，至今仍向每一位打乱牌片的创作者发出同样的追问——那块盘面，真的可解吗？