我们将要讨论的第一个经典问题是一位需要过河的农夫所面临的难题。读者以前可能已经遇到过类似性质的问题。
怎样过河
一位农夫带着一只狐狸、一只鹅和一袋玉米过河。农夫有一条划艇，只能容纳他自己加上其中一件物品。遗憾的是，狐狸和鹅都饥肠辘辘。狐狸和鹅不能单独待在一起，因为狐狸会吃了鹅。同样，也不能单独把鹅和那袋玉米放在一起，因为鹅会吃了玉米。农夫怎样才能把所有东西都送过河呢？
图1.1展示了这个问题的场景。如果读者以前从来没有遇到过这样的问题，可以花几分钟的时间认真研究一下怎样解决这个问题。如果以前曾经遇到过这样的问题，也可以回忆一下它的解决方案，看看自己有没有办法独立解决。
图1.1 狐狸、鹅和一袋玉米。船一次只能载一样物品。
狐狸不能单独和鹅待在同一岸边，鹅不能单独和玉米待在同一岸边
在没有任何提示的情况下，很少有人能够解出这个难题。作者也自认没有这个能耐。下面是人们解决这个问题时的通常思路。由于农夫一次只能携带一样物品，因此他需要往返多次才能把所有物品送到对岸。在第一趟过河的时候，如果农夫带走狐狸，鹅就会单独和那袋玉米待在一起，肯定会吃了玉米。类似地，如果农夫选择带走那袋玉米，狐狸就会和鹅单独呆在一起，鹅也难逃被吃的厄运。因此，农夫第一趟必须带鹅过河，从而出现如图1.2所示的场景。
图1.2 解决狐狸、鹅和玉米问题必然采取的第一步。
但是，从这一步开始，所有后续的步骤看上去都将以失败告终
到目前为止，一切正常。但在第二趟过河时，农夫必须带走狐狸或玉米。但是，不管这次农夫带走什么，当农夫从对岸返回取最后一件物品时，第二趟所带去的物品必须在对岸与鹅单独待在一起。这意味着，要么是狐狸和鹅独处，要么鹅和玉米独处。由于这两种情况都是无法接受的，因此问题看上去似乎是无法解决的。
如果读者以前曾经看到过这个问题，很可能还记得解决方案的关键要素。如前所述，农夫在第一趟时必须带走鹅。在第二趟时，我们假设农夫带走了狐狸。但是，他并不是让狐狸和鹅一起待在对岸，而是在返回时把鹅带回近岸。然后，农夫把玉米带到对岸，将狐狸和玉米放在一起后返回。在第四趟过河时，农夫最后把鹅带走。图1.3展示了完整的解决方案。
这个问题很难，因此大多数人从来不会想到把物品再从对岸带回近岸。有些人甚至觉得这个问题是不公平的，表示：“你并没有说我可以把物品带回来！”确实如此，但是在描述问题的时候，题目也没有说禁止从对岸把物品带回来。
图1.3 狐狸、鹅和玉米难题的一步步解决方案
可以想象一下，如果事先明确说明可以把物品从对岸带回来，这个问题就会相当容易解决：
农夫有一条划艇，可以来回搬运物品，但小艇每次只能容纳农夫自身再加上他的三件物品之一。
有了这个说明之后，很多人都能解决这个问题了。这说明了解决问题的一个重要原则：如果没有意识到所有可以采取的动作，很可能无法解决问题。我们可以把这些动作称为操作。通过列举所有可能的操作，可以解决许多问题。我们只要测试这些操作的每种组合，直到发现可行的方案。概括地说，就是用更加形式化的术语重新陈述一个问题，常常可以发现此前被我们所忽略的解决方案。
我们先把这个问题的解决方案抛之脑后，然后用更形式化的方式陈述这个特定的难题。首先，我们列出了约束条件。这个问题的关键约束条件如下。
1．农夫在船中一次只能放一件物品。
2．狐狸和鹅不能单独放在同一岸边。
3．鹅和玉米不能单独放在同一岸边。
这个问题是说明约束条件重要性的一个很好的例子。如果我们去除所有的约束条件，这个问题就毫无难度。如果我们去除第一个约束条件，可以简单地一次携带全部3件物品过河。即使一次只能在船上放两件物品，也可以让狐狸和玉米先过河，然后再带鹅过河。如果我们去掉第二个约束条件（但保留另两个约束条件），就必须小心谨慎了。首先要带鹅过河，然后带狐狸过河，最后带玉米过河。因此，如果我们忘了或忽略了任何一个约束条件，就相当于遇到了小林丸号这样的情况。
接着，我们列出所有的操作。陈述这个问题的操作可以采用多种不同的方式。我们可以创建一个特定的列表，列出所有可以采取的操作。
1．操作：把狐狸带到河的对岸。
2．操作：把鹅带到河的对岸。
3．操作：把玉米带到河的对岸。
但是必须谨记，以形式化的方式重新陈述问题的目标是为了能够更好地发现解决方案。除非我们已经解决了问题并发现了“被隐藏的”可能操作（也就是把鹅带回到近岸），否则我们是无法通过上面所列出的这些操作方式发现这个操作的。因此，我们应该设法列出更基本（或参数化）的操作。
1．操作：把船从岸的一边划到另一边。
2．操作：如果船为空，从岸上装载一件物品。
3．操作：如果船不为空，把物品卸到岸上。
通过用最基本的术语来考虑问题，上面的操作列表可以让我们轻松地解决这个问题，就不会把“把鹅从对岸带回近岸”看成是什么奇思妙想了。如果我们枚举所有可能的移动序列，当每个序列违反了其中一个约束条件或重复了此前已经看到过的一个配置时就终止该序列，最终能够得到图1.3所描述的序列并解决这个问题。通过形式化地重新陈述这个问题的约束条件和操作，就成功地避开了它内在的困难性。
经验和教训
我们可以从狐狸、鹅和玉米的问题中学到什么呢？
用更形式化的方式重新陈述问题是一种非常出色的技巧，可以让我们拥有对问题更好的洞察力。许多程序员设法与其他程序员一起讨论问题，并不仅仅因为对方可能已经有了答案，而是因为清晰地陈述问题常常会激发有用的新思路。重新陈述问题就相当于与其他程序员讨论问题，只不过现在是一人分饰两角。
更深远的意义在于，认识到思考问题很可能与思考解决方案具有相同的工作效率，甚至更胜一筹。在许多情况下，通往解决方案的正确道路本身就是解决方案。
瓷砖滑块问题存在许多不同的规格，正如我们稍后所看到的那样，它提供了一种特定的解决机制。下面是对3×3版本的瓷砖滑块问题的描述。
滑动8块
一个3×3的网格中放了8块瓷砖（编号从1～8），剩下一格为空。一开始，网格的配置很杂乱。瓷砖可以滑动到邻近的空格中，使它的原先位置为空。这个问题的目标是在网格中滑动瓷砖，使它们从左上角开始在网格中有序地排列。
图1.4展示了这个问题的目标。如果读者之前从来没有遇到过这样的问题，可以花些时间考虑怎么解决。网络上可以找到大量的滑动瓷砖问题模拟程序，但最好还是用扑克牌或索引卡在桌上试验。图1.5显示了推荐的初始配置。
图1.4 8块瓷砖版本的瓷砖滑块问题的目标配置，
空格表示邻近的瓷砖可以移动到的空间
图1.5 瓷砖滑块问题的一个特定初始配置
这个问题与前面所讨论的农夫与狐狸、鹅和玉米的问题截然不同。过河问题的难度在于可能会忽略其中一种可行的操作。在这个问题中，并不会发生这样的情况。对于任何特定的配置，空格周围最多有4块瓷砖，它们都可以移动到这个空格中。这样的描述已经枚举了所有可能的操作。
这个问题的难度在于解决方案所需的漫长的操作环节。一系列的滑动操作可能把某些瓷砖滑动到它们的目标位置，同时又把其他瓷砖移出正确位置，或者可能把某些瓷砖滑动到靠近目标位置，同时又把其他瓷砖滑动到远离目标位置。由于这个原因，很难认定任何特定的操作是否朝着最终的目标迈近了一步。因为没有办法衡量进度，所以很难形成一种策略。很多人通过随机的滑动来解决这个问题，希望恰好能够滑动到最终的目标配置。
但是，瓷砖滑块问题还是存在策略的。为了演示其中的一种方法，我们可以考虑一个更小的网络，它是长方形的，而不是正方形的。
滑动5块
有一个2×3的网格里放了5块瓷砖（编号从4～8），另外剩下1个空格。一开始，这些瓷砖排列得很混乱。瓷砖可以滑动到邻近的空格中，使自己原来的位置成为空格。这个问题的目标是使这个网格中的瓷砖排列有序，4号瓷砖出现在网格的左上角，接下来依次类推。
读者可能注意到这几块瓷砖是以4到8编号的，而不是从1到5。读者很快就能知道这样安排的原因。
尽管它是与8块的瓷砖滑块相同的基本问题，但只有5块瓷砖显然要简单得多。尝试完成如图1.6所示的配置。
如果试上几分钟，很可能会找到一种解决方案。从较小数量的瓷砖滑块问题出发，我开发了一个特定的技巧。这个技巧加上我们稍后将要进行的讨论，可以用来解决所有的瓷砖滑块问题。
图1.6 2×3版本的瓷砖滑块问题的一个特定起始配置
我把这种技巧称为“串列”，它基于对一组瓷砖位置所形成环路的观察。这些位置加上空格就构成了一个瓷砖串列，可以在这个环路中旋转，同时保持这些瓷砖的相对顺序。图1.7演示了由4个位置所组成的最小可能串列。在一开始的配置中，1可以滑动到空格中，2可以滑动到1移走后所留下的空格中，最后3可以滑动到2移走后所留下的空格中。这样，空格就与1相邻，使这个串列可以继续旋转。因此，这些瓷砖可以在这条串列路径中有效地旋转到任何位置。
图1.7 “串列”，与空格相邻的瓷砖开始形成了一条瓷砖路径，
在游戏过程中可以像一列火车一样滑动
我们可以使用串列移动一系列的瓷砖，同时保持它们之间的相对关系。现在我们回到前面的2×3的网格配置。尽管这个网格中没有任何一个瓷砖位于它最终的正确位置，但有些瓷砖却靠近它们在最终配置中需要靠近的瓷砖。例如，在最终的配置中，4将出现在7的上面，而这两块瓷砖当前是相邻的。如图1.8所示，我们可以用一个包含6个位置的串列把4和7移动到它们最终正确的位置。当我们完成这个操作时，剩余的瓷砖几乎都处于正确的位置，只需要再移动一下8就可以了。
图1.8 从配置1出发，经过2次沿规划的“串列”旋转之后来到配置2，
然后只要滑动1次就可以产生最终的配置3
这种技巧是怎么解决所有瓷砖滑块问题的呢？考虑最初的3×3配置。我们可以用包含6个位置的串列移动相邻的1和2，使2和3相邻，如图1.9所示。
图1.9 从配置1出发，瓷砖沿规定的“串列”旋转到达配置2
这样1、2和3就相邻了。在8个位置的串列中，我们就可以旋转1、2和3了，使它们到达最终的正确位置，如图1.10所示。
图1.10 从配置1出发，瓷砖经过旋转之后到达配置2，这样瓷砖1、2和
3位于正确的最终位置
注意瓷砖4～8的位置。这些瓷砖的配置正好与前面的2×3网格的例子相同。这是一个至关重要的观察。把瓷砖1～3放在正确的位置之后，我们就可以把剩余的瓷砖看成是一个更小、更容易解决的独立问题。注意，为了使这种方法可行，必须要解决一整行或一整列的瓷砖。如果我们把瓷砖1和2放在正确的位置，但3仍然置于别处，那样就无法在不移动左上角两块已经就绪的瓷砖的情况下，把任何瓷砖移动到右上角位置。
这个技巧也可以用于解决规模更大的瓷砖滑块问题。常见的最大尺寸是15块瓷砖，也就是4×4的网格。这样的问题也可以用分解法来解决：首先把瓷砖1～4移动到正确的位置，这样就只剩下一个3×4的网格，然后再完成最左列的瓷砖，这样就只剩下一个3×3的网格。此时，就只剩下8块瓷砖需要移动了。
经验和教训
我们可以从瓷砖滑块问题中学到什么呢？
由于瓷砖移动的次数相当之多，因此无法在初始配置时就规划一个完整的解决方案。但是，无法规划完整的解决方案并不意味着就无法采取策略或技巧系统性地解决问题。在解决编程问题时，有时候会出现无法看到通向解决方案的清晰道路的情况，但这绝不能成为跳过计划和采用系统性方法的借口。更好的办法是采用一种策略，而不是通过简单地反复尝试和失败来解决问题。
我是通过对较小的问题进行研究时发现这种“串列”技巧的。在编程中，我常常会使用这种类似的技巧。在面临一个复杂的问题时，我常常会对这个问题的削减版本进行试验。这些试验常常能够产生有价值的思路。
另一个经验是问题的细分通常并不是非常明显的解决之道。由于移动一块瓷砖不仅影响这块瓷砖本身，还会影响接下来可能发生的移动，人们可能觉得瓷砖滑块问题必须在一个步骤中完成，而不能分阶段解决。因此，花时间研究怎样对问题进行细分通常是非常合算的。即使无法找到一种清晰的细分，仍然有助于增强对这个问题的理解，可以促进这个问题的解决。在解决问题时，头脑里已经拥有一个特定的目标总比随机的尝试要好得多，无论最终是否能够实现这个目标。
数独游戏作为一种在报纸和杂志上出现的益智游戏，其流行程度已经达到了惊人的地步，并且已经发展成一种基于网络和手机的游戏。数独拥有许多不同的版本，但这里只简单讨论传统的版本。
完成数独方块
一个9×9的网格，其中部分方格填有数字（1～9），玩家必须填满剩余的空格，并满足下面这个约束条件：对于每一行和每一列，每个数字恰好只出现1次。而且，对于粗框内的每个3×3区域，每个数字也恰好只出现1次。
如果读者以前曾经玩过这个游戏，很可能已经知道应该采用什么策略在最短的时间内完成一个空格。我们首先观察如图1.11所示的方块，关注最关键的起始策略。
数独游戏的难度差异极大，它们的难度取决于需要填充的空格数量。按照这种衡量方法，这是一个相当容易的问题，因为已经有36个空格已经填好，只需要再填写45个空格就可以完成任务了。问题在于，我们应该首先填充哪个空格呢？
图1.11 一个很简单的数独方块问题
记住，这个问题包含了约束条件。在每一行、每一列以及粗框内的每个3×3区域中，9个数字必须都正好出现1次。这些规则决定了我们应该从哪里着手。最中间的3×3区域的9个方格已经有8个填好了数字。因此，正中心的那个空格只可能填入这个3×3区域的其他方格没有出现的那个数字。我们应该从这个空格开始解决这个问题。这个区域所缺少的数字是7，因此我们在最中间的那个空格中填入7。
填好了这个数字之后，注意最中间那列的9个值已经有7个已经填好，只剩下2个空格，必须填上这一列所缺少的两个值：3和9。与这个列有关的约束条件允许把这两个值放在任意一个位置，但是注意3已经在第三行出现过，9已经在第七行出现过。因此，我们应该把9填在中间那列的第三行，把3填在中间那列的第七行。图1.12对这些步骤进行了概括。
图1.12 解决示例数独问题的开始步骤
我们不打算完成整个方块的填写，但前面这几个步骤已经说明了重要的一点，就是搜索那些可能出现的值最少的空格。在最理想的情况，就是只剩下一个空格。
经验和教训
我们在数独问题中所学到的主要经验就是应该寻找问题约束性最强的部分。虽然约束条件往往使问题难以着手（还记得狐狸、鹅和玉米问题吗），但它们也可以简化思路，因为它们消除了很多选择。
尽管我们不会在本书中详细讨论人工智能，但还是要简单地提一下，在人工智能中解决某些类型的问题时有一个称为“最大约束变量”的规则。它表示在一个问题中，当我们向一些不同的变量赋一些不同的值来满足约束条件时，应该从约束性最强的变量开始。换用更通俗的说法，就是那些可能采用的值具有最少的变量。
下面是这种思维方式的一个例子。假设有一组工友计划一起吃午饭，并且想要找一家每个人都喜欢的餐厅。问题在于，每个工人对于整个小组的决策都会施加某种程度的影响。例如，Pam是个素食主义者，Todd不喜欢中国菜等。如果目标是最大限度地减少寻找餐厅的时间，首先应该询问对餐厅最挑剔的那个工人。例如，如果Bob对很多食物都过敏，首先列出他可以进食的餐厅列表是非常合理的。像Todd不喜欢中国菜这样的癖好应该放在最后考虑，因为这个困难是很容易克服的。
这个技巧往往也可以用于编程问题。如果问题的某个部分具有很强的约束条件，很可能应该从这一部分开始着手，这样就不必担心把时间花在将来可能会返工的任务上了。一个相关的推论是：应该从最显而易见的那部分任务开始着手。如果可以解决这个部分的问题，就可以在此基础上继续执行其他可以完成的任务。通过审视自己的代码，可能会激发自己的想象力，从而解决剩余部分的问题。
对于上面这几个问题，读者以前可能也看到过。但是对于本章的最后一个问题，除非以前曾经阅读过本书，否则绝不可能见过，因为这是我自己“发明”的。请认真阅读，因为这个问题的描述稍微有点复杂。
打开外星锁
一种敌对的外星生物Quarrasi登陆到地球上，你在战斗中被它们抓获并关押在飞船里。你设法打倒了看守，尽管它们体形庞大并且长有触角。但是，为了逃离飞船（仍然在地面上），必须打开巨大的舱门。开门的指令非常奇怪，它是用英语的形式显示的，但非常难弄。为了打开舱门，必须沿着轨道滑动3个条状的Kratzz，从右侧的接收器滑动到位于门尽头的左侧接收器，距离大约3m。
这个任务相当简单，但是必须避免触发警报。警报的工作原理如下：每个Kratzz就是一个或多个星形的水晶力量宝石，称为Quinicrys。每个接收器具有4个传感器，如果一个纵列中Quinicrys的数量为偶，它们就会被点亮。如果被点亮的传感器的数量正好为1，就会发出警报。好消息是每个警报都配备了一个抑制器，只要按下这个按钮，就可以防止警报发出声音。如果可以同时按下所有的抑制器，问题就非常简单了，但是没有办法做到这一点，因为人类的胳膊过于短小，不比长长的Quarassi触角。
根据上面的描述，怎么才能在不触发任一警报的前提下滑动Kratzz打开舱门呢？
图1.13展示了初始配置，3个Kratzz都位于右侧的接收器。为了清晰起见，图1.14展示了一种不好的思路：把最上面那个Kratzz滑动到左侧接收器会导致右侧接收器处于报警状态。你可能想到用抑制器来避免报警，但是要记住，你刚刚把最上面的Kratzz移动到左侧接收器，够不着相距3m的右侧接收器上的抑制器。
图1.13 Quarrasi锁问题的初始配置。必须滑动当前位于右侧
接收器的3个Kratzz条，在不触发任何一个警报的情况下把它们
滑动到左侧的接收器。当偶数个星形的Quinicrys出现在上面的
纵列时，就会点亮一个传感器，如果正好有一个被连接的
传感器被点亮，就会触发警报。抑制器可以防止警报
发声，但你只能控制自己所站那一侧的抑制器
图1.14 处于报警状态的Quarrasi锁。你刚刚把最上面的Kratzz滑动到
左侧的接收器，因此够不到右侧的接收器。右侧警报的第2个传感器
被点亮，因为出现在那个纵列的Quinicrys数量为偶，现在正好
是一个传感器被点亮，所以就会触发报警
在继续尝试之前，先花点时间研究这个问题，设法确定一个解决方案。这取决于看问题的着眼点，此问题并没有看上去那么难。认真地说，要在尝试之前先对它进行思考！
考虑好了吗？现在是不是能够想出一个解决方案？
为了回答这个问题，可以选择两条可能的路径。第一条路径就是不断尝试，不过它是错误的做法：尝试用各种方式移动这几个Kratzz，一旦达到警报状态时就返回到前一步骤，直到最终通过一系列的移动，成功地打开锁。
第二条路径是认识到这个问题实际上是个机关。你从前可能没看到过这种机关，它实际上就是披着伪装外衣的狐狸、鹅和玉米问题。尽管警报的规则是以通用的方式描述的，但是与这种特殊的锁有关的组合却是有限的。如果只考虑3个Kratzz，我们只需要知道接收器上的哪些Kratzz组合是可以接受的。如果我们把这3个Kratzz分别命名为top、middle和bottom，那么会触发报警的组合是“top和middle”以及“middle和bottom”。
如果我们把top重新命名为狐狸，把middle重新命名为鹅，把bottom重新命名为玉米，这样所有的麻烦组合都与狐狸、鹅和玉米问题一样了，也就是“狐狸和鹅”和“鹅和玉米”。
因此，这个问题的解决方式与狐狸、鹅和玉米问题相同。我们把middle（鹅）滑动到左侧的接收器，再把top（狐狸）滑动到左侧，当我们移动top（狐狸）时摁住左侧警报的抑制器；接着，我们把middle（鹅）滑动回右侧的接收器；然后，我们把bottom（玉米）滑动到左侧；最后，我们把middle（鹅）再次滑动到左侧，这样就打开了锁。
本文节选自《像程序员一样思考（修订版）》