第3-4课：爱因斯坦的思考题（下）

接上一课，我们继续分析搜索算法是如何实现的。

搜索算法实现

与其他穷举类算法一样，本问题的穷举法的实现也包含两个典型过程，一个是对所有状态的穷举过程，另一个是对状态的正确判定过程。本问题的穷举搜索过程明显比之前的几个题目复杂，因为每个状态有 5 个类型，每个类型都要对 5 个值进行排列组合。

枚举所有状态

前几课介绍了几个线性空间的搜索和树状空间的搜索的例子，这些例子中的状态都比较简单，可以边遍历边生成新状态，并且状态的合法性判断也比较简单。本题则有些特殊，需要对不同类型的元素分别用穷举法进行枚举遍历，然后再将枚举遍历的结果按照组的关系组合起来才能得到一个状态（完整的二维表），并且组合的方法不是线性关系的组合，而是类似阶乘的几何关系的组合。

状态遍历算法的具体思路就是按照 group 中的元素顺序，依次确定状态二维表中各个元素的值。首先对房子根据颜色组合进行穷举，每得到一组房子颜色组合后，记录到状态二维表的第一列，然后在此基础上对住在房子里的人的国籍进行穷举，将国籍的穷举结果记录到二维状态表的第二列，同时将国籍穷举得到的集合与房子颜色的结果做排列组合，并在这个组合结果的基础上，继续对饮料类型进行穷举和排列组合。以此类推，直到穷举完最后一种类型得到完整的状态二维表。其遍历组合的过程如图（1）所示，在这么多组合的结果中，只有蓝色的那一个组合结果才完全符合题目的要求，是一个正确的结果。

图（1）爱因斯坦