15 数码问题
15 数码问题，也叫数字华容道，是一个装着十五个带数字方块和一个空格的框。把方块滑回原来的顺序，就解开了。它看起来很简单，却在 1880 年掀起了一阵热潮，背后还藏着趣味数学中最精巧的证明之一：一半的局面永远解不开。
1880 年的热潮
这个谜题来自 1870 年代的纽约州；人们通常认为它的发明者是卡纳斯托塔的邮政局长诺伊斯·查普曼。1880 年初，它掀起了一阵热潮，先是席卷美国，然后传到欧洲。
山姆·洛伊德的 14-15
美国谜题设计师山姆·洛伊德后来声称这个谜题是他发明的，还说谁能在只对调 14 和 15 的情况下解开它，就能得到 1,000 美元奖金。没有人赢得这笔奖金，也不可能有人赢得：那个局面根本无解。他自称发明了这个谜题，也并非事实。
为什么一半的局面不可能
把空格当作第十六个方块。每次滑动都是空格与一个方块交换。空格要回到它的角上，向左和向右移动的次数必须相同，向上和向下移动的次数也必须相同，所以空格在角上的局面，与排好的顺序之间总是相差偶数次交换。对调 14 和 15 是一次交换，是奇数，所以任何滑动都到达不了那个局面。1879 年，威廉·约翰逊和威廉·斯托里证明了恰好一半的排列可以到达。
判断任意局面的方法
逐行读出框里的方块，数一数顺序颠倒的方块对。在 3×3 或 5×5 盘面上，这个数为偶数时局面可解。在 4×4 盘面上，再加上空格从下往上数所在的行数：和为奇数时局面可解。
用计算机求解
计算机可以用 A* 搜索回去的路，A* 总是先查看最有希望的局面。它根据每个方块离目标位置有多远来估计还需要多少步，再为每一对在自己所属的行或列中互相挡路的方块加上两步。在大盘面上，找到最短解会变得非常困难。15 数码最难的局面需要 80 步，而 8 数码从不需要超过 31 步。
在 PictorX 中试试
打开数字华容道，点击一个方块就能滑动它。“打乱”把方块打乱成一个可解的新局面，“求解”一步一步地演示一个解，“显示归位方块”会给已经在正确位置上的方块数字上色。选择“洛伊德的 14-15”可以看到那个不可能的局面，用“大小”可以在 3×3、4×4 和 5×5 之间切换。
常见问题
数字华容道是谁发明的？
人们通常认为发明者是纽约州卡纳斯托塔的邮政局长诺伊斯·查普曼，时间在 1870 年代。山姆·洛伊德后来自称是发明者，这并不属实。
14-15 谜题能解开吗？
不能。它与排好的顺序只差一次交换，而滑动能到达的每个局面都相差偶数次交换。
数字华容道有多少个局面？
16 个格子共有 20,922,789,888,000 种填法。其中恰好一半，即 10,461,394,944,000 种，可以通过滑动到达。
PictorX 会上传什么吗？
不会。谜题画在你浏览器里的画布上。“保存”会下载 PNG，“编辑”会在 PictorX 编辑器中打开那张图。
相关工具
数字华容道
在浏览器中玩经典的数字华容道（15 数码），木制方块可选 3×3、4×4 或 5×5。打乱方块，一次滑动一整行，试试山姆·洛伊德那个不可能完成的 14-15，或者看“求解”把它解完。
汉诺塔
在浏览器中把一座圆盘塔移过三根柱子。每次一个圆盘，大盘绝不能压在小盘上。最短解是 2ⁿ − 1 步。
汉诺塔
汉诺塔：三根柱子，每次一个圆盘，大盘绝不压小盘。最短解是 2ⁿ−1 步。爱德华·卢卡斯于 1883 年提出了这个谜题。
骑士巡逻
让国际象棋的马跳遍棋盘的每一格，每格恰好一次。你可以借助瓦恩斯多夫提示自己玩，也可以看“求解”完成开放巡逻或封闭巡逻。把路径保存为 PNG。
八皇后
在棋盘上放置八个皇后，使它们互不攻击。自己动手试试，观看回溯搜索一步一步找到一个解，再浏览全部 92 个解。
兰顿蚂蚁
在浏览器中运行兰顿蚂蚁。观察对称、混沌和 104 步的高速公路，再试试多色规则、多只蚂蚁、六边形网格和 Turmite。
准备好尝试了吗？
在浏览器中打开 PictorX — 无需安装，无需信用卡即可启动。
玩数字华容道