进入正题之前，先写这篇概览的缘由，在于盘点进行算法设计的若干通用策略。尽管在解决某一个具体谜题的时候，未必非要套用这些策略不可，但是它们汇总起来却构成了一套极有用的工具集。这些策略如果运用得当，能够用以解决计算机科学中的众多问题。所以，学会将这些策略应用到谜题中去，可以视为一种很好的计算机科学领域入门途径。
进入正题之前，先写这篇概览的缘由，在于盘点进行算法设计的若干通用策略。尽管在解决某一个具体谜题的时候，未必非要套用这些策略不可，但是它们汇总起来却构成了一套极有用的工具集。这些策略如果运用得当，能够用以解决计算机科学中的众多问题。所以，学会将这些策略应用到谜题中去，可以视为一种很好的计算机科学领域入门途径。
但在着手盘点这些主要的算法设计策略之前，我们要先对两种类型的算法谜题做重要的评点。每个算法谜题皆需要输入，而输入则定义了该谜题的谜面（instance）。谜面可以是具体的（例如，试使用一架天平在8枚硬币中找到一枚伪币），也可以是一般的（例如，试使用一架天平在n枚硬币中找到一枚伪币），这样就区分了两种不同的谜题类型。当求解带有特定谜面的谜题时，解谜者无须为任何超出谜面表述的范围花费功夫。实际上，谜面一变，解法可能完全不同，甚至可能根本没有解。不过，话又要说回来，谜题中煞有介事地放上具体数字，有可能根本并不重要。在这种情况下，毕其功于一役地解决其一般版本不仅让人更有成就感，甚至难度也更小。但无论谜面的形式是具体的还是一般的，先拿少数几种情况尝试尝试，几乎总不会错。在很罕见的一些情况下，解谜者会因为这种尝试而误入歧途，但是远为常见的情形是，这种尝试会为给定的谜题带来有用的洞见。
理论上，许多谜题可以用穷举搜索（exhaustive search）的办法求解。这种解题策略会直截了当地试遍所有的可能解，直至找到问题的解为止。采用穷举搜索时，很少需要运用匠心别裁。因此，如果一道谜题确定要用这种策略来求解的话，就很少需要人工计算，而基本上是为计算机准备的。穷举搜索的最大局限性在于它的效率低下：通常，如果可能解的数量随着问题规模而呈指数增长或更快的话，那么这条途径不仅对人类来说遥不可及，计算机也只能望洋兴叹了。举例来说，考虑构造一个三阶幻方（magic square）谜题好了。
幻方 试将1～9这9个不同整数填入一个的表格，使得每行、每列以及每条对角线上的数字之和相同（见图1.1）。
填满整个表格有多少种方法呢？可以考虑一次填入一个数字，先把1放到某个位置，最后把9放妥。所以，有9种方法可以放置1，接下来有8种方法可以放置2，依此类推，最后，数字9就只能放置在唯一的空置单元格中了。因此，就有9! = 9·8·…·1 = 362 880种方法可以将9个数字排列到3×3的表格单元格中。（这里我们使用了标准记法，，读作的阶乘，来表示从1到的连续整数之积。）所以，采用穷举搜索来求解这个题目时，实际上就是生成把1到9这些不同的整数放入表格的所有362 880种可能排列，然后逐个地检查每一种排列，以验证它们的每行、每列和每对角线的数字之和是否都相等。这样的工作量显然不可能靠手工完成。
图1.1 将1～9的整数填入
3×3表格以构造一个幻方
实际上，不难这样求解：首先证明该公共和的值必为15，所以5必须被放置在中心单元格（参见正文中的谜题重温幻方（#29））。还有，人们可以利用数种已知算法来构造任意阶数的幻方，这些算法对于阶数为奇数的幻方尤其有效（例如第29道谜题）。当然，这些算法的基础并非穷举搜索：在阶数仅仅增长到5这样小的数时，可能解的数量已经大得十分夸张了。，因此即使使用每秒执行100 000亿次运算的计算机，也需要49 000年才能完成这项任务。
采用穷举搜索会遭遇两个主要困难。第一个困难在于产生所有可能解的机制。对于有些问题而言，这些可能解会形成一种具备良好结构的集合。举例来说，将头9个整数置入表格的可能排列（参见上述幻方例题）可以形成这些数字的全排列（permutation），有好几种已知算法可用于此。但还有许多问题，可能解无法形成具备如此规则结构的集合。第二个，也是更加根本的困难在于需要生成和处理的可能解数量。一般地，该集合的规模至少随着问题规模呈指数增长。所以，穷举搜索只在这类题目很小规模的谜面上才可行。
回溯法（backtracking）是对穷举搜索所采取的蛮力做法的一种重要改进。它给出了一种生成可能解的方便方法，这样就可以避免生成不必要的可能解了。其核心思想在于，采用一次添加一个组件的办法来构造解，并且如下评估可能解的“半成品”：如果这个构造到一半的解可以再向前推进一步而不违反题设的约束，则选择第一个合法选项作为下一个部件。如果找不到合法选项作为下一个部件，那么就不再需要去考虑任何其余部件了。在这种情况下，算法就要执行回溯，把当前构造到一半的解的最后一个部件替换成该部件可选的下一个合法选项。
一般地，回溯法总是涉及一定数量的错误选项撤销动作。这个数量越小，算法找到解的速度就越快。尽管在最差情况（worst-case scenario）下，某个回溯算法可能与穷举搜索一样，最终生成了所有的可能解，但这种情况很罕见。
把回溯算法解释成构造一棵反映决策过程的树，是很自然的。计算机科学家们使用术语树来描述带有继承谱系的结构，比如家谱和组织结构图等。一棵树通常用这样的图形来表示：放在顶部的是根结点（唯一没有父结点的结点），位于底部或靠近底部的是叶结点（没有子结点的那些结点）。这样画图的目的，无非是为了符合自然的拓扑结构。应用于回溯算法的时候，这样的一棵树被称为状态空间树（state-space tree）。状态空间树的根结点所对应的，就是解的构造过程的出发点。我们可以认为，根结点放在树的第0层。然后，根结点的子结点——就是那些放在第1层的结点——对应于解的第一个部件的可能选择（比如，在构造幻方时，对应于可以用来放置数字1的那些单元格）。它们的子结点——就是那些放在第2层的结点——就对应于解的第二个部件的可能选择，依此类推。状态空间树的叶结点有两种可能的类型。第一种被称为无望结点（nonpromising node）或死路结点（dead end），这种结点对应的是那些不可能达成解的“半成品”。一旦构造出了无望达成解的结点，回溯算法就会中止该结点（称为树的剪枝），通过回溯至无望结点的父结点，并考虑该部件的下一个选项的办法来撤销针对可能解最晚添加的一个部件所做出的决策。而第二种叶结点就是解结点了。如果搜索到一个解，算法会就此终止。如果还需要搜索其他的解，则算法回溯到叶结点的父结点，继续搜索下去。
下面是个演示回溯算法在特定问题中的应用的经典例子。
n皇后问题 将n个皇后放置在n×n的国际象棋棋盘上，其中没有任何两个皇后处于同一行、同一列或同一对角线上，以使得它们不能互相攻击。
在n=1的条件下，该问题有平凡解。而在n=2和n=3的条件下，容易看出该问题无解。所以我们从4皇后问题入手，采用回溯法来求解。由于每个皇后都要放到它独占的一列中去，我们只需要把每个皇后在棋盘上分配到某一行上就可以了，见图1.2。
我们以空棋盘作为出发点，把皇后1放置到第一个可能的位置，即第1列的第1行。接下来放置皇后2，经历过把它放置到第2列的第1、2行的两次不成功的尝试以后，找到了放置它的第一个可行位置，就是棋位(3,2)，即第3行第2列的方格。但这是一条死路，因为这么一来第3列就没有任何位置可以放置皇后3了。是故，算法执行回溯操作，把皇后2移动到下一个可能的棋位(4,2)。接下来，皇后3被放置到(2,3)，又是一条死路。于是，算法一路回溯到皇后1，并把它移动到(2,1)。皇后2紧接着被放置到(4,2)，皇后3放置到(1,3)，皇后4放置到(3,4)，这就形成了问题的一个解。图1.3给出了本次搜索的状态空间树。
图1.2 4皇后
问题中的棋盘
如果需要找其他解（4皇后问题只有一个其他解），算法可以直接从它停下来的那个叶结点继续搜索下去。另一个办法是利用棋盘的对称性获得所求的解。
图1.3 采用回溯算法求解4皇后问题的状态空间树
图注：X表示将皇后摆放在该行的尝试失败；结点上方的字母给出了各个结点的生成顺序。
一个解
回溯法比穷举搜索算法能快多少？如果我们考虑 4 个皇后在棋盘上放置在4个不同棋位的所有可能，那么总数就是
（求从个不同对象中不计顺序地选取个不同对象的取法总数，数学上称为从个不同对象中每次取个的组合，记作，或
，其值为
。）如果仅考虑位于不同列的皇后，可能解的总数骤降为
。如果增加约束，规定皇后必须位于不同行，选项数就进一步降到了
。最后，这个数看上去十分温良，但是如果换成规模更大的谜面，就完全不是那么一回事了。比如，如果换成普通的
棋盘，可能解的数量就成了8! = 40 320。
读者诸君可能有兴趣了解，8皇后问题总共有92个解，其中12个是本质上完全不同的，而其余的80个则可以从这12个基础解出发，通过旋转和镜射得到。一般地，在的条件下，n皇后问题都有解。可是，尚没有发现一个解的数量公式对任意的都成立。已知解的数量随着值的增加，增长得非常快。例如，在n=10的条件下，解的数量为724，其中有92个本质不同的解。而在n=12的条件下，对应的数字为14 200和1 787。
本书中有很多谜题可以采用回溯法求解。而对于每一个可以采用回溯法求解的问题，读者都应该努力寻找某种更有效的算法。特别地，正文中的重温n皇后问题（#140）就要求读者设计一种快得多的算法来求解n皇后问题。
减而治之（decrease-and-conquer）策略的基础，在于从给定问题的解及其较小规模谜面的解之间找到某种关系。一旦找到，这样的关系就可以自然而然地导向某种递归算法（recursive algorithm），它可以将问题减少为一系列的、规模越来越小的谜面，直至可以一下子解决为止1。请看一个例子。
名流问题 在总人数为的人群中的名流，就是指不认识任何人，所有其他人却都认识的人。问题的任务是：仅仅通过向人们提出形如“你是否认识某某”的问题，来识别出名流。
为简化该问题，假设在给定总人数为的人群中存在名流，该问题可以采用下述“每次减一”的算法来解。如果，则根据定义，这仅有的一个人肯定是名流。如果，则从人群内任选两人甲和乙，并问甲是否认识乙。如果甲认识乙，则将甲从可能成为名流的其余人中移除；如果甲不认识乙，则移除乙。然后，对其余个可能成为名流的人群采用递归方式求解（使用相同的方法）即可。
作为简单练习，请读者尝试对正文部分的谜题士兵摆渡（#4）求解。
一般地，采用减而治之方法求解时，较小谜面的规模未必是。尽管“每次减一”乃是规模减少的最常见情况，减少幅度更大的例子也是有的。如果我们能够在每次迭代时，把谜面规模降低一个常数因子，比方说减半，那我们就能获得极快的算法。这种算法的一个著名例子源自下面的著名游戏。
猜数字 （允许提20个问题）仅通过提问答案为“是”或“否”的问题，在到（含）的范围内判定一个事先选择的整数。
针对本题的最快算法，在提问时每次迭代都可以将包含答案的集合大小大约减半。例如，第一个问题可能是“选择的整数大于吗？”。
表示向上取最接近
的整数。2如果答案是“否”，那么选择的整数就在从1到
的范围内；如果答案是“是”，那么选择的整数就在
到n的范围内。无论答案是什么，算法都将原始问题的规模减半，而问题的形式则保持不变。重复执行算法，当谜面规模减少到时，问题即告解决。
由于该算法每次将谜面的规模大约减半（这里说的谜面，是指处理后仍然包含选择整数的范围），所以它快得惊人。例如，当n=1 000 000时，算法只要求提不多于20个问题。这已经够快了，但是如果某个算法能以更大的因子，比如，来减小谜面规模的话，则还会更快。
正文部分硬币中的假币（#10）这道谜题说明了减而治之策略中“每次减少常因子”（decrease-by-constant-factor）这种变体，也是读者看到这里以后可以去做的一道很好的习题。
值得一提的是，有时通过自底而上的方法来发掘较大和较小问题之间的关系，可能会更简单。这就是说，先把谜题的最小规模谜面解出，然后再看第二小的，依此类推。这种方法有时称为增量法（incremental approach）。具体的例子参见正文部分矩形切割（#3）的第一种解法。
分而治之（divide-and-conquer）策略就是要把一个问题划分成若干较小的子问题（通常具有相同或相关的类型，理想情况下规模也大致一样），然后各个击破，最后在必要时把子问题的解组合起来，就得到了原始问题的解。这种策略囊括了计算机科学中的诸多有效算法。有些出人意料的是，能够采用分而治之求解的谜题并不多。但下面这个例子很出名，它完美地说明了本策略。
三格骨牌谜题 使用适当的三格骨牌来覆盖一块缺了一格的棋盘。所谓三格骨牌就是L形的相邻三格。棋盘上缺的可以是任何一格。三格骨牌必须覆盖除缺格以外的全部其他格，且不能有重叠。
本题可以采用递归的分而治之算法求解，如图1.4所示，先在棋盘中央放置一块三格骨牌，这样规模为的问题谜面就变成了各自规模为的四个相同问题。当每个缺了一格的的区域都被算法生成的一块三格骨牌所覆盖时，算法即告终止。
读者或许想要完成如图1.4所示的8×8棋盘的铺陈，这会是个快速但有用的练习。
大多数分治算法都采用递归方式求解较小规模的子问题，因为，正如上例所示，子问题表示的是相同问题的较小谜面。但也不总是如此，特别地，有些同样涉及棋盘的问题，棋盘可能需要被分割成的子棋盘并不一定就是给定棋盘的缩小版。这样的例子参见本书正文部分的2n筹码问题（#37）和直三格骨牌铺陈（#78）。
关于分而治之策略，还有一点值得一提。尽管有些人把减而治之（前面讨论过）视为分而治之的一种特殊情况，但还是把减而治之当作一种独立的设计策略比较好。这两者的本质区别在于每一步需要解决的子问题个数：分治算法每一步需要解决多个子问题，而减治算法则仅需要解决一个。
图1.4 三格骨牌在缺了一格的2 n×2n 棋盘上铺陈的第一步，采用分治算法
变而治之（transform-and-conquer）是一种人尽皆知的解题途径，它的思想基础是变换。问题的求解分为两个阶段。首先是变换阶段，某个问题被修改或变换成另一个问题，出于某种理由，修改或变换后的问题较容易求解。在我们的算法解题的领域里，人们可以看到本策略的三种变体。第一种变体称为谜面简化（instance simplification），即首先将问题的一个谜面变换成同样问题的另一个谜面，而该谜面具备某种特殊性使得问题较易求解，如此将问题解出。第二种变体称为表示变更（representation change），它的基础是把问题的输入变换成另一种表示，从而更有助于找到有效算法来求解。第三种变体称为问题归约（problem reduction），即把给定问题的谜面整体转化为另一个问题的谜面。
先举个例子，考虑Jon Bentley编写的《编程珠玑》一书中的一道像谜题的题目。
变位词检测 变位词就是由相同的字母组成的单词。比如，eat、ate和tea就是变位词。设计一种算法，在一个巨大的英语单词文件中找出所有的变位词集合。
该题的有效算法分为两个阶段。首先，它为每个单词指派了一个“签名”，就是单词按其组成字母重新排序的结果（这里采用了表示变更），然后，将文件按签名的字母顺序排序（将数据排序是谜面简化的一个特例），这样变位词就可以彼此靠在一起了。
读者可以动手求解谜题数字填充（本书中第43号谜题），它运用的思想是一样的。
另一种间或有用的表示变更，是采用问题输入的二进制或三进制表示。若读者不熟悉该重要议题，这里作简要介绍。逢十进位的系统是世界上大部分地区在过去800年里一直使用的，其中整数采用的幂组合来表示，例如， 。而在二进制和三进制系统中，整数相应地采用或的幂组合来表示。例如，，因为 又因为 。十进制数是由10个数字（0～9）中的某些组成的，组成二进制数的数字只有两种可能（0和1），而三进制数则只有三种可能（0、1和2）。每个十进制整数在这些系统中的任一种里面，都有唯一的表示，只要把它不断地除以2和3即可。二进制系统尤为重要，因为对于计算机实现来说，它业已被证实是最方便的。
下面举一个利用了二进制系统的谜题的例子，W. Poundstone的著作提及的一个问题。
现金分装 你手里有1000张1美元的钞票。如何将其分装到10个信封内，使得从1到1000美元（含）的任何数额皆可仅用若干信封的组合给出？当然，不允许找零。
我们可以把数量为1、2、22、…、28张1美元钞票分装在前9个信封内，然后把数量为张1美元钞票放入第10个信封内。这样，任何小于489的数额都可以用的幂组合得到：
，其中，系数b8、b7、……、b0非0即1（这些系数，实际上就组成了的二进制表示。使用9位二进制数能够表示的最大整数是
），而若在489～1000（含），则它可以表示为
，其中
，这样它就可以使用第10个信封加上前9个信封的组合得到，后者其实就是
的二进制表示。值得指出的是，对于某些数额而言，本谜题的解并不唯一。
作为一个很好的练习，读者可以尝试求解谜题Bachet的砝码（#115）的两个版本，它们分别利用了二进制系统，以及三进制系统的某种变体。
最后，许多题目可以通过变换成图论问题求解。所谓图（graph），可以把它想象成平面上的有限个点，以及将其中的一些连接起来的线段。这些点和线段分别称为图的顶点（vertex）和边（edge）。边可以是无向的，也可以规定从一个顶点出发到另一个顶点结束这样的方向。前一种情况下，称该图为无向图；而后一种，则称为有向图（directed graph，或简写为digraph）。在谜题和博弈中，图的顶点往往用来表示题目中的问题的各种可能状态，而边则表示状态之间的可能变化。图中要有一个顶点表示初始状态，还要有一个顶点表示题目的目标状态（但是，表示目标状态的顶点可能有多个）。这样的图称为状态空间图（state-space graph）。总而言之，上述变换将题目归约到了在初始状态顶点和目标状态顶点之间寻找一条路径的问题。
下面看一个具体的例子，考虑一个古老而著名问题的较小谜面3。
两个吃醋的丈夫 两对夫妇要过河。他们只有一条小船，每趟只能承载不多于两人。麻烦在于，两个丈夫都很吃醋，不肯让自己的妻子在没有自己陪伴的前提下与别的男人独处。试问，在这样的约束下，能否所有人成功过河？
本谜题的状态空间图如图1.5所示，其中Hi和Wi分别代表第对夫妇中的丈夫和妻子（取值1和2）；两根竖线| |代表河；小船的位置由灰色椭圆表示，它也指示了下一次过河的方向。（为简化起见，图中没有包含那些仅通过明显的下标替换相区分的过河步骤，比如第一步让第一对夫妇H1W1而不是第二对夫妇过河。）对应于初始和结束状态的顶点以加粗的边框表示。
图1.5 两个吃醋的丈夫谜题的状态空间树
从初始状态顶点到结束状态顶点共有4条最短路径，每条路径由5条边构成。把路径用边来表示，结果如下：
是故，本题共有4个最优解（不包括明显的对称变换），每个解要求过河5次。
传教士与食人族谜题（#49）可以作为此类策略的又一道练习题。
关于用图表示来解题，有两点值得一提。首先，如何为更复杂的谜题建立状态空间图本身可能就是一道算法题。事实上，建立状态空间图可能会由于需要考虑的状态和变换数量太大而变得不可行。比如，用来表示魔方的状态图包含顶点的数量多于个。其次，尽管理论上图的顶点画在哪里并不重要，但是精心选择顶点在平面上的位置却可能为题目中的问题提供重要的洞见。比如，考虑下面这道谜题。通常认为本题在1512年出于Paolo Guarini之手，但其实在公元840年左右就已经在阿拉伯棋谱中发现过它的踪迹了。
Guarini谜题 在的国际象棋棋盘上有4枚骑士4白方的两枚骑士位于底部两个角落，黑方的两枚骑士位于顶部两个角落（如图1.6所示）。试用最少的步骤移动棋子，使得白方的骑士移至顶部两个角落，而黑方的骑士移至底部两个角落。
图1.6 Guarini谜题
由题意自然想到把棋盘的各个格子（即在图1.7（a）中简化成连续整数者）表示成图的顶点，这样就可以使用连接两个顶点的边来表示在顶点所代表的格子之间的一次移动。如果仿照棋盘上的原位来放置我们的顶点，我们就会得到如图1.7（b）所示的图。（由于位于中央、编号为5的格子是骑士所走不到的位置，因此这里就省略掉了。）可是，图1.7（b）对问题求解没有多少助益。如果我们把顶点摆成一圈，使得它们能够从顶点1开始依次被各枚骑士走到，如图1.7（c）所示，这样就能够得到一张清楚得多的图案5。从图1.7c中可以清楚地看出，每一枚骑士走的每一步都保留着所有的骑士之间按顺时针和逆时针排列的相对顺序。是故，若要以最少步数解出这个谜题，只有两种方法：让每一枚骑士都按顺时针或逆时针方向沿着图示的边走，直到每一枚骑士都首次抵达对角为止。而每个这样的对称解都需要总共16步。
图1.7 （a）Guarini谜题中对棋盘格子的编号（b）将谜题采用直接的图表示（c）优化的图表示
试解一下谜题星星上的硬币（#34），作为图变换方法的巩固练习。
还有一些谜题可以归约为数学问题，如解方程或求函数最值的问题来求解。示例如下。
最优馅饼切法 在一块矩形的馅饼上切刀，最多能把馅饼切成多少块？规定只能平行于馅饼的边进行横切或竖切。
馅饼横切了刀、竖切了刀以后，就会被切成块。由于切分次数等于，则原题可归约为求下式的最大值：
其中，的取值范围为从到的整数（含n）。由于h(n-h)数，所以，函数欲取最大值，则当n是偶数时，须h=/2；当n是奇数时，须向上或向下取整（记作或
）。所以，当是偶数时，谜题有唯一解
；当是奇数时，有两个解（可视为对称解）
、
，以及
、
。
采用贪心法（greedy approach）求解最优化问题，就是经过一系列步骤，步步为营地对一个部分构造的解进行扩展，直至达成一个完整的解为止。
步步为营——这就是本策略的核心所在，每一步怎么走，取决于如何能够产生最大的短期收益并且不违反题设的约束。每一步都如此“贪心”地在所有选择中选取最好的一个，实际上是把希望寄托于局部最优解的序列可以最终产出整个问题的（全局）最优解。这种直线思维式的解法在某些情况下奏效，但在某些情况下则行不通。
如果一道谜题可以采用贪心法求解，那么我们就不能指望从求解的过程中收益很多：但凡是好的谜题，基本上都会设计得足够“精巧”，如此直线思维式地求解，行不通。不过，能够采用贪心法求解的谜题也还是有的。通常，设计一个贪心算法并不难，难点在于证明真的能够产出最优解。下面的谜题就是一个例子。
不可互攻的王 在一张棋盘上放置尽可能多的王，使得它们两两互不相邻—纵向、横向和对角线方向皆如此。
从贪心策略的视角出发，我们可以在一开始在第一列放置尽可能多的互不相邻的王（4枚）。接下来要跳过第二列，因为不能和第一列已经放置的王相邻。我们只能再把4枚王放置在第三列，并跳过第四列，依此类推，直至我们最终将16枚王放到了棋盘上为止（如图1.8a所示）。
图1.8 （a）16个不可互攻的王的摆位（b）证明不可能
摆放大于16枚不可互攻的王的棋盘划分
为了证明要在棋盘上放置多于16个互不相邻的王是不可能的，我们可以把棋盘划分为16个纵四横四的正方形区域，如图1.8（b）所示。显然，想在任何一个正方形区域内放置多于一枚王都是不可能的，这也就揭示了棋盘上放置互不相邻的王的总数不可能超过16。
我们要举的第二个例子尤其出名，因为据说这道谜题曾经被微软公司用作面试题。
夜过吊桥 一行4人A、B、C、D，只有一个手电筒，需要在夜间过一座吊桥。桥身最多承载两人的重量，并且无论是一人还是两人在过桥时都需要手电筒照明。手电筒只能让人携带着来回，不可以扔来扔去。A过桥需要1分钟，B需要2分钟，C需要5分钟，D需要10分钟。如果结对过桥，就只能迁就速度慢的那个人。试求过桥的最快方案。
图1.9 夜过吊桥谜题的贪心解法
如果按照图1.9所示的贪心算法来求解，应这样做：先让最快的两个人A和B过桥，花费2分钟；然后让两个人中比较快的那个人把手电筒带回来，再花费1分钟；然后让其余人中最快的两个人A和C过桥，花费5分钟；然后让最快的A把手电筒带回来，再花费1分钟；最后，余下的两个人一起过桥，花费10分钟。这么一来，根据贪心策略制定的行程，一共需要花费分钟，但是这并不是最快的可能解，参见本题在正文中的解法（#7）。
不用图解，仅用贪心法来重温谜题星星上的硬币（#34），读者也会很有启发。
贪心算法是一块块地将解拼凑出来的，而迭代改进（iterative improvement）算法则是从易得的估计解出发，并重复地应用同样的简单步骤不断地改进估计解。要验证这种算法，就需要确认存疑的算法是否真的可以在有穷步内终止，最终得到的估计解是否真的解决了问题。试求解下面这个谜题，它是根据Martin Gardner在其名著《啊哈！灵机一动》[Gar78, pp. 131-132]中的一道题目改编的政治立场上的正确版本。
柠檬水摊设点 艾力克斯（Alex）、布兰达（Brenda）、凯茜（Cathy）、丹（Dan）和厄尔（Earl）五个朋友想合伙摆个柠檬水摊，他们分别住在图1.10（a）中以A、B、C、D、E标识的五处。试问，这个摊要摆在哪个十字路口，才能距离所有人的家最近？距离的计算是指家和摊点之间的纵横街区总数。
图1.10 （a）柠檬水摊设点谜题的谜面（b）算法的各个步骤（c）算法算得的距离值
一开始，他们决定在1号十字路口摆摊（如图1.10（b）所示），这一点是住在最左边的A与最右边的B之间的水平中点，以及住在最上面的A与最下面的E之间的垂直中点。但很快有人发现，这个位置并不是最佳的可选选址。所以他们又决定采用如下的迭代改进算法：以他们的初步选择为出发点，然后按照某种特定顺序尝试距离该点一个街区的各个位置，例如上（北）、右（东）、下（南）、左（西）。只要新位置比旧位置离所有人的家近，就用新位置来取代旧位置，然后重复这个过程。如果四个相邻的位置都不近，就认为找到了最优位置，并终止算法。算法的各步操作如图1.10（b）所示，而算得的距离如图1.10（c）所示。
图1.10（c）标示的3号位置看上去是一个不错的选择，不过算法并未提供可靠的证明来说明它就是全局最优解。换句话说，谁能保证和选中的位置再隔一个街区的某个方向上的位置不是最优解？谁又能保证任何一个其他十字路口不是最优解呢？其实，我们的担心是多余的：这个位置的确是最优的，并且读者可以在本谜题的推广——谜题地点选择（#74）的求解中了解到如何证明这一点。
再看一道可以采用迭代改进策略求解的谜题。
正数变号 给定一个的实数表格，能否找出一个算法，能够在仅允许将一整行或一整列的数字改变符号的前提下，使得所有的行和列之和非负？
自然而然的想法是寻找一个算法，每步都能增加和为非负数的行列个数。但是，把和为负数的一行（列）数字的符号改变以后，可能另外的列（行）的和就变成负数了。一种巧妙的办法是关注表格中全部数字之和。由于它可以用所有的行和或列和之总和来算得，将原本为负数和的某行或某列改变符号，必然会使得总和增加。我们可以反复寻找负数和的行或列，一旦找到就改变其符号；如果找不到了，就达成了目标，算法即告中止。
这样就可以了吗？恐怕不行。我们还要证明算法不会永远进行下去，即不会无法中止。这个算法符合该要求，因为反复应用算法的所有操作，只能得到有限个不同的表格（因为表格中的个元素最多只能两种状态）。是故，表格中所有数字的和也只能是有限个。由于算法产生的表格有着递增的元素和，所以它必然会在有限步内中止。
上述的两个例子中，我们都利用了问题的以下几点特征：
这种特质称为单变性（monovariant）。寻找适当的单变性是需要技巧的任务。这就使得包含单变性的谜题在数学竞赛中很常见。例如，上面的第二个例子就曾用在1961年全俄数学奥林匹克的训练题中[Win04, p.77]。可是，如果把迭代改进策略和单变性仅仅看成是数学玩具，那就错了。计算机科学中的一些最重要的算法，如单纯形法（simplex method），其基础就是该方法。感兴趣的读者可以在本书较难谜题部分找到若干涉及单变性的谜题。
动态规划（dynamic programming）被计算机科学家们用来解决有着彼此重叠子问题的问题。其解法并不是一遍遍地对彼此重叠的子问题求解，而是只对较小规模的子问题求解一次，然后把结果记录在一个表格中。而原问题的解就可以从表格中得到。动态规划是一名杰出的美国数学家Richard Bellman在20世纪50年代发明的，当时是作为求解多阶段决策过程的通用方法提出。对于欲用本方法求解的最优化问题而言，问题必须具备所谓的最优子结构（optimal substructure），只有这样，才能从子问题的最优解有效地构造出全局最优解。
举个例子，考虑最短路径计数问题。
最短路径计数 假设某城市中全是完全纵横方向的街道，计算十字路口A和B之间的最短路径条数如图1.11（a）所示
图1.11 （a）用动态规划法计算到十字路口(i, j)的最短路径数，
（b）从十字路口A到各十字路口的最短路径数
令表示从十字路口A到第行第列交叉的十字路口的最短路径条数。任何最短路径都是水平向右的街道数和垂直向下的街道数组成的。所以，从十字路口A到第行第列交叉的十字路口的最短路径数可以视为从十字路口A到第行第列交叉的十字路口的最短路径数（记作）和十字路口A到第行第列交叉的十字路口的最短路径数（记作）之和：
又有
从上述公式可以逐行逐列地计算出所有的的值。
该问题也可以采用简单的组合法求解。由于最短路径至多由4条水平街道和3条垂直街道构成，互不相同的最短路径就只能从7种可能性中选出3种垂直街道来求得。这样，最短路径总数也就是7选3的可能性数量，也就是6。可是，对于这道简单的例题来说，组合解法更快，并不意味着在不规则的网格中进行路径计数时这一点同样成立。读者可以试着求解正文部分谜题被堵塞的路径（#13），就知道以上绝非妄言。
尽管有些动态规划的应用一点儿也不直截了当，谜题寻找最大和（#20）和硬币收集（#62）仍然可以作为本策略的简单应用，在此建议读者练习求解。
1 递归是计算机科学中最重要的概念之一。不熟悉这个概念的读者可以从维基百科中的“递归（计算机科学）”条目等处查询相关的参考资料和链接。
2 称为实数的向上取整函数，取值是大于或等于的最小整数。如且；而称为实数的向下取整函数，取值是小于或等于的最大整数。如且。
3 本谜题的经典版本来自已知最古老的拉丁语数学问题全书《磨练青年人的命题集》（拉丁语：Propositiones ad Acuendos Juvenes），传说为生活在英格兰诺森布里亚王国约克市的著名学者Alcuin（约735—804）所作。题目原文的表述现在看来，更加直白。
4 国际象棋中，knight一般译为“马”。但是本书中多处用到了诸如“跨越多瑙河的骑士”、“亚瑟王的骑士”这种搭配，为统一起见，knight一律译为“骑士”，此情非得已，特告读者。——译者注
5 Dudeney [Dud58, p. 230] 将这种变换称为纽扣丝线法（buttons and strings method）：把图的顶点和边分别看作纽扣和丝线，就可以把图1.7（c）中的2、8、4、6号“纽扣”换至对边的办法将它们提起来，并为丝线“解除纠缠”。
6 熟悉基础组合学的读者会发现P[i,j]的值也可以从A点开始，从西南至东北方向的对角线沿着十字路口算出来。算得的值是著名的组合结构帕斯卡三角形的元素（参见[Ros07, 5.4节]——又称杨辉三角形，译者注）。
本文节选自《算法谜题》