老顽固
PDF数独算什么，我能做得更好
这股源自日本的新谜题热潮正席卷全球，并考验着我们的布尔逻辑。
斯坦·凯利-布特尔，作者
我将本文献给杰夫·拉斯金（Jef Raskin，1943年3月9日 - 2005年2月26日），以示纪念。比我更有权威的悼念文章还在不断涌现，毫无疑问，一本纪念这位杰出博学之士的纪念文集也将问世。“Le don de vivre a passé dans les fleurs.”
命运弄人，杰夫一定会喜欢这个巧合：IBM在他去世的那一周宣布了OS/2的死讯。或者更确切地说，它发布了《PC World》所谓的“OS/2 走向终结的官方路线图”。人们可以想象一个GPS在发出指令：“左转，然后直行六个月。注意路障。在停车标志处停车。您的旅程结束了。弃车。感谢您的惠顾和耐心。”
关于杰夫·拉斯金去世的噩耗是通过《伦敦时报》上的一篇讣告传到我耳中的。成熟的读者1 每天早上都会首先翻阅《泰晤士报》的讣告版，在确信我们又活过了一天之后2，便匆匆开始做填字游戏（一个方便的四分钟计时器）。但如今对于解题者来说，已经没有速战速决的方法了：我们现在面临着一种新的、令人上瘾的谜题，一种被称为数独（Su Doku）（http://www.sudoku.com）的邪恶时尚。这个游戏起源于日本，但它与西方的谜题，如拉丁方阵和幻方，有一些共同之处。
我被告知，与《泰晤士报》填字游戏中那些神秘的文学离合诗不同，符号/逻辑数独是完全可计算的（尽管并非每个谜题都有唯一解或任何解）。原始网格是一个 9x9 的矩阵，细分为九个 3x3 的单元格。81 个单元格中的一些单元格预先分配了 1-9 的整数，剩下的空白方格则由您来分配整数。每行、每列以及每个 3x3 的方框都必须正好包含数字 1-9，且不重复。这听起来像是一个数字问题。实际上，它是带有危险曲线的摩托车布尔逻辑。可以使用任何九个不同的符号，并且已经有人提出了字母版本。有人建议以 B 到 L 这九个字母（省略元音 E 和 I）用于英语使用者，以免意外出现一些不雅的序列。“辅音诅咒的某些方面”，作为一个有用的博士论文选题，一定会让杰夫·拉斯金的文字游戏爱好感到高兴。
数独的关键在于出题者最初在哪些方格中分配了哪些数字作为“线索”。我们假设这些线索没有违反禁止重复的规则。如果给出的线索太多，谜题可能会变得 trivial。例如，如果给出 81 个合法的线索，那么你就得到了一个无效的游戏，被不敏感的人称为“一片式波兰拼图”。当然，如果没有给出线索，问题就有太多的解决方案，以至于“近似无限”这个词也可以被原谅。上限是 (9!)9，即包括非法配置在内的所有可能的网格条目的数量。Sourendu Gupta 和其他人 (http://theory.tifr.res.in/~sgupta/sudoku/expert.html) 计算出的实际总数为 6,670,903,752,021,072,936,960!，其中作者最后的“!”是感叹号，而不是阶乘！（毫无疑问，数学天才拉马努金会发现这个数字的某些重要意义。我只能冒险猜测，这个 22 位数字的字符串将出现在 pi 的十进制展开式的某个位置。证明我是错的。）
请注意，这是可能的数独解的总数。合法谜题的数量要大得多，但尚不清楚确切数字。不同的线索布局可能会产生相同的解，并且许多猜想仍未解决。例如，据信 17 是可解数独所需的最小线索数。大多数已出版的谜题都有 26 到 42 条线索。通常（也有例外），复杂度随着线索数量的增加而降低，为了减少“数独狂怒”，《泰晤士报》将其评级为非常简单、简单、中等、困难和魔鬼级，并附带一个令人羞辱的完成时间估计。然后，人们还在争论哪些被称为“令人满意”的谜题可以通过纯逻辑在没有反复试验的情况下解决。尽管如此，这些“令人满意”的谜题的供应实际上是取之不尽的——这是一个天赐之物，因为数独正越来越多地出现在报纸、杂志和网站上，并且有整本书专门介绍这种狂热。美国佬们注意了：数独已经感染了《纽约邮报》。
手工创建一个非平凡的数独问题非常费力。计算机大大降低了生成具有多个解（或无解）的数独问题的风险，但仍然存在一些不可计算的、艺术性的方面，这些方面反映了日本人通过对称性体现的美感。线索的放置和避免过多的依赖性线索（即可以从其他线索中容易推断出的线索——这个概念在公理化中也有体现，公理化的目标是一组一致的、独立的公理）带有一种神秘的色彩。这就解释了我过去认为的营销炒作：《泰晤士报》声称其谜题在美学上更胜一筹。当然，将数独推广到全世界的新西兰人韦恩·古尔德（Wayne Gould）在东方花费了数年时间来完善生成《泰晤士报》谜题的程序。
既然谜题是由计算机生成的，那么计算机肯定也能解开它——乐趣就结束了。然而，到目前为止，我所见过的软件似乎只对解题者有所帮助，除非在产生完整解的简单情况下。您完成的每个空格都会触发网格的新一次迭代，而且奇怪的是，您填写某些空格的顺序会改变进一步的进度。您可能会遇到谚语中的“碰壁”情况，即几个空格显然有无法解决的替代方案。我怀疑，与国际象棋一样，算法尚未捕捉到人脑的模式识别能力。已经可以看到，那些可以背着身子复原魔方，或者在脑海中开出非常大的数字的 13 次方根的天才们，正以光速完成最难的数独。
大多数英国人更喜欢用铅笔和橡皮擦勉强应付。然后，当您只剩下几个空格时，却发现它们无解时，就会产生那种受虐般的颤栗——因此需要橡皮擦来进行疯狂的“撤销/重做”序列。关于英国礼仪（Britiquette？）的一个神圣问题是，一位《泰晤士报》读者寻求建议，如果您注意到火车上坐在您旁边的陌生人在同一列中输入了两个 5，该怎么办。共识是避免 kibitzing3，这是一种讨厌的外国习惯。
英国人肯定有一种游戏精神，会抵制自动化解决方案。正如吉卜林或那一伙人中的一位曾经说过：“重要的不是谁输谁赢，而是我们参与了游戏。” 避开“盲目的”算法。相反，展示您大脑天生的布尔筛选器能够多么有效地发挥作用。
最完美的范例是被称为 Mornington Crescent 的“非游戏”（等等）。任何数量的参赛者都可以与一位裁判一起玩，裁判的决定是最终的，并且会受到通常的贿赂。轮流地，每位玩家必须说出一个在该环节中之前未被说出的伦敦地铁站名。有效的、被质疑的重复或不合格的名称（包括空响应）会导致您突然死亡出局。无效的质疑，如果被有效质疑并被裁判接受，也会淘汰虚假的质疑者。获胜者是最后的幸存者或第一个说出 Mornington Crescent 的人！当我们在 20 世纪 50 年代在剑桥玩这个游戏时，通常会有一位缺乏反讽意识的外国参赛者，在第一轮中，他会喊道：“Mornington Crescent！Ach so—wo ist unser Preis？” 全场一片叹息声！
读者挑战：Mornington Crescent 可计算吗？伦敦地铁站名的数量是有限的，因此，在没有过早的“胜负者”的情况下，重复是不可避免的。然而，与国际象棋一样，重复必须受到有效的质疑（被认为是不光彩的？），否则，理论上，游戏可以继续进行下去，直到啤酒喝完。真正的传统英国式、挽回面子的获胜者必须等到 Mornington Crescent 是最后一个幸存的未被命名的车站。即使那样，也必须带着深深的歉意说出来。问
参考文献
- 1 考虑到罕见的错误，例如导致温斯顿·丘吉尔宣称“关于我去世的报道被大大夸大了”的过早讣告。或许，这个好得难以置信的轶事的报道也是如此。
- 2 超负荷的缩写 EOF 可以理解为文件结束（end of file）和非常老的老屁（extremely old fart）两种含义。
- 3 源自意第绪语 kibits’r，指爱管闲事的人。他们会在您编程时盯着您的肩膀，并说：“您在第 5 行有一个悬空的 else。” 崇高的纽约意第绪语吉尔伯特与沙利文歌剧协会已成功“翻译”了《彭赞斯的海盗》。最初的飞行员兼海盗变成了拉比兼强盗。模仿爱国主义的“我是一个英国人”被翻译成 “Ich bin ein gute Yid”（当然，这在意第绪语中并不冒犯）。
斯坦·凯利-布特尔（STAN KELLY-BOOTLE）（http://www.feniks.com/skb/; http://www.sarcheck.com）出生于英国利物浦，20 世纪 50 年代在剑桥大学研读纯数学，之后在先驱性的 EDSAC I 计算机上研究了不纯粹的计算机科学。他的许多著作包括《魔鬼的 DP 词典》（McGraw-Hill，1981 年）和《理解 Unix》（Sybex，1994 年）。《软件开发》杂志已授予他首届年度斯坦·凯利-布特尔 ElecTech 奖，以表彰他在“技术和文学领域的终身成就”。诺贝尔和图灵都没有获得如此珍贵的同名认可。在他的艺名斯坦·凯利（Stan Kelly）下，他还作为歌手和词曲作者享受着并行职业生涯。
最初发表于 Queue 第 3 卷，第 10 期—
在 数字图书馆 中评论本文
© 保留所有权利。